鸡汤

 在超凡入圣与无恶不作之间还有第三种抉择，这是所有成熟的成年人都会选择的一条路。因此你会在得失之间求得平衡，两害相权取其轻，尽力将善意放在前面。
                                         --《肖申克的救赎》

我们真的懂HashMap吗

 关于Java的集合框架，这是一个面试都被问烂了的问题。相信很多人都已经对HashMap的源码掌握得滚瓜烂熟了，面试也能对答如流。但是我们真的有认真的想过为什么JDK会这样来实现一个HashMap吗？下面我问大家几个问题（基于JDK1.8）：

1、为什么HashMap不直接使用native的hashcode来直接对数组长度求值，而是在hashcode上再次进行了一次hash运算？
2、为什么HashMap的长度是2的n次幂，扩容是2倍扩容，而ArrayList扩容却是1.5倍？
3、向默认生成的HashMap中放入256个不同的值，会导致几次扩容？
4、HashMap的entry链表什么时候会转化为红黑树？

---

上面的问题自认为都能准确回答的大佬们可以不需要再往下看了

---

如果对上面的问题，你仍保持疑问，那今天我就跟大家一起来研究研究HashMap的源码，去寻找答案。

源码分析

hashCode的奥妙

我们先找到第一个问题对应的代码，进入HashMap的put()方法

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

可以看到在putVal()之前调用了hash(key)这个方法对key进行了hash运算

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

 这里我们会发现key的hash值并不是简单的使用了hashCode()方法求值，而是对hashCode值进行了一次移位+异或运算。在回答这个问题之前我们先来设想一些极端的案例：
如果现在我要向一个HashMap中放入如下一些值（hashCode二进制表示）：

• 11110000001111110000000000111111
• 11110000001100110000000000111111
• 11000000001101110000000000111111
• 11000000001101100000000011111111
  假设此时map数组的长度为32，二进制表示为00000000000000000000000000100000
  我们知道HashMap中定位数组索引的算法：(n - 1) & hash 此时n为数组的长度，hash为以上列出的hashCode值，由此算法算得上面的所有数据都会得到相同的索引：00000000000000000000000000011111，发生了严重的hash碰撞，所有的值都落在了同一个索引（链表或红黑树）上，这无疑会大大的增加了查询和插入的时间复杂度（O（n））

 而native hashcode的计算方式导致hash值的差异主要是在高位，而(n - 1) & hash 的算法是忽略了高位，所以上述情况很容易发生。
 现在我们再来看这段HashMap针对这种情况给出的解决方案：key.hashCode()) ^ (h >>> 16);，这实际上是一个高低位混合运算，为了让key值的hashCode变得更加的均匀，现在我们重新对以上数据hashCode进行运算：
hashCode值11110000001111110000000000111111，先对此值做无符号右移（>>>）得到值00000000000000001111000000111111，然后两个值进行异或运算（^）得到值11110000001111111111000000000000，以此类推分别得到值：

• 11110000001111111111000000000000
• 11110000001100111111000000001100
• 11000000001101111100000000001000
• 11000000001101101100000011001001
  以上数据再进行索引hash都会得到不同的值，这样就让数据较为均匀的散落在了map数组上了。一行短短的代码，让HashMap能够拥有更强的场景适应性，和更高效的操作性能，这才是我们应该仔细去思考和学习的地方。

---

最轻松的扩容

再来看第二个问题

为什么HashMap的长度是2的n次幂，扩容是2倍扩容，而ArrayList扩容却是1.5倍？

 对于HashMap的长度是2的n次幂，这个很好理解，跟上面是同样的原因，为了避免hash碰撞。例如数组长度为0b100000，n - 1为0b011111,这样与key值进行&运算就能尽量保证不同的值分布在集合不同的位置上，避免了hash碰撞。

找到map数组扩容的源码：

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}

 从这里newCap = oldCap << 1我们可以看到，map数组的扩容采用了左移运算(<<)，由于数组的初始长度为2的n次幂，所以每次左移相当于进行了2倍的扩容，这样也保证了数组长度始终为2的n次幂。
 我们知道，计算机只能识别二进制代码，所以位运算是最快的，由此也能部分解释为什么要进行2倍扩容，因为只需要一次简单的移位操作，但是这些都不是关键。

我们知道，在数组扩容之后，接下来就会进行rehash操作，看源码：

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 { // preserve order
                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;
                }
            }
        }
    }
}

 阅读上面代码后我们了解到，假设扩容前数组长度为2ⁿ，在rehash时，当key的hash值在第n + 1位上为0时，元素的位置不会发生变化，当key的hash值在第n + 1位上为1时，则向后移动2ⁿ步长。这样的规律使得链表/红黑树能够一次性构造完成并赋值，避免了rehash的查询操作，性能上大大的提高了。而且这种固定步长的迁移，也能够尽量保证hash散列的均匀，避免rehash导致的hash碰撞。
 ArrayList的扩容因为只是简单的ArrayCopy，所以为了节省内存开销，设计成了1.5倍的扩容方式。

 写得有点累，先写这么多。写这些其实是为了提醒自己，在阅读优秀的源码时，我们应该注重里面的算法思路和设计模式。多思考借鉴，才能写出更优秀的代码。

注：以上所有内容来自个人理解，如有偏差，无须在意。