HashMap深度分析疑问

图一.jpg

hashMap底层是基于散列算法实现，散列算法分为散列再探测和拉链式。hashmap使用了拉链式散列算法，在jdk1.8中引入了红黑树来提升性能。

怎么解决hash 冲突:hashMap通过key来计算hashCode 如果hashcode相同，通过拉链法来解决冲突。所谓的拉链法就是:将链表和数组结合，也就是说创建一个链表数组，数组每一格就是一个链表，若遇到hash冲突，则将冲突的值加入到链表当中即可

java 8 中的hashMap有什么改变，说说hashMap 的底层实现原理
变化1:java8 用数组+链表+红黑树的方式来记录键值
变化2:java8 重写了resize()方法，解决了链表循环问题
变化3:hash算法的改进.直接右移16位

底层实现和原理:
hashmap其实是一种数组+链表+红黑树的数据结构，在put操作中，通过内部定义算法寻址找到数组下标，将数据直接放入此数组元素中，若通过算法得到该数组的元素已经有元素了(即hash冲突) 就遍历链表，将新的元素放在链表的尾部，若这个链表的长度大于8，就转成红黑树。红黑树的作用，就是能够进行元素的快速查找。

用node<K,V>来存储值，当hash冲突时，node中的next就会指向链表的下一个元素。
为什么要引入红黑树:在jdk1.7时，通过hash算法寻址，能够高效的找到对应的下标，随着数据的增长，hash碰撞越来越多，在get元素的时候就原来越慢，这个时候红黑树的出现，就解救了这种情况

解析一下map put方法的流程

图二.png

在扩容resize()操作中，因无需重新计算hash值，同时均匀将链表冲突的元素均匀分布到新的数组中。这设计实在是巧妙。

• 计算键的 hash 值

只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的 hash 高4位数据与低4位数据进行异或运算，即

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

这样做有两个好处，我来简单解释一下。我们再看一下上面求余的计算图，图中的 hash 是由键的 hashCode 产生。计算余数时，由于 n 比较小，hash 4)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下