原创

Java中的HashMap的底层原理实现、工作原理

温馨提示:
本文最后更新于 2022年01月10日,已超过 212 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

工作原理分析

Java中的HashMap是以键值对(key-value)的形式存储元素的。HashMap需要一个hash函数,它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候,HashMap会计算key的hash值,然后把键值对存储在集合中合适的索引上。如果key已经存在了,value会被更新成新值

HashMap的一些重要的特性是它的容量(capacity),负载因子(load factor)和扩容极限(threshold resizing)

对比jdk1.7和jdk1.8版本的不同

底层数据结构不一样,1.7是数组+链表,1.8则是数组+链表+红黑树结构(当链表长度大于8,转为红黑树)。

JDK1.8中resize()方法在表为空时,创建表;在表不为空时,扩容;而JDK1.7中resize()方法负责扩容,inflateTable()负责创建表。

1.8中没有区分键为null的情况,而1.7版本中对于键为null的情况调用putForNullKey()方法。但是两个版本中如果键为null,那么调用hash()方法得到的都将是0,所以键为null的元素都始终位于哈希表table【0】中。

当1.8中的桶中元素处于链表的情况,遍历的同时最后如果没有匹配的,直接将节点添加到链表尾部;而1.7在遍历的同时没有添加数据,而是另外调用了addEntry()方法,将节点添加到链表头部。

1.7中新增节点采用头插法,1.8中新增节点采用尾插法。这也是为什么1.8不容易出现环型链表的原因。

1.7中是通过更改hashSeed值修改节点的hash值从而达到rehash时的链表分散,而1.8中键的hash值不会改变,rehash时根据(hash&oldCap)==0将链表分散。

1.8rehash时保证原链表的顺序,而1.7中rehash时有可能改变链表的顺序(头插法导致)。

在扩容的时候:1.7在插入数据之前扩容,而1.8插入数据成功之后扩容。

正文到此结束
本文目录
    Loading...