HashMap&LinkedHashMap 原理总结
详细的源码分析： 图解HashMap原理 、 图解LinkedHashMap原理
HashMap 原理
- 存储了 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 原理
LinkedHashMap 继承 HashMap ，基本原理和流程是相同的，只不过在 HashMap 的基础上添加了双向链表来保证数据的顺序。
LinkedHashMap 与 HashMap 的区别：
- 存储对象 Entry 添加了 before 和 after 的指向 Entery
- 在初始化 LinkedHashMap 的时候，会创建一个头结点的双向链表，before 和 after 都指向自己
- put 方法，把元素加入 HashMap 的同时，也要加入双向链表。
- 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 是线程不安全的。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
