jdk1.7与jdk1.8的HashMap区别详解


首先我们来谈谈HashMap,从字面上来看,HashMap的名字中带有hash,我们就可以联想到HashMap的存储方式可能与hash有关。

下面我们来谈谈HashMap的存储机制:

HashMap是以键值对的形式存储数据的,其底层存储是以数组+链表的方式实现的(jdk1.8之后又引入了红黑树)。

首先我们可想象一个数组,这个数组的默认大小是16(因为在创建一个HashMap对象时,如果不指定其长度,那么底层将会默认创建一个有16个大小的数组)。

HashMap在存入一个数据时,会先去调用对象的hashCode方法计算出该对象应该放在之前创建的数组的哪个位置(即数组的索引值),若该位置为空,则直接将该对象存进去,若该位置有值,在去调用对象的equals方法比较两个key的值是否相等,如果相等则覆盖掉value的值,如果不相等,则在数组该索引处将旧值后移并将新值插入,形成一个链表(这是jdk1.7及以前的方式)。

上述方式存在一个问题,即如果多次添加数据的位置相同的话,那么这个链表就会一直增长,而且每次在链表中添加数据时都要移动链表中的数据,这样情况称之为碰撞。我们需要尽量减少这种碰撞的发生,发生碰撞,可能会增长链表,链表增长越长,碰撞的所需的时间就越多,可想是多么影响效率。

所以HashMap就引入了加载因子避免碰撞,默认为0.75,即当元素达到现有hash表的75%时扩容,一旦扩容将会重新排序hash表,减少碰撞的概率。

jdk1.8之后:

上述情况依旧不能避免形成一长串链表的可能,所以在jdk1.8之后引入了红黑树。开始的存储方式与之前相同,通过key确定存放位置,通过value判断是否覆盖或添加链表,超过阈值0.75自动扩容,但是改变的是如果链表的长度大于8,那么就会将链表转化为红黑树,但是在转变成树之前还会有一个判断,只有键值对的数量大于64才会发生转换。这是为了避免在哈希表创建初期,多个键值对恰好被放入了同一个链表中而导致的不必要的转化。


作者:砰砰的猿,发布于:2020/06/30
原文:https://www.cnblogs.com/pengpengdeyuan/p/13212736.html