想知道HashMap在Java8有哪些新变化吗?

Posted by 好记性不如烂笔头 on 03-20,2020

想知道HashMap在Java8有哪些新变化吗?

HashMap是由数组和链表组合构成的数据结构,数组里面每个地方都存了Key-Value这样的实例,也叫做键值对,在Java7叫Entry,在Java8中叫Node,也叫作“桶”。

Node类型的数组

hashmap示意图

当发生哈希碰撞时(就是哈希计算发现两个键值对要放在同一个“桶”里),此时一个Node上就会形成一个链表,java7之前是头插法,就是说新来的值会在数组位置插入,其余的元素往下推。但是,在java8之后,都是使用尾部插入了。在这之前我们先了解HashMap的扩容机制。

HashMap内部定义了一个常量,叫做负载因子,数组中最多存放的键值对数量会等于数组长度×负载因子,而HashMap的默认负载因子设定为0.75

默认负载因子

也就意味着,假设数组length为16, 当已经存放了12个键值对,在加入第13个键值对的时候,将会触发扩容!

扩容分为两步:

  1. 创建一个新的Node空数组,长度是原数组的2倍。
  2. ReHash:遍历原Node数组,把所有的Node重新Hash到新数组。

为什么不是直接复制粘贴过去,而是重新哈希呢? 是因为长度扩大以后,Hash算出来的数组下标也会变化!,HashMap是根据Key和数组长度length来计算放在数组中的位置的。具体过程是:

  1. 先获取key对象的hashcode值,然后再把这个值位运算向右移16位,然后再与原值进行异或,得到一个hash值。

获取hash值

  1. 通过(n-1)&hash获取该Node节点在table数组中的位置。hash就是上一步中获取的hash值,n是数组的长度,也就是用长度减1和hash值进行与运算(&),与运算相当于求余(%),但是在计算机中的运算效率比求余高。

节点在数组中的位置

如果原来长度是8,与运算出来的值是2 。而新的长度变为16,与运算出来的值明显就不一样了,那么放在数组中的位置扩容前后自然就不一样了,自然就不能直接复制过去到原来的位置。

回到问题,为啥之前用头插法,java8之后改成尾插了呢?

因为在多线程情况下,扩容后,头插法可能导致同一位置的链表变成环形,导致死循环,这是非常致命的。(读着可以自己思考为啥会变成环形,结合多线程和扩容时的重新哈希来考虑)

循环哈希

java8之后的尾插法不会导致环形链表,但是也不意味着线程安全!因为get和put方法都是没有加锁的,无法保证上一秒put进去的值,下一秒get的时候还是原来的值,所以线程安全还是无法保证。