〇.简介

Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

下面针对各个实现类的特点做一些说明：

HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

在JDK8中HashMap的实现由原先的数组加链表，也就是通过链地址法，解决哈希冲突，变成了数组加链表加红黑树，如图所示

当链表长度大于8时，链表会变成红黑树，这样做的目的是为了改进之前由于hash函数选择不好导致链表过长的查询瓶颈，之后会具体介绍。

一. 关键参数及构造方法

/* ---------------- Fields -------------- */  
  
    //存储节点的table数组，第一次使用的时候初始化，必要时resize，长度总是2的幂 
    transient Node<K,V>[] table;  
  
    //缓存entrySet，用于keySet() and values()  
    transient Set<Map.Entry<K,V>> entrySet;  
  
    //容器中元素的个数  
    transient int size;  
  
    //每次扩容和更改map结构的计数器  
    transient int modCount;  
  
    //阈值，当实际大小超过阈值时，会进行扩容  
    int threshold;  
  
    //装载因子  
    final float loadFactor;      
  
    //默认的初始容量，必须是2的幂次，出于优化考虑，默认16  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
  
    //默认的最大容量  
    static final int MAXIMUM_CAPACITY = 1 << 30;  
  
    //默认的装载因子，在无参构造器中默认设为该值  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
  
    //阈值，当链表中节点数大于该阈值后就会转变成红黑树  
    static final int TREEIFY_THRESHOLD = 8;  
  
    //与上一个阈值相反，当小于这个阈值后转变回链表  
    static final int UNTREEIFY_THRESHOLD = 6;  
  
    // 看源码注释里说是：树的最小的容量，至少是 4 x TREEIFY_THRESHOLD = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64  
    static final int MIN_TREEIFY_CAPACITY = 64;  
  
  
  
    //基本哈希容器节点 实现Map.Entry接口  
    static class Node<K,V> implements Map.Entry<K,V> {  
        final int hash;//不可变的哈希值，由关键字key得来  
        final K key;//不可变的关键字  
        V value;  
        Node<K,V> next;  
  
        Node(int hash, K key, V value, Node<K,V> next) {  
            this.hash = hash;  
            this.key = key;  
            this.value = value;  
            this.next = next;  
        }  
  
        public final K getKey()        { return key; }  
        public final V getValue()      { return value; }  
        public final String toString() { return key + "=" + value; }  
  
        public final int hashCode() {//Node对象的哈希值，关键字key的hashCode()与值value的hashCode()做异或运算    
            return Objects.hashCode(key) ^ Objects.hashCode(value);  
        }  
  
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
  
        public final boolean equals(Object o) {//对象相同或同类型且key-value均相同，则返回true    
            if (o == this)  
                return true;  
            if (o instanceof Map.Entry) {  
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;  
                if (Objects.equals(key, e.getKey()) &&  
                    Objects.equals(value, e.getValue()))  
                    return true;  
            }  
            return false;  
        }  
    }  
      
    /* 
     * 构造函数 
     */  
      
    public HashMap(int initialCapacity, float loadFactor) {//给定初始容量和装载因子，构造一个空的HashMap  
        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);//根据指定的容量计算容量，因为必须是2的幂次，虽然将该值赋给threshold，但表示的依然是容量，到时候会重新计算阈值  
    }  
  
    public HashMap(int initialCapacity) {//指定初始容量，和默认装载因子0.75构造空HashMap  
        this(initialCapacity, DEFAULT_LOAD_FACTOR);  
    }  
  
    public HashMap() {//无参，使用默认的初始容量16,和装载因子0.75构造空的HashMap  
        this.loadFactor = DEFAULT_LOAD_FACTOR;   
    }  
  
    public HashMap(Map<? extends K, ? extends V> m) {//构造一个和给定Map映射相同的HashMap，默认装载因子，初始空间以足够存放给定Map中的映射为准   
        this.loadFactor = DEFAULT_LOAD_FACTOR;  
        putMapEntries(m, false);  
    }      
}

