1、HashMap 简介

HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在。JDK1.8 版本中其数据结构是：数组+链表+红黑树的形式。下面详解源码及解决的问题。

2、HashMap 类

public class HashMap<K,V> extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable 

接口方法：

• put 方法(新增 )

• resize 方法(扩容 )

• get 方法(遍历)

• remove 方法(删除)

• treeifyBin 方法(链表树化)

• untreeify 方法(红黑树转链)

成员变量：

• table 变量：HashMap 的底层是 Node 类的实体数组，Node 是一个静态内部类，一种数组和链表相结合的复合结构，用于保存 key-value 对；

• size 变量：表示已存储的 HashMap 的 key-value 对的数量；

• loadFactor 变量：装载因子，默认值为 0.75f（DEFAULT_LOAD_FACTOR = 0.75f;）；

• threshold 变量：临界值，超过此值 hashmap 自动扩容，threshold＝容量*加载因子；

• capacity：容量，非成员变量，默认值是 16；

3、HashMap 方法详解

1.put 方法源码及总结

put

总结：

• 判断 HashMap 中的数组是否为空或者大小为 0，如果是则初始化数组。

• 如果该 hash 值对应的数组中的位置为空，则将该数据组成的节点直接插入到该位置中。

• 如果数组对应位置数据不为空，判断该位置节点的 key 与要插入的 key 是否相等，如果是设置 e（局部变量）等于该节点。

• 如果 Node 结构为树结构，则遍历树结构找到 key 对应的节点，设置为 e。

• 如果 Node 结构为链表，遍历链表，如果链表中没有找到对应的 key,将数据构造成 Node 节点插入链表最后，如果链表长度大于等于 8，则将结构转为树。

• 如果在链表中找到对应的 key,则将该节点设置为 e.

• 如果 e（上面遍历找到的节点）不为 null,则设置新的 value，返回旧的 value.

• 如果 e 为 null，说明是新增，HashMap 大小加一，判断是否大于阈值，如果大于，则扩容。

2.get 方法源码及总结

get

总结：

• 根据 key 的 hash 值找到数组中对应的位置。

• 判断该位置上的值和要查找的值是否相等（==或者 equals），如果是则返回

• 如果不是则判断该节点的下一个节点是否为空，为空则返回 null。

• 判断结构是否是红黑树，如果是，遍历树。

• 如果不是树，则遍历链表。

• 如果不符合上面的条件则返回 null。

3.resize（扩容）方法源码及总结

总结：

• 数组是否已经达到最大值，如果已经最大，设置阈值也为最大值，否则数组大小和阈值都改为之前的两倍。

• 数组是否已经初始化，如果没有则初始化数组和阈值。

• 旧数组不为 null，遍历旧数组，将对应位置的链表/树分为成两个链表/数组，一个在原先的位置上，一个在原先的位置+原先数组大小的位置上，将两个链表/树放入新数组的对应位置。

jdk1.8 的优化

由 JDK1.7 的，数组 + 链表

JDK1.8 变为：数组 + 链表 + 红黑树

具体触发条件为：某个链表连接的个数大于 8，并且总的容量大于 64 的时候，那么会把原来的链表转换成红黑树。这么做的好处是什么：红黑树除了添加元素外，查询和删除效率比链表快。

红黑树查询、增加和删除的时间复杂度：O(log2n)

链表的查询和删除的时间复杂度： O(n)，插入为：O(1)