共计 1867 个字符，预计需要花费 5 分钟才能阅读完成。
详细的源码分析：图解 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 为 nullhash 值为 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 是线程不安全的。
