在项目开发中，HashMap是及其常用的数据结构。今天，我们一起来看看它的源码实现（本文源码来自JDK 1.8）。
HashMap有如下类注释： 
从中可知：
- 基于哈希表的Map接口实现
- 允许空值和空键
- HashMap类大致相当于Hashtable，不同之处在于它是不同步的，是线程不安全的
- HashMap不保证映射的顺序
- 为基本操作(get和put)提供O(1)的性能
- 集合视图进行迭代所需的时间，与HashMap实例的容量加size成正比
- HashMap实例有两个影响其性能的参数:初始容量和负载因子
- 当哈希表中的条目数超过负载因子和当前容量的乘积时，将对哈希表进行重建，使哈希表的桶数大约增加一倍。
1 数据结构
HashMap是Map接口基于哈希表的一种实现。 
哈希表基于数组实现，元素是Entry对象。HashMap中将Entry形成链表（或者红黑树），来解决哈希冲突。 HashMap主要属性如下：
java
代码解读
复制代码
// 默认初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，2^31
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表树化时的阈值，当向entry数量为8的桶put元素时，将引起链表树化
static final int TREEIFY_THRESHOLD = 8;
// 桶取消树化时的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表
transient Node<K,V>[] table;
// 哈希表尺寸
transient int size;
// 触发下次扩容时map中的entry数，取值为capacity * load factor，
int threshold;
// 负载因子
final float loadFactor;
// 对HashMap实例的修改次数
transient int modCount;
// Entry视图
transient Set<Map.Entry<K,V>> entrySet;
1.1 负载因子
当哈希冲突严重时，键值对在哈希表中的分布将很不均匀，有些桶中没有元素，而有些桶中有很多元素；此时，查询性能将受到影响。
因此，不能等到HashMap中键值对数量，达到或超过哈希表长度时，才进行扩容。
使用loadFactor（小于1）衡量哈希表的饱和程度。要求size > capacity * load factor时，就进行扩容。通过rehash来减少哈希冲突，以保证HashMap的性能。
1.2 分离链表法
嵌套类Node<K,V>，即键值对，是单链表结构。树化时使用嵌套类TreeNode<K,V>。
树化只为提高哈希冲突严重时，在桶中查找某个key的效率。 红黑树本质是自平衡的二叉查找树。 
使用分离链表法的哈希表：
2 主要方法实现
2.1 初始化
创建HashMap时，可指定初始容量和loadFactor。如果不指定，则使用默认值。 
也可用一个Map实例来创建新Map。 
2.1.1 哈希表的尺寸
当指定initialCapacity时，会通过计算得到tableSize。HashMap中哈希表长度，要求始终是2的次方数。便于使用&与运算计算余数。
tableSize-1的二进制表示，除最高位外其余全是1；与key的hashCode做与运算，即可得到对哈希表长度的余数。 
如，tableSizeFor(12)=16，tableSizeFor(32)=32。
2.1.2 延迟创建哈希表
在HashMap的构造方法中，并没有立即初始化哈希表，而是在发生第一次put时，才创建哈希表。 
2.2 put实现
先看hashCode计算，HashMap中做了优化。 
核心逻辑在putVal()中，逻辑如下：
- 如果table为null或length为0，则初始化哈希表；
- 根据哈希值，使用与运算计算桶下标i；
- 如果桶为空，则指直接放入；
- 如果桶不为空，则在红黑树或链表中put；
- 如果桶中已存在key，则覆盖旧值，返回；
- 最后，真的新增了一个entry后，判断是否需要扩容。
注意：
- 在判断key是否已存在时，要求hash值相同，且要求equals()返回true；
- 当桶中entry是链表时，使用尾插法；
- HashMap中先执行put，后处理扩容；由于使用
size > threshold判断，不会导致无效扩容。如容量为16，负载因子为0.75，threshold=12；当插入第13个key时，才会触发扩容； afterNodeInsertion()定义了插入entry后的额外动作，是一个扩展点。- 参数
onlyIfAbsent为true时，put操作将只插入新key，不覆盖已存在的key（除非旧value为null）。
2.3 resize实现
主要逻辑如下：
- 当对HashMap第一次put时，将通过
resize()来触发哈希表的初始化。 - 先将threshold设置为触发下次扩容时的键值对总数。如当前哈希表长度为16，threshold=12；扩容后哈希表长度为32，threshold=24；
- 遍历每一个桶，将其中的键值对重新rehash。
需要注意，resize时对链表也采用尾插法。 
为什么resize能减少哈希冲突程度呢？
比如，在长度为16的哈希表中，在index=2的桶中，有key=2、18、34、82、98共5个key；
在resize后哈希表长度变为32，2、34、98将仍在index=2的桶中，而18、82会被移动到index=2+16的桶中。
从而降低了哈希桶中哈希冲突
2.4 get实现
get方法调用了getNode()，在key不存在时返回null。 
而getOrDefault()在key不存在时，可以返回给定值。 
2.5 size相关方法
实现很简单。 
2.6 contains相关方法
containsKey时间复杂度是o(1)。 
而containsValue是O(n)，与size成正比。 
2.7 树化和反树化
2.7.1 树化
只有向HashMap真的插入一个键值对时，才可能触发桶的树化。
当某个哈希桶中键值对数量大于等于7时，将尝试对链表树化：binCount即桶中entry的计数 
但是，当哈希表长度小于64时，不会树化，而是扩容。 
2.7.2 反树化
反树化实现是java.util.HashMap.TreeNode#untreeify。 
当哈希桶中键值对数量减少时，都可能触发反树化。如remove、resize等操作。
桶由树退化为链表的条件，是桶中entry数小于等于6时。 
3 总结
3.1 与JDK7比较
JDK7中，HashMap的桶不会树化，始终是链表结构。在JDK8中，HashMap引入了红黑树 
扩容差异：
- 在JDK7中，当HashMap的容量达到阈值时，才会触发扩容。
- 在JDK8中，除了容量达到阈值外，当哈希表长度小于64时，某个桶中的链表长度大于等于7时，也会触发扩容。（树化只是提高了桶中查询效率，而扩容直接削弱了哈希冲突程度，效果更好）
链表的插入方式：
- 在JDK7中，put、resize操作时，对链表使用头插法，在并发扩容时，可能形成环形数据结构，导致死循环；
- 在JDK8中采用头插法，来避免出现死循环。
3.2 注意事项
- 在设置HashMap的初始容量时，应考虑map中的键值对预期数及其负载因子，以尽量减少rehash操作的数量。
- 作为一般规则，默认负载因子(0.75)在时间和空间成本之间提供了一个很好的权衡，最好不要自己指定。
