JDK7和JDK8中HashMap版本有什么不同？

﹏ヽ暗。殇╰゛Y 2022-11-02 11:58 132阅读 0赞

HashMap**底层是数组**，称为**哈希桶**，存储结构：JDK7是数组+链表，JDK8 是数组+链表/红黑树。

**1、****链表插入方式的不同**

在1.7之前，链表元素的插入采用的是头插法，也就是说，当有新结点进来时，会在插入在链表的头部。很明显，由于不用遍历链表，这种插入方式的效率是更高的。但是1.8之后，因为当结点插入的时候，本身就要为了判断元素的个数而遍历链表（看看是否达到了树化的阈值），所以就可以搭一个顺风车，在遍历完之后，把结点插入到链表尾部，即采用的尾插法。这种方式也解决了多线程下可能引发的死锁问题。因为头插法的链表在扩容移动时，会被逆序，即后插入的先被处理，如果这个时候有另一线程进行get操作，就有可能引发死锁。

**2、****rehash的方式不同**（n为数组长度）

数组扩容了，key的下标需要重新通过哈希计算。在1.7之前，采用的是按照之前的方式全部重新计算一遍，这样很明显会比较耗费时间。而1.8之后，采用了非常巧妙的一种方式。我们发现，扩容过后，进行与运算的(n - 1)，本质上就是把最低的0位变为1而已，比如原来是(0011 1111)就会变为(0111 1111)。那么同一份hash值，经过这2个不同的(n - 1)的与运算结果，是有一些关联的。由于我们的(n-1)就是前面多了一个1，所以原来的hash值经过该运算，和原结果相比，只会有2种结果，要么原hash值对应的那个位置是上原本就算0，那么与运算的结果不变，要么原来是1，现在就发生了变化。举个例子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70][]

也就是讲，重新计算后的元素，要么就在原来的位置，要么就会在一个新位置这两种选择。而这个新位置，从进制中也可以明显得看出，就是在前面多了一个1而已，也就是在原基础上加上了2n（这里的n都是指原来的n），这个2n刚好也是原来的容量，所以说，元素新的位置，要么不变，要么就在(原位置+原容量)这个索引处。而究竟是哪一个，完全就由hash中权值为2n的这个位决定，而这位的数字，在概率上来说，也是随机的，也就是大家都是50%的概率，这样也很好得减小了hash碰撞的概率。

**3、****插入时机不同**

1.7之前是扩容后再插入新的数据，并且不会先计算插入值的哈希值，最后单独算。

1.8之后是先插入再扩容，插入的值和大家一起计算新的哈希值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70]: /images/20221024/8b31298cf2cf404a9dd548b0c8a6933f.png