HashMap&LinkedHashMap 原理总结

详细的源码分析: 图解HashMap原理 、 图解LinkedHashMap原理

HashMap 原理

HashMap&LinkedHashMap 原理总结

  • 存储了 N 条单项链表的数组
  • 通过横向的单向链表解决 Hash 冲突
  • initialCapacity 是 HashMap 的初始化容量(即初始化table时用到),默认为16。loadFactor 为负载因子,默认为0.75。threshold 是HashMap 进行扩容的阀值,当 HashMap 的存放的元素个数超过该值时,会进行扩容,它的值为 HashMap 的容量乘以负载因子。比如,HashMap 的默认阀值为16*0.75,即12。
  • HashMap 提供了指定 HashMap 初始容量和负载因子的构造函数,这时候会首先找到第一个大于等于 initialCapacity 的2的平方数(充分利用 table 的奇数坐标位),用于作为初始化table。(所以,initialCapacity一定为2的幂)

put 流程

  • 通过 key 值获得 hash 值
  • 通过 hash 值和 HashMap 的容量,算出该值应该存放在 table 中的位置 index。 [index 算法:hash & (length-1) 相当于 hash % (length-1) 取余]
  • 获取 table[index] 的单向链表,轮训判断是否已经存在 key 与 hash 值相同的 Entry。如果存在则替换该 Entry 的 value 值。
  • 如果不存在,则取出 table[index] 的值 oldEntry,将 put 的 Entry 放入 table[i],新的 Entry 的 next 指向 oldEntry。即,将 put 的值放在表头。

扩容流程

  • 创建一个新 table 数组,容量为扩容之后的大小。
  • 遍历 老table 中的数据,重新计算 hash 值,利用新容量重新计算 每个Entry 在新 table 中的位置。
  • 重新计算阈值

get 流程

  • 通过 key 值获得 hash 值
  • 通过 hash 值和 HashMap 的容量,算出该值在 table 中的位置 index。
  • 获取 table[index] 的单向链表,轮训判断是否存在相同 key 值的 Entry。如果存在获取 Entry 的 value 值。不存在返回 null。

key 为 null

hash 值为0,即 table[0] 的 Entry。因为 key 值不能相同,所以 table[0] 只有一个值。

remove 流程

  • 通过 key 值获得 hash 值
  • 通过 hash 值和 HashMap 的容量,算出该值在 table 中的位置 index
  • 轮训 table[index] 的单向链表。如果是表头的位置:table[index]=next,把该结点的 next 结点放到头结点;非表头的位置:pre.next=next,把上一个结点的 next 指向本结点的 next

HashMap 总结

  • HashMap存储数据是无序的
  • HashMap不支持存储多个相同的key,且只保存一个key为null的值,多个会覆盖
  • HashMap是线程不安全的,如果有线程安全需求,推荐使用ConcurrentHashMap

LinkedHashMap 原理

HashMap&LinkedHashMap 原理总结

LinkedHashMap 继承 HashMap ,基本原理和流程是相同的,只不过在 HashMap 的基础上添加了双向链表来保证数据的顺序。

LinkedHashMap 与 HashMap 的区别:

  • 存储对象 Entry 添加了 before 和 after 的指向 Entery
  • 在初始化 LinkedHashMap 的时候,会创建一个头结点的双向链表,before 和 after 都指向自己

HashMap&LinkedHashMap 原理总结

  • put 方法,把元素加入 HashMap 的同时,也要加入双向链表。

HashMap&LinkedHashMap 原理总结

  • remove 在 table 中删除,同时在双向链表中删除,即断开 after 与 before 对其的引用。
  • 扩容,LinkedHashMap 的效率高于 HashMap。因为 LinkedHashMap 通过双向链表遍历,遍历到 Header 为止。而 HashMap 是先遍历 table 再遍历 table 中的单向链表。所以,LinkedHashMap 的遍历次数小于 HashMap 的遍历次数。
  • LnkedHashMap 存储数据是有序的,而且分为两种:插入顺序和访问顺序。默认为插入顺序(put 的顺序)。accessOrder 为 true 时为访问顺序(put 和 get 操作已存在的 Entry 时,先从双向链表中删除,再插入链表尾。其实它在 table 中的位置不变,只是改变了它在双向链表中的位置)。

LinkedHashMap 总结

  • LinkedHashMap 有序,可分为插入顺序和访问顺序两种。如果是访问顺序,那 put 和 get 操作已存在的 Entry 时,都会把 Entry 移动到双向链表的表尾(其实是先删除再插入)。
  • LinkedHashMap 是线程不安全的。

原文 

https://segmentfault.com/a/1190000018899644

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap&LinkedHashMap 原理总结

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址