Map的实现类有很多，其中较为常见的有HashMap，HashTable，LinkedHashMap，TreeMap，下面分别对这几个类进行简单的分析：

1、HashMap

HashMap的结构数组+链表的组合。

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

在创建HashMap时，可以选择设置容量initialCapacity和加载因子loadFactor。

1)

initialCapacity默认值是16。我们可以根据需求自己设置，不过它会把我们设置的值进行处理，看看源码中是怎么处理的：

static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

在二进制中，除了符号位，最高有效位必然是1，经过一连串位移和或预算，n的值将变成11……11的形式，再加1变成100……00的形式，即最后获取的值将是不小于cap的2的最低次幂。

2)

loadFactor的默认值为0.75，当前最大容量为数组长度*加载因子。所以如果我们在创建HashMap对象时不做任何设置，HashMap对象的最大容量为16*0.75=12个，超过则扩容。

扩容是一个非常耗费资源的过程，最好我们最好根据具体需求设置合适的initialCapacity和loadFactor。

---

在添加键值对时，HashMap会对Key的hash码做均匀化处理：

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

再来看看添加时的操作：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

将key的hash码处理后的值和数组长度做与运算，确定下标，若数组的这个位置为null，则将键值对生成的新对象放在这个位置，否则，添加到此链表的尾部。

到这里就能看出，HashMap将数组长度设为2的次幂，将key的hash码均匀化处理的原因了，因为这样使整个散列均匀化分布，提高插入和查询的效率。

---

2、HashTable

hashTable也是数组+链表的结构，它也实现了Map接口，但它继承了陈旧的Dictionary类，Dictionary是java早期设计的类，相比HashMap有很多不足之处。

在初始化的时候，默认的数组长度为11，也可以在创建HashTable对象时自己设定，与HashMap不同的是，HashTable数组长度直接就是我们设置的值，不做其它处理。

下面是HashTable添加新元素时的操作：

private void addEntry(int hash, K key, V value, int index) {
modCount++;

    Entry<?,?> tab\[\] = table;  
    if (count >= threshold) {  
        // Rehash the table if the threshold is exceeded  
        rehash();

        tab = table;  
        hash = key.hashCode();  
        index = (hash & 0x7FFFFFFF) % tab.length;  
    }

    // Creates the new entry.  
    @SuppressWarnings("unchecked")  
    Entry<K,V> e = (Entry<K,V>) tab\[index\];  
    tab\[index\] = new Entry<>(hash, key, value, e);  
    count++;  
}

对于索引值它也只是对key的hash码做简单的绝对值取余处理，而且在添加元素时，并不是如同HashMap一样加在链表的末端，而是放在表头。

除此之外，HashTable的key和value都不能是null，HashMap可以。

HashTable是线性安全的，而HashMap非线性安全。

---

3、LinkedHashMap

LinkedHashMap是HashMap的子类，相比于HashMap它最大的特点是它是有序的。它的顺序可分为两种：插入顺序和访问顺序，因此它常用于Lru算法中。

public LinkedHashMap(int initialCapacity,  
                     float loadFactor,  
                     boolean accessOrder) {  
    super(initialCapacity, loadFactor);  
    this.accessOrder = accessOrder;  
}

accessOrder为true则为访问顺序；false则为插入顺序。

相比于HashMap，它的Entry增加了前一个Entry对象before和后一个Entry对象after：

static class Entry<K,V> extends HashMap.Node<K,V> {  
    Entry<K,V> before, after;  
    Entry(int hash, K key, V value, Node<K,V> next) {  
        super(hash, key, value, next);  
    }  
}

新插入的对象放在末尾：

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {  
    LinkedHashMap.Entry<K,V> last = tail;  
    tail = p;  
    if (last == null)  
        head = p;  
    else {  
        p.before = last;  
        last.after = p;  
    }  
}

访问过的对象放在末尾，前后对象互为前后：

public V get(Object key) {  
    Node<K,V> e;  
    if ((e = getNode(hash(key), key)) == null)  
        return null;  
    if (accessOrder)  
        afterNodeAccess(e);  
    return e.value;  
}

void afterNodeAccess(Node<K,V> e) { // move node to last  
    LinkedHashMap.Entry<K,V> last;  
    if (accessOrder && (last = tail) != e) {  
        LinkedHashMap.Entry<K,V> p =  
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;  
        p.after = null;  
        if (b == null)  
            head = a;  
        else  
            b.after = a;  
        if (a != null)  
            a.before = b;  
        else  
            last = b;  
        if (last == null)  
            head = p;  
        else {  
            p.before = last;  
            last.after = p;  
        }  
        tail = p;  
        ++modCount;  
    }  
}

---

4、TreeMap

TreeMap的结构是红黑树，相比于前面几种Map，要复杂许多。

TreeMap的一大功能就是可以根据设定规则进行排序，下面为一个简单示例：

public class Test {
public static void main(String[] args) {
Comparator comparator = new Comparator() {

        @Override  
        public int compare(Person o1, Person o2) {  
            return o1.compareTo(o2);  
        }

    };  
    Map<Person, String> map = new TreeMap<>(comparator);  
    map.put(new Person(1), "first");  
    map.put(new Person(2), "second");  
    map.put(new Person(4), "third");  
    map.put(new Person(3), "fourth");  
    iterate(map);  
    /\*  
    output:  
        key:1;value:first  
        key:2;value:second  
        key:3;value:fourth  
        key:4;value:third  
    \*/  
}  
public static <K,V> void iterate(Map<K,V> map){  
    for(Entry<K, V>  entry:map.entrySet()){  
        System.out.println("key:"+entry.getKey()+";value:"+entry.getValue());  
    }  
}  

}

class Person implements Comparable {

private int id;

public Person(int id) {  
    this.id = id;  
}

public void setId(int id) {  
    this.id = id;  
}

public int getId() {  
    return id;  
}

@Override  
public int compareTo(Person person) {  
    if (this.id < person.getId()) {  
        return -1;  
    } else if (this.id == person.id) {  
        return 0;  
    } else {  
        return 1;  
    }  
}

@Override  
public String toString() {  
    return id + "";  
}

}