共计 5848 个字符，预计需要花费 15 分钟才能阅读完成。
前言
本文的目的是阅读理解 HashMap 的源码，作为集合中重要的一个角色，平时用到十分多的一个类，深入理解它，知其所以然很重要。本文基于 Jdk1.7，因为 Jdk1.8 改变了 HashMap 的数据结构，进行了优化，我们先从基础阅读，之后再阅读理解 Jdk1.8 的内容
HashMap 的特性
1. 通过 key-value 的形式快速的存取元素
2. 允许键为 Null，但只允许有一个键的值为 Null
3. 线程不安全
4. 底层结构是 Hash 表，元素是无序的
5. 再不考虑 Hash 冲突的时候，插入和查询的复杂度是可以达到 O（1）的
HashMap 的数据结构
底层数据结构是一个 Hash 表，基于数组和链表，数组里面保存着一个单向链表的头节点，单项链表保存着具有相同 Hash 值的不同元素，再不发生 Hash 冲突的情况下，链表应该只有一个元素，这是最理想的状态。
链表的数据结构代码
`
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next; // 下一个 Entry 对象的引用
int hash; // 其实就是 key 的 hash 值
} HashMap 的常量结构
// 默认初始化容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap 允许的最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载率 75%
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空的哈希表
static final Entry<?, ?>[] EMPTY_TABLE = {};
// 实际使用的哈希表
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
// HashMap 的大小, 即存储的 key-value 的数量
transient int size;
// 扩容的阀值，当 HashMap 的 size 达到阀值时，就开始扩容 threshold=length*threshold
int threshold;
// 负载率
final float loadFactor;
// 修改次数, 用于 fail-fast 机制
transient int modCount;
// 替代哈希使用的默认扩容阀值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
// 随机的哈希种子, 有助于减少发生哈希碰撞的几率
transient int hashSeed = 0;HashMap 的初始化
HashMap 的初始化涉及到上面的多个常量，在了解完常量的作用之后，我们就可以理解 HashMap 的初始化思想，首先，HashMap 并不是通过构造函数来初始化的，构造函数只是初始化 HashMap 的初始化参数，包括 DEFAULT_INITIAL_CAPACITY，loadFactor 等，再初始化参数之后，真正的调用 Put 方法时，会判断 table 是否已经初始化，没有的话再根据参数进行初始化。
put 方法的流程我们这边也要先理解：
（1）检查哈希表是否是个空表，如果是空表就调用 inflateTable 方法进行初始化
（2）判断 key 是否为 null，如果为 null，就调用 putForNullKey 方法, 将 key 为 null 的 key-value 存储在哈希表的第一个位置中
如果 key 不为 null，则调用 hash 方法计算 key 的 hash 值
（3）根据 hash 值和 Entry 数组的长度定位到 Entry 数组的指定槽位
（4）判断 Entry 数组指定槽位的值 e 是否为 null, 如果 e 不为 null, 则遍历 e 指向的单链表, 如果传入的 key 在单链表中已经存在了, 就进行替换操作, 否则就新建一个 Entry 并添加到单链表的表头位置
（5）如果 e 为 null, 就新建一个 Entry 并添加到指定槽位
下面是代码：
构造方法
public HashMap(int initialCapacity, float loadFactor) {
// 如果初始容量小于 0，则抛出异常
if (initialCapacity < 0) {throw new IllegalArgumentException("Illegal initial capacity:" + initialCapacity);
}
// 如果初始容量大于容量最大值，则使用最大值作为初始容量
if (initialCapacity > MAXIMUM_CAPACITY) {initialCapacity = MAXIMUM_CAPACITY;}
// 如果负载率小于等于 0 或负载率不是浮点数，则抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {throw new IllegalArgumentException("Illegal load factor:" + loadFactor);
}
// 设置负载率
this.loadFactor = loadFactor;
// 设置阀值为初始容量
threshold = initialCapacity;
// 空实现, 交由子类实现
init();}
//初始化数组方法
private void inflateTable(int toSize) {
// 寻找大于 toSize 的, 最小的,2 的 n 次方作为新的容量
int capacity = roundUpToPowerOf2(toSize);
// 阀值 = 容量 * 负载因子, 如果容量 * 负载因子 > 最大容量时, 阀值 = 最大容量
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 按新的容量创建一个新的数组
table = new Entry[capacity];
// 重新初始化 hashSeed
initHashSeedAsNeeded(capacity);
}put 方法
public V put(K key, V value) {
// 如果哈希表没有初始化就进行初始化
if (table == EMPTY_TABLE) {
// 初始化哈希表
inflateTable(threshold);
}
// 当 key 为 null 时，调用 putForNullKey 方法，保存 null 于 table 的第一个位置中，这是 HashMap 允许为 null 的原因
if (key == null) {return putForNullKey(value);
}
// 计算 key 的 hash 值
int hash = hash(key);
// 根据 key 的 hash 值和数组的长度定位到 entry 数组的指定槽位
int i = indexFor(hash, table.length);
// 获取存放位置上的 entry，如果该 entry 不为空，则遍历该 entry 所在的链表
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
// 通过 key 的 hashCode 和 equals 方法判断，key 是否存在，如果存在则用新的 value 取代旧的 value，并返回旧的 value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 修改次数增加 1
modCount++;
// 如果找不到链表 或者 遍历完链表后，发现 key 不存在，则创建一个新的 Entry，并添加到 HashMap 中
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {// 添加 key 到 table[bucketIndex]位置，新的元素总是在 table[bucketIndex]的第一个元素，原来的元素后移
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 判断元素个数是否达到了临界值，若已达到临界值则扩容，table 长度翻倍
if (size++ >= threshold)
resize(2 * table.length);
}HashMap 的查
当 key 值为 Null 的时候会进行特殊处理，在 table[0]的链表上查找 Key 为 null 的元素，get 的过程是：
（1）计算 hash 与 table.length 取模计算 index 值
（2）遍历 table[index] 上的链表，直到找到 key
void addEntry(int hash, K key, V value, int bucketIndex) {// 添加 key 到 table[bucketIndex]位置，新的元素总是在 table[bucketIndex]的第一个元素，原来的元素后移
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 判断元素个数是否达到了临界值，若已达到临界值则扩容，table 长度翻倍
if (size++ >= threshold)
resize(2 * table.length);
}#HashMap 的删
remove 方法同样也是，先计算 hash, 在计算 index，遍历查找，找到之后删除节点
/**
* 根据 key 删除元素
*/
public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e. value);
}
/**
* 根据 key 删除链表节点
*/
final Entry<K,V> removeEntryForKey(Object key) {
// 计算 key 的 hash 值
int hash = (key == null) ? 0 : hash(key.hashCode());
// 根据 hash 值计算 key 在数组的索引位置
int i = indexFor(hash, table.length);
// 找到该索引出的第一个节点
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 遍历链表（从链表第一个节点开始 next），找出相同的 key，while (e != null) {
Entry<K,V> next = e. next;
Object k;
// 如果 hash 值和 key 都相等，则认为相等
if (e.hash == hash &&
((k = e. key) == key || (key != null && key.equals(k)))) {
// 修改版本 +1
modCount++;
// 计数器减 1
size--;
// 如果第一个就是要删除的节点（第一个节点没有上一个节点，所以要分开判断）if (prev == e)
// 则将下一个节点放到 table[i]位置（要删除的节点被覆盖）table[i] = next;
else
// 否则将上一个节点的 next 指向当要删除节点下一个（要删除节点被忽略，没有指向了）prev. next = next;
e.recordRemoval(this);
// 返回删除的节点内容
return e;
}
// 保存当前节点为下次循环的上一个节点
prev = e;
// 下次循环
e = next;
}
return e;
}HashMap 的扩容
resize 扩容是 HashMap 中非常重要的一个操作，在容器里的元素达到一个临界值时，HashMap 会自动进行扩容，扩容的具体流程是；
1. 在 put 的时候检查是否需要扩容，根据两个参数：初始容量和装载因子
2. 创建一个容量为 table.length* 2 的 table，修改临界值
3. 重新计算所有元素的 hash 值，并放入新的 table，使用的是 头插法
4. 用新的 table 替换旧的 table
void resize(int newCapacity) {Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {// 最大容量为 1 << 30
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];// 新建一个新表
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;// 是否再 hash
transfer(newTable, rehash);// 完成旧表到新表的转移
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
---------------------
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {// 遍历同桶数组中的每一个桶
while(null != e) {// 顺序遍历某个桶的外挂链表
Entry<K,V> next = e.next;// 引用 next
if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);// 找到新表的桶位置; 原桶数组中的某个桶上的同一链表中的 Entry 此刻可能被分散到不同的桶中去了，有效的缓解了哈希冲突。e.next = newTable[i];// 头插法插入新表中
newTable[i] = e;
e = next;
}
}
}扩容的整体操作如上，但是有一些十分精妙的细节十分厉害
为什么扩容的容量一定是 2 的幂？
这么设计当然是为了性能，而且是十分显著的性能提升，涉及到了位操作，我觉得非常有意思，会在下一篇专门讲这样计算进行提升性能的例子。
