HashMap的数据结构

时间:2022-11-24 10:17:29
即数组和链表的结合体。
HashMap底层就是一个数组结构,数组中的每一项又是一个链表。
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。只允许key有一个null值,value不限定。
初始容量为 16,负载因子为 0.75   达到12时扩容
entity:
hash
key
value

next

存放:

当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标), 如果数组该位置上已经存放有其他元素了(hash碰撞),如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

读取:
从HashMap中get元素时,首先计算key的hashCode(),找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。