注释中给出了相应解释，下面再着重介绍几个参数。

1. table数组

也就是我们之前所说的HashMap实现中的数组，通过对key计算hash后得到相应数组的index，数组中存储着相同index的链表首结点或者红黑树的根节点，结点类型就是上面代码中的Node

2. 容量，装载因子，阈值

threshold = loadFactor * capcity

由于这样的一个对应关系，这三个变量在HashMap中只有threshold和loadFactor这两个是明确给出来的。在给出初始容量和装载因子的构造函数中我们可以发现，threshold被作为了初始化的容量变量，他将在第一次调用resize()中被使用。

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);
}

容量的默认值是16，装载因子默认为0.75, 至于为什么要有装载因子这个设定，而不是在table数组满了再扩容，文档中是这么说的

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

意思总结差不多就是这是时间和空间均衡后的决定。我们也知道hashmap是用空间换时间，0.75这个装载因子能在二者之间达到一个比较好的平衡。反正就是我们不要乱改就好了。

二. 关键方法

1.hash()

在对hashCode()计算hash时具体实现是这样的：

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

他的执行过程如图所示：

其实就是将本身的hashcode的高16位和低16位做了一个异或操作。至于为什么要这么做呢？这里牵扯到了table数组中index的计算。

1	index = (n - 1) & hash

n为数组的长度，而table长度n为2的幂，而计算table数组下标的时候，举个例子，加入n=16，那么n-1=15的二进制表示就是0x0000 1111，可以看出，任何一个2的幂次减1后二进制肯定都是这种形式，它的意义在于，任何一个值和它做&操作，得到的结构肯定都在0~(n-1)之间，也就是说计算出来的下标值肯定数组的合法下标，这种方式由于使用了位运算比单纯的取模更快。

但问题也来了，设计者认为这方法很容易发生碰撞。为什么这么说呢？不妨思考一下，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。

因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

2.put

put方法的流程如下：

如果table数组为空，那么调用resize()方法新建数组
对key的hashCode()做hash，然后再计算index;
如果没碰撞直接放到bucket里；
如果碰撞了，放在以链表的形式存在buckets后；
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
如果节点已经存在就替换old value(保证key的唯一性)

如果bucket满了(超过load factor*current capacity)，就要resize

public V put(K key, V value) {  
     return putVal(hash(key), key, value, false, true);  
 }      
   
 /* 
  * 实现Map.put以及相关方法 
  * 向map中加入个节点 
  * 没有分析onlyIfAbsent和evict 
  */       
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  
    Node<K, V>[] tab;//指向table数组  
    Node<K, V> p;//对应下标中的第一个节点，为null说明没有碰撞，不为null代表链表第一个元素或红黑树根节点  
    int n, i;//n为table数组的长度，2的幂次; i表示对应的下标index  
    if ((tab = table) == null || (n = tab.length) == 0) // 如果table为空即第一次添加元素，则进行初始化  
        n = (tab = resize()).length;  
    /* 
     * 计算下标，根据hash与n计算index 
     * 公式:i = (n - 1) & hash; 
     */  
    // p=table[i]; 对应下标中的第一个节点  
    if ((p = tab[i = (n - 1) & hash]) == null) // p为null说明没有碰撞，  
        tab[i] = newNode(hash, key, value, null);//直接新建一个节点加入就可以了  
    else {// p不为null，说明有碰撞  
        Node<K, V> e;//e，代表map中与给定key值相同的节点  
        K k;//代表e的key  
        // p的关键字与要加入的关键字相同，则p就是要找的e  
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;  
        // 如果p的类型是红黑树，则向红黑树中查找e  
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  
        // 否则就是链表  
        else {  
            for (int binCount = 0;; ++binCount) {//遍历链表查找e，如果找不到就新建一个  
                if ((e = p.next) == null) {// 如果next为null，说明没有找到  
                    p.next = newNode(hash, key, value, null);// 那么新创建一个节点  
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 加入节点后如果超出树形化阈值  
                        treeifyBin(tab, hash);// 则转换为红黑树  
                    break;  
                }  
                if (e.hash == hash && // 找到关键字相同的节点，退出循环  
                        ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  
                p = e;  
            }  
        }  
        if (e != null) { //e不为null，说明原来存在对应的key，那么返回原来的值  
            V oldValue = e.value;// 保留原来的值，用于返回  
            if (!onlyIfAbsent || oldValue == null)  
                e.value = value;  
            afterNodeAccess(e);  
            return oldValue;  
        }  
    }  
    //说明新插入了一个节点，返回null  
    ++modCount;  
    if (++size > threshold) // 超过临界值，则resize  
        resize();  
    afterNodeInsertion(evict);  
    return null;  
}

