HashMap实现原理

HashMap的主干是一个Entry数组,Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。

transient Entry[] table = (Entry[]) EMPTY_TABLE;

HashMap的整体结构如下


简单来说,HashMap是由数组和链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的。

HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象多了,就有可能不同的对象计算出来的hash值是相同的,这就出现了所谓的hash冲突。

HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。

存储数据put方法

HashMap存放数据的时候,会先拿到key的hashCode值,对其进行hash运算,得到具体的hash值,然后根据hash值查找存放的位置,找到存放的位置后,然后遍历Entry数组找到对应的位置的Entry,如果当前的key已经存在,且对比Entry的hash值和key的相同的话,那么就更新value值,否则就将key和value值加到数组中。

这里需要注意
e.key == key || e.key.equals(key)
并且
e.hash == hash(key对应的hash值)

HashMap的get方法

首先拿到key的hashCode,求出hash值,根据hash值找到索引的位置,然后去Entry数组中获取对应索引的元素,如果key值相同并且key的hash相同,那就是我们要找的Entry,把对应的Entry值返回去即可。

参考文章