HashMap源码阅读解惑

HashMap的hash函数（1.8）

首先1.7的是四次扰动，1.8做了优化。

        简单的说就是对key做hashCode操作，然后将得到的32为散列值向右位移16位，再与hashCode做异或计算。实质上是把一个数的低16位与他的高16位做异或运算。

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

首先 h = key.hashCode()是key对象的一个hashCode，每个不同的对象其哈希值都不相同，其实底层是对象的内存地址的32位的散列值，h >>> 16的意思是将hashcode右移16位，然后高位补0，然后再与(h = key.hashCode()) 异或运算得到最终的h值。

        为什么是异或运算呢？

    当然我们知道目的是为了让h的低16位更有散列性，但为什么是异或运算就更有散列性呢？而不是与运算或者或运算呢？这里我自己证明一下为什么异或就能够得到更好散列性。

先来看一下下面的这组运算

【与运算 1&0=0, 0&0=0, 0&1=0 都等于0 1&1=1 3次0,1次1】

【或运算 1&0=1, 1&1=1, 0&1=1 都等于1 0&0=0 3次1,1次0】

【异或运算 0&0=0, 1&1=0，而另外0&1=1, 1&0=1 2次1,2次0】

 上面是将0110和0101分别进行与、或、异或三种运算得到不同的结果，我们主要来看计算的过程：

        与运算：其中1&1=1，其他三种情况1&0=0, 0&0=0, 0&1=0 都等于0，可以看到与运算的结果更多趋向于0，这种散列效果就不好了，运算结果会比较集中在小的值

        或运算：其中0&0=0，其他三种情况 1&0=1, 1&1=1, 0&1=1 都等于1，可以看到或运算的结果更多趋向于1，散列效果也不好，运算结果会比较集中在大的值

        异或运算：其中0&0=0, 1&1=0，而另外0&1=1, 1&0=1 ，可以看到异或运算结果等于1和0的概率是一样的，这种运算结果出来当然就比较分散均匀了

        总的来说，与运算的结果趋向于得到小的值，或运算的结果趋向于得到大的值，异或运算的结果大小值比较均匀分散，这就是我们想要的结果，这也解释了为什么要用异或运算，因为通过异或运算得到的h值会更加分散，进而 h & (length-1)得到的index也会更加分散，哈希冲突也就更少。

为什么使用 hash & (length - 1) 作为数组的寻址算法？

        首先我们如果把数据存在一个数组中，我们会使用数组中的值hash % length取模操作，为每个值寻找存在数组中的位置，但是这种取模的操作性能不是很好，比起位运算差远了，后来发现当数组的容是2的n次方的时候hash & (length - 1) == hash % length，所以就使用hash & (length - 1) 来替代取模运算，这样操作效率高，而且数据均匀分布，hash碰撞少。

使用hash & (length - 1) 作为寻址算法也是jdk1.8的优化。

寻址算法的优化：使用与运算替代取模，提升性能。

那为什么要用数组值的hash值的高16与它的低16做异或呢？

        首先我们的寻址算法优化了，是使用hash & (length - 1) ，假设我们不适用新的优化后的hash算法，我们就直接使用数组中的值的hashcode，不使用高16与低16做异或，因为n-1的值通常是很小的，n-1通常高16为都是0，那么这个hash的高16为和n-1做与运算，hash的高16位就不起作用了，就相当于与之与两个都是低16位的值做与预算，而我们的目的就是为了hash更加散列，很少甚至不起hash冲突。所以如果使用hash值的高16与低16做异或，让他的低16为同时保持了高低16为的特征，尽量避免了hash冲突。

HashMap的容量为什么建议是2的幂次方？

关键就在于把当前数据存放到哪一个桶中，这个算法就是取模运算。

假设：

length：HashMap的容量

hash：当前key的哈希值

取模运算为 hash % length

        但是，在计算机中，直接取模运算的效率不如位运算（&），什么是位运算？就是对于二进制数据的按位运算，1和1才得1，其他都得0，比如：1011 & 1100 = 1000

        sun公司的大牛们发现，当容量为2的n次方时，hash & (length - 1) == hash % length ，于是就在源码中做了优化，通过 hash & (length - 1) 来替代取模运算，而前提就是容量必须为2的n次方。这样做的好处在于：

1. 提高操作运算效率（位运算效率 > 取模运算效率）

2. 减少碰撞，数据均匀分布，提高HashMap查询效率

为什么可以减少碰撞？举个例子，现在两个hash分别是2和3,：

比如 length 为 9 的情况：3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；

比如 length 为 8 的情况：3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

为什么不采用AVL树或B树，B+树？

红黑树和AVL树都是最常用的平衡二叉搜索树。

但是，两者之间有些许不同：

        AVL树更加严格平衡，因此可以提供更快的査找效果。因此，对于查找密集型任务使用AVL树没毛病。 但是对于插入密集型任务，红黑树要好一些。

通常，AVL树的旋转比红黑树的旋转更难实现和调试。

红黑树更通用，再添加删除来说表现较好，AVL虽能提升一些速度但是代价太大了。

而不用B/B+树的原因：

        B和B+树主要用于数据存储在磁盘上的场景，比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖，每个结点存放一个磁盘大小的数据，这样一次可以把一个磁盘的数据读入内存，减少磁盘转动的耗时，提高效率。而红黑树多用于内存中排序，也就是内部排序。

为什么树化阈值是8？为什么树退化为链表的阈值是6？

        根据泊松分布。当我们计算的哈希冲突到了8次，概率就非常小了，可以看到当链表长度为8时候的概率为千万分之6，概率极低。所以取该值作为树化阈值。