内容来自《收割Offer：互联网大厂面经》

HashMap用于存放键值对，用于非线程安全，其数据结构由数组、链表和红黑树构成。链表主要是为了解决哈希碰撞问题，而红黑树则是避免为链表长度过长而导致查询效率低的问题。HashMap数据结构如图1-27所示。

1）get方法的执行流程

（1）计算 key 的 hash 值，通过 hash & (length-1)的方式计算 key 对应的数组下标。

（2）若首节点为 nul，则返回 null。

（3）若首节点 key 与目标值相同，则直接返回 key 对应的 value。

（4）若首节点 key 与目标值不同，且首节点的下一个节点为 null，则返回nul；否则判断首节点类型，首节点类型如果是链表，则遍历查找 O(n)，如果是红黑树，则效率查找 O(logn)。

2）put方法的执行流程

（1）如果数组为空就进行第一次扩容。

（2）计算key的hash 值，通过 hash & (length - 1) 的方式计算 key 对应的数组下标。