【精分】HashMap最全最详细分析汇总

[jifuwei]

问题

• HashMap如何初始化？
• 添加元素put流程？
• 为何加载因子默认为0.75，而不是其他数字？
• 为何数组容量必须是2次幂，默认值为何是16而不是其他数字？
• 获取hash值时：为何在hash方法中加上异或无符号右移16位的操作？
• 红黑树了解么？为何1.8后要改为红黑树？为何链表转红黄黑树的默认值是8而不是其他数字？为何树形化需要检测当前数组长度超过64？
• 扩容流程？老节点位置是如何变化的？1.7和1.8有何区别？
• Hashmap 为何不是线程安全的？什么情况下会发生？
• 为何hashmap允许存储key和value都会null的值，而hashtable不允许？
• JDK 7与 8中关于HashMap的对比

HashMap如何初始化？

• 应不应该设置HashMap的默认容量？
• 如果真的要设置HashMap的初始容量，我们应该设置多少？

HashMap有扩容机制，随着元素的增加，到达指定的扩容条件时：size >= threshold = loadFactor * capacity,就会自动扩容。

如果不设置初始容量大小，随着元素的增加，发生多次扩容，而扩容机制是每次都需要重建hash表，是非常影响运行性能的！

那既然需要设置初始化容量，究竟设置多少？

当我们通过HashMap(int initialCapacity)设置初始容量的时候，HashMap并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。白这个不发是2的幂次方。

不管是Jdk 1.7还是Jdk 1.8，计算初始化容量的算法其实是如出一辙的，主要代码如下：

/**
* Returns a power of two size for the given target capacity.
*/
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;
}

代码的目的是：通过计算，得到第一个比他大的2的幂并返回。
理解上面代码：对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。

举例：

目标数h              ->  6 
转换为二进制          ->  0000 0000 0110

h >>> 1             ->  0000 0000 0010
h = (h | h >>> 1)   ->  0000 0000 0110

h >>> 2             ->  0000 0000 0001
h = (h | h >>> 2)   ->  0000 0000 0111

h >>> 4             ->  0000 0000 0000
h = (h | h >>> 4)   ->  0000 0000 0111

h >>> 8             ->  0000 0000 0000
h = (h | h >>> 8)   ->  0000 0000 0111

h >>> 16            ->  0000 0000 0000
h = (h | h >>> 16)  ->  0000 0000 0111

通过几次 无符号右移 和 按位或 运算，把0000 0000 0110转换成了0000 0000 0111，再加1，就得到了0000 0000 1000，也就是7转换为8。

但是还有一种特殊情况套用以上公式不行，这些数字就是2的幂自身。如果数字8 套用公式的话。得到的会是 16。

为了解决这个问题，JDK的工程师把所有用户传进来的数在进行计算之前先-1，就是源码中的第一行：

int n = cap - 1;

至此，再来回过头看看这个设置初始容量的代码，目的是不是一目了然了。

当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。那么，是不是我们只需要把已知的HashMap中即将存放的元素个数直接传给initialCapacity就可以了呢？

关于这个值的设置，参考的是JDK8中putAll方法

return (int) ((float) expectedSize / 0.75F + 1.0F);

虽然，当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。但是这个值并没有参考loadFactor的值。
也就是说，如果我们设置的默认值是7，经过Jdk处理之后，会被设置成8，但是，这个HashMap在元素个数达到 8*0.75 = 6的时候就会进行一次扩容，这明显是我们不希望见到的。

如果我们通过expectedSize / 0.75F + 1.0F计算，7/0.75 + 1 = 10 ,10经过Jdk处理之后，会被设置成16，这就大大的减少了扩容的几率。
当HashMap内部维护的哈希表的容量达到75%时（默认情况下），会触发rehash，而rehash的过程是比较耗费时间的。所以初始化容量要设置成expectedSize/0.75 + 1的话，可以有效的减少冲突也可以减小误差。

所以，当我们明确知道HashMap中元素的个数的时候，把默认容量设置成expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

总结

当我们想要在代码中创建一个HashMap的时候，如果我们已知这个Map中即将存放的元素个数，给HashMap设置初始容量可以在一定程度上提升效率。