3. get() 和 containsKey()方法

这两个方法是最常用的，都是根据给定的key值，一个获取对应的value，一个判断是否存在于Map中，在内部这两个方法都会调用一个finall方法，就是getNode()，也就是查找对应key值的节点。

getNode方法的大致过程：

table里的第一个节点，直接命中；
如果有冲突，则遍历链表或二叉树去查找相同节点
查找节点时先判断hash值是否相等
如果hash值相等，再判断key值是否相等
判断key值相等时，用==或equals或，整个判断条件为：

(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

public V get(Object key) {  
    Node<K,V> e;  
    return (e = getNode(hash(key), key)) == null ? null : e.value;  
}  
public boolean containsKey(Object key) {  
    return getNode(hash(key), key) != null;  
}  
/* 
 * 实现Map.get以及相关方法 
 */  
final Node<K,V> getNode(int hash, Object key) {  
    Node<K,V>[] tab; //指向table数组  
    Node<K,V> first, e; //first为table[index]，即所在数组下标中第一个节点；e用于遍历节点  
    int n; K k;//n为table的长度，k用于指向节点的key  
    if ((tab = table) != null && (n = tab.length) > 0 &&//首先必须保证table数组不为空                 
        (first = tab[(n - 1) & hash]) != null) {//计算下标，保证数组下标中第一个节点不为null不然就肯定找不到直接返回null  
        if (first.hash == hash && // 先检查第一个节点hash值是否相等  
            ((k = first.key) == key || (key != null && key.equals(k))))//再判断key，如果相等直接返回  
            return first;  
        if ((e = first.next) != null) { //第一个不符合，就从下一个开始找  
            if (first instanceof TreeNode)//红黑树 O(logn)  
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
            do {//不然就是链表O(n)  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    return e;  
            } while ((e = e.next) != null);  
        }  
    }  
    return null;  
}

4. resize()

从put函数我们不难看出，当table数组为空，或者当加入某个元素后超过阈值，都会调用resize()进行扩容，他的目的就在于将链表和红黑树分散，使得碰撞分散，提高查询效率。简单来说就是下面的步骤：

将容量和阈值扩大两倍，如果超过最大值就使用最大值最为新的容量和阈值
新建一个大小为新容量的table，然后将之前的结点放进去

这里有一个很有意思的小技巧，还记得我们的index是怎么计算的吗？

1	index = (n - 1) & hash

假设我们的容量没有超标，由于容量都是2的幂，这里的n扩大2倍，相当于在原来的n-1的基础上高位增加了一个1，说白了就是多取了一位的hash。如图所示

所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置，因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

final Node<K,V>[] resize() {  
    Node<K,V>[] oldTab = table;  
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  
    int oldThr = threshold;  
    int newCap, newThr = 0;  
    /* 
     * step1: 先根据容量和阈值确定新的容量和阈值 
     */  
    //case1: 如果table已经被初始化，说明不是第一次加入元素  
    if (oldCap > 0) {              
        if (oldCap >= MAXIMUM_CAPACITY) {//如果table的容量已经达到最大值，那么就不再扩容了，碰撞也没办法  
            threshold = Integer.MAX_VALUE;//那么扩大阈值到最大值  
            return oldTab;//原来的table不变  
        }  
        //不然的话table的容量扩大2倍，newCap = oldCap << 1            大部分情况下肯定都是这种情况              
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  
            newThr = oldThr << 1; //阈值也扩大2倍  
    }          
    //case2: table没有被初始化，但是阈值大于0，说明在构造函数中指定了容量，但是容量存在阈值那个变量上  
    else if (oldThr > 0)  
        newCap = oldThr;//那么将阈值设置为table的容量，下面还会重新计算阈值  
    //case3: table和阈值都没有初始化，说明是无参构造函数  
    else {                 
        newCap = DEFAULT_INITIAL_CAPACITY;//使用默认的初始容量  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//计算默认的阈值，threshold=load_factor*capacity  
    }  
    //重新计算阈值  
    if (newThr == 0) {  
        float ft = (float)newCap * loadFactor;  
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                  (int)ft : Integer.MAX_VALUE);  
    }  
    /* 
     * step2: 更新阈值和新容量的table 
     */  
    threshold = newThr;  
    @SuppressWarnings({"rawtypes","unchecked"})  
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
    table = newTab;  
    /* 
     * step3: 将原来table中元素，加入到新的table中 
     */               
    if (oldTab != null) {  
        for (int j = 0; j < oldCap; ++j) {  
            Node<K,V> e;  //e = oldTab[j]
            if ((e = oldTab[j]) != null) {  
                oldTab[j] = null;  
                if (e.next == null)  //e所在位置没有哈希冲突，只有一个元素，直接计算
                    newTab[e.hash & (newCap - 1)] = e;  
                else if (e instanceof TreeNode)  //e所在位置是一颗红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
                else {// e所在位置是一个链表，则遍历链表
                  	// 根据e.hash & oldCap) == 0，确定放入lo还是hi两个链表
                  	// 其实就是判断e.hash是否大于oldCap
                  	// lo和hi两个链表放分别放在在newTab[j]和newTab[j + oldCap]
                    Node<K,V> loHead = null, loTail = null;  
                    Node<K,V> hiHead = null, hiTail = null;  
                    Node<K,V> next;  
                    do {  
                        next = e.next;  
                        if ((e.hash & oldCap) == 0) {  
                            if (loTail == null)  
                                loHead = e;  
                            else  
                                loTail.next = e;  
                            loTail = e;  
                        }  
                        else {  
                            if (hiTail == null)  
                                hiHead = e;  
                            else  
                                hiTail.next = e;  
                            hiTail = e;  
                        }  
                    } while ((e = next) != null);  
                    if (loTail != null) {  
                        loTail.next = null;  
                        newTab[j] = loHead;  
                    }  
                    if (hiTail != null) {  
                        hiTail.next = null;  
                        newTab[j + oldCap] = hiHead;  
                    }  
                }  
            }  
        }  
    }  
    return newTab;  
}

三. 性能探讨

1.hashcode()

HashMap的查询效率我们理论上看做是O(1),这是在没有发生冲突的情况下，但是当发生冲突较严重的时候，我们会浪费很多的时间在链表的查询或者红黑树的查询，以至于退化为O(n)或者O(logn),所以当作为key的类型，其Hashcode()函数的设计尤为重要。

2. Key的要求

由上一条可知，一个作为key的类型，首先需要有一个设计良好的Hashcode函数，其次我们发现，在get函数中，我们首先判断hashcode相等，再判断equals()或者==来判断是否为同一个对象，因为hashcode相等的两个对象不一定相等，由此可见作为key的另一个条件时重写了equals方法。最后还有一个隐藏条件，key需要为不可变对象比如String，什么叫不可变对象呢？
不可变对象就是创建后状态不能修改的对象，因为只有这样才能确保hashcode不发生变化，才能保证能找到相应的key，总结起来就是一下三个：

重写hashcode（）
重写equals（）
不可变对象

四. 引用

https://tech.meituan.com/java-hashmap.html
http://paine1690.github.io/2016/11/12/Java/JDK/HashMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/