hashMap 源码解析

ref1: http://blog.csdn.net/fan2012huan/article/details/51097331

ref2: https://zhuanlan.zhihu.com/p/21673805

数据结构

JDK1.8中，hashMap是以数组、链表和红黑树构成的。数组上的链表长度大于8时，会转换成红黑树。

resize的巧妙之处

if ((e.hash & oldCap) == 0) {
  ...

if (loTail != null) {
  loTail.next = null;
  newTab[j] = loHead;
  } 
// 原索引+oldCap放到bucket里
if (hiTail != null) {
  hiTail.next = null;
  newTab[j + oldCap] = hiHead;
}

因为扩容时是让容量翻倍，所以原来的数组元素到了扩容后要么放在原位置j，要么放在j+oldCap。用e.hash & oldCap) == 0可以判断那一位为0还是1。那一位是0的话放在j, 1的话放在 j+oldCap。 详情见 https://zhuanlan.zhihu.com/p/21673805

hash

总结

通过让高16位于低16位异或，使得在散列的时候，即使数组长度较短(小于2^16)，在取余时，hash的生成是与hashcode的高低16位都相关的，使得不同的hashcode不那么容易散列到同一个位置。

n = table.length;
index = （n-1） & hash;

与hashtable的比较

hashtable的散列方式

可以看出，hashtable的散列方式简单暴力多了，就是先和0x7FFFFFFF(Integer中最大的正数，7的二进制是0111，F的二进制是1111，所以连起来就是0后面跟31个1)进行与运算，保证结果是个正数，再取余(否则可能会出现负数进行取余的情况)。这样更容易让不同的hashcode散列到同一个位置。

tableSizeFor

static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 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的幂的容量，它大于cap且是最接近cap的。 javascript:void(null)

一系列异或操作的作用

这段代码的意义在于让n(cap - 1)的最高位的1与它的右边的所有位都变为1。

比如n为0001xxxx时，通过转换可得到n为00011111。 如此，可以在n+1时使之变为00100000，刚好是

为何一系列异或操作能达到这个效果

见引用的博客http://blog.csdn.net/fan2012huan/article/details/51097331

为何要cap - 1

根据这段代码的作用，如果cap是2的幂，比如00010000，那么n就是00011111，那么最后得到的n是00011111，n+1便是00100000。正是2的幂。

如果不让cap-1的话，那么00010000经过转换会得到00111111，再+1后得到的是01000000，便是原来的两倍。

简单来说，

• cap-1，那么转换过程
  • 00010000 n
  • 00011111 n = cap -1
  • 00011111 n转换
  • 00100000 n+1
• 不cap-1， 转换过程
  • 00010000 n = cap
  • 00111111 n转换
  • 01000000 n+1 该段代码的详细解释看博客。