但是，JDK并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到一个2的幂。原因在得到这个数字的算法其实是使用了使用无符号右移和按位或运算来提升效率。

为了最大程度的避免扩容带来的性能消耗，我们建议可以把默认容量的数字设置成expectedSize / 0.75F + 1.0F

添加元素流程？

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//将key的哈希值，进行高16位和低16位异或操作，增加低16位的随机性，降低哈希冲突的可能性
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<K,V>[] tab; Node<K,V> p; int n, i;
    //首次table为null，首先通过resize()进行数组初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //利用index=(n-1)&hash的方式，找到索引位置
    //如果索引位置无元素，则创建Node对象，存入数组该位置中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {  //如果索引位置已有元素，说明hash冲突，存入单链表或者红黑树中
        Node<K,V> e; K k;
        //hash值和key值都一样，则进行value值的替代
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) //hash值一致，key值不一致，且p为红黑树结构，则往红黑树中添加
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { //hash值一致，key值不一致，且p为单链表结构，则往单链表中添加
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.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) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) //当元素个数大于新增阈值，则通过resize()扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

流程：

为何加载因子默认为0.75？

The documentation explains it pretty well:

/* <p>An instance of <tt>HashMap</tt> has two parameters that affect its
 * performance: <i>initial capacity</i> and <i>load factor</i>.  The
 * <i>capacity</i> is the number of buckets in the hash table, and the initial
 * capacity is simply the capacity at the time the hash table is created.  The
 * <i>load factor</i> is a measure of how full the hash table is allowed to
 * get before its capacity is automatically increased.  When the number of
 * entries in the hash table exceeds the product of the load factor and the
 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.
 *
 * <p>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 <tt>HashMap</tt> class, including
 * <tt>get</tt> and <tt>put</tt>).  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.
 */

默认的负载系数（.75）在时间和空间成本之间提供了一个很好的权衡。较高的值会减少空间开销，但会增加查找成本（在HashMap类的大多数操作中都得到体现，包括get和put）。

为何数组容量必须是2次幂？

索引计算公式为i = (n - 1) & hash，如果n为2次幂，那么n-1的低位就全是1，哈希值进行与操作时可以保证低位的值不变，从而保证分布均匀，效果等同于hash%n，但是位运算比取余运算要高效的多。

获取hash值时：为何在hash方法中加上异或无符号右移16位的操作？

此方式是采用"扰乱函数"的解决方案，将key的哈希值，进行高16位和低16位异或操作，增加低16位的随机性，降低哈希冲突的可能性。

红黑树了解么？为何1.8后要改为红黑树？为何链表转红黄黑树的默认值是8而不是其他数字？为何树形化需要检测当前数组长度超过64？

红黑树

红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：

• 每个节点都只能是红色或者黑色
• 根节点是黑色
• 每个叶节点（NIL节点，空节点）是黑色的。
• 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

对于红黑二叉树而言它主要包括三大基本操作：左旋、右旋、着色。

当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，如果 hash 冲突严重，由这里产生的性能问题尤为突显。

JDK 1.8 中引入了红黑树，当链表长度 >= TREEIFY_THRESHOLD（8） & tab.length >= MIN_TREEIFY_CAPACITY（64）时，链表就会转化为红黑树，它的查找时间复杂度为 O(logn)，以此来优化这个问题。

为什么链表的长度为8是变成红黑树？为什么为6时又变成链表？

document say's:

/* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  In
* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million
*/

TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。

这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。

通俗点将就是put进去的key进行计算hashCode时 只要选择计算hash值的算法足够好(hash碰撞率极低)，从而遵循泊松分布，使得桶中挂载的bin的数量等于8的概率非常小，从而转换为红黑树的概率也小，反之则概率大。

所以，之所以选择8，不是拍脑袋决定的，而是根据概率统计决定的。由此可见，发展30年的Java每一项改动和优化都是非常严谨和科学的。

树化操作：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

注意，并不是只要满足了单链表节点 >= 8 就树化，此处还判断了table.size是否满足 MIN_TREEIFY_CAPACITY = 64，否则扩容

为什么需要 > 64才能转为树化操作？

并未找到官方的解释，以下是我个人猜测：

• 转化树节点是比普通节点要多2被占用的，能不转则不转
• 依据泊松分布理论，如果hash的分部足够好，基本上不会出现超过8个元素，但是如果数据的技术很小，而又hash冲突特别多，此时应扩容打散一半到当前节点和+ oldCap节点上，若大数组依然冲突的厉害，则考虑上红黑树，减少查询时间

此处的核心问题应该是违背了泊松分布理论，即hash算法的问题，导致太多冲突，所以java编写大佬们才使用红黑树保证查询效率（治不了你，只能预防你 哈哈哈）

扩容流程？老节点位置是如何变化的？1.7和1.8有何区别？

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//数组不为空
        if (oldCap >= MAXIMUM_CAPACITY) { //当前长度超过MAXIMUM_CAPACITY，新增阈值为Integer.MAX_VALUE
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) //进行2倍扩容，如果当前长度超过初始16，新增阈值也做2倍扩容
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // 数组为空，指定了新增阈值
        newCap = oldThr;
    else { //数组为空，未指定新增阈值，采用默认初始大小和加载因子，新增阈值为16*0.75=12
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) { //按照给定的初始大小计算扩容后的新增阈值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; //扩容后的新增阈值
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //扩容后的数组
    table = newTab;
    if (oldTab != null) {  //将原数组中元素放入扩容后的数组中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) //无后继节点，则直接计算在新数组中位置，放入即可
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) //为树节点需要拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { //有后继节点，且为单链表，将原数组中单链表元素进行拆分，一部分在原索引位置，一部分在原索引+原数组长度
                    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) { //哈希值和原数组长度进行&操作，为0则在原数组的索引位置，非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;
}

JDK 1.7:
单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的�哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。

JDK 1.8:
JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

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

//哈希值和原数组长度进行&操作，为0则在原数组的索引位置，非0则在原数组索引位置+原数组长度的新位置
if ((e.hash & oldCap) == 0) {
}

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置

内部流程：

为何hashmap允许存储key和value都会null的值，而hashtable不允许？

在并发下，如果 map.get(key) = null，ConcurrentMap 无法判断 key 的 value 为null，还是 key 不存在。
但是 HashMap 只考虑在非并发下运行，可以用 map.contains(key) 来做判断。

JDK 7与 8中关于HashMap的对比

• jdk7中使用数组+链表来实现，jdk8使用的数组+链表+红黑树
• hash 值的计算方式不同 (jdk 8 简化)
  为什么jdk8的hash函数会变简单？jdk8中我们知道用的是链表过度到红黑树，效率会提高，所以jdk8提高查询效率的地方由红黑树去实现，没必要像jdk那样右移那么复杂。
• 1.7 table 在创建 hashmap 时分配空间，而 1.8 在 put 的时候分配，如果 table 为空，则为 table 分配空间
• 在发生冲突，插入链中时，7 是头插法，8 是尾插法
  jdk8中为什么新来的元素是放在节点的后面？我们知道jdk8链表大于8的时候就要树化，本身就要算这个链表的长度有多大，链表算大小就要一个个去遍历了，遍历到了才能知道数量，也可以直接把数据放到后面了，这样也是很方便，减少了把数据移动到头数组位置这一步，效率也提高了。而且，jdk7中出现的那个HashMap死循环bug不会有了，因为这里是只是平移，没有调换顺序
• 在 resize 操作中，7 需要重新进行 index 的计算，而 8 不需要，通过判断相应的位是 0 还是 1，要么依旧是原 index，要么是 oldCap + 原 index
• 在jdk7中，节点是Entry，在jdk8中节点是Node，其实是一样的

一些不重要的：

jdk7里面addEntry方法扩容的条件size>threshold，还有一个很容易忽略的，就是null!=table[bucketIndex],这个是什么意思？意思是如果当前放进来的值的那个位置也被占用了，才进行扩容，否则还是放到那个空的位置就行了，反正不存在hash冲突。（但是在jdk8里面取消了这个限制，只要达到了threshold，不管原来的位置空不空，还是要扩容）

jdk8 默认初始化大小16，加载因子0.75。还有一个默认的树化的大小8。非树化大小为6，也就是红黑树的元素小于6的时候，又会变回一个链表。