HashMap中的put()和get()的实现原理

原文：HashMap中的put()和get()的实现原理

put()方法

Java 8

1. 计算 key 的 Hash 值
2. 如果节点数组是空，则初始化节点数组
3. 将 hash 值转换成数组的下标，下标位置上如果没有任何元素，就把 Node 添加到这个位置上
4. 如果说下标对应的位置上有节点，并且该节点的 hash 值、k 与传入的相对，则进行覆盖
5. 如果说下标对应的位置上是树节点，则调用树节点处理方法
6. 如果说下标对应的位置上有节点链表，则将新节点放入链表的末尾。
7. 如果链表的长度超过阀值 8，则调用 treeifyBin 方法进行扩容或者树化：如果数组的长度小于 64 则进行 resize，如果数组的长度大于 64 则将链表转为红黑树

get() 方法

Java 8

1. 先调用 k 的 hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标
2. 通过数组下标快速定位到某个位置上，如果这个位置上什么都没有，则返回 null
3. 检查第一个节点的 hash 与 k，如果相等则返回
4. 如果第一节点是树节点则按照 hash 和 k 查找树，如果相等则返回
5. 如果第一节点是链表节点则遍历，比较 hash 与 k，如果相等则返回