前言
首先推荐一个特别好的git仓库：https://github.com/wupeixuan/JDKSourceCode1.8
有比较详细的中文注释，大家可以git下来或者fork到自己的仓库仔细研读。
正文
在解读List源码之前，需要对数据结构中的数组、链表、哈希表有一定的认识。
如有需要，可以参考本人的博客：
【数据结构与算法】数组
【数据结构与算法】链表
【数据结构与算法】哈希表
HashMap简介
- HashMap是常用的Java集合之一，是基于哈希表的Map接口的实现。
- HashMap是线程不安全的。
- 如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
- 在JDK1.6中，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。
- 而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值8且元素数量超过64时，会将链表转换为红黑树，这样大大减少了查找时间。
- 原本Map.Entry接口的实现类Entry改名为了Node。转化为红黑树时改用另一种实现TreeNode。
HashMap关键属性
/**
* 默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认装填因子0.75，如果当前键值对个数 >= HashMap最大容量*装填因子，进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* JDK1.8 新加，Entry链表最大长度，当桶中节点数目大于该长度时，将链表转成红黑树存储；
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* JDK1.8 新加，当桶中节点数小于该长度，将红黑树转为链表存储；
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶可能被转化为树形结构的最小容量。当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突。
* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap的构造方法
无参构造方法
- 使用指定的初始化容量（16）和默认的加载因子，上面的DEFAULT_LOAD_FACTOR （0.75）构造一个空HashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
指定初始容量和加载因子的构造方法
- 使用指定的初始化容量initial capacity 和加载因子load factor构造一个空HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
指定初始容量的构造方法
- 使用指定的初始化容量initial capacity和默认加载因子DEFAULT_LOAD_FACTOR（0.75）构造一个空HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
指定一个旧Map的构造方法
- 使用指定Map m构造新的HashMap。使用默认的初始化容量（16）和默认加载因子DEFAULT_LOAD_FACTOR（0.75）
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
//如果参数map不为空
if (s > 0) {
// 判断table是否已经初始化
if (table == null) { // pre-size
// 未初始化，s为m的实际元素个数
float ft = ((float) s / loadFactor) + 1.0F;
int t = ((ft < (float) MAXIMUM_CAPACITY) ?
(int) ft : MAXIMUM_CAPACITY);
// 计算得到的t大于阈值，则初始化阈值
if (t > threshold)
//根据容量初始化临界值
threshold = tableSizeFor(t);
// 已初始化，并且m元素个数大于阈值，进行扩容处理
} else if (s > threshold)
//扩容处理
resize();
// 将m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
Hash Put方法（重点）
- 将指定参数key和指定参数value插入map中，如果key已经存在，那就替换key对应的value
- 通过hash(Object key)方法计算key的哈希值。
- 通过putVal(hash(key), key, value, false, true)方法实现put功能。
- 返回putVal方法返回的结果。
public V put(K key, V value) {
// 倒数第二个参数false：表示允许旧值替换
// 最后一个参数true：表示HashMap不处于创建模式
return putVal(hash(key), key, value, false, true);
}
可以看出，put的重点在于putVal方法，源码如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
//如果哈希表为空，调用resize()创建一个哈希表，并用变量n记录哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定参数hash在表中没有对应的桶，即为没有碰撞
* Hash函数，(n - 1) & hash 计算key将被放置的槽位
* (n - 1) & hash 本质上是hash % n，位运算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接将键值对插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中已经存在元素
Node<K, V> e;
K k;
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// 当前桶中无该键值对，且桶是红黑树结构，按照红黑树结构插入
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 当前桶中无该键值对，且桶是链表结构，按照链表结构插入到尾部
else {
for (int binCount = 0; ; ++binCount) {
// 遍历到链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 检查链表长度是否达到阈值，达到将该槽位节点组织形式转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 链表节点的<key, value>与put操作<key, value>相同时，不做重复操作，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到或新建一个key和hashCode与插入元素相等的键值对，进行put操作
if (e != null) { // existing mapping for key
// 记录e的value
V oldValue = e.value;
/**
* onlyIfAbsent为false或旧值为null时，允许替换旧值
* 否则无需替换
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 更新结构化修改信息
++modCount;
// 键值对数目超过阈值时，进行rehash
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
putVal的实现逻辑：
- 如果哈希表（table，哈希桶数组）为空，调用resize()创建一个哈希表。
- 如果指定参数hash在表中没有对应的桶（链表或红黑树），即为没有碰撞，直接将键值对插入到哈希表中即可。
- 如果有碰撞，遍历桶，找到key映射的节点
- 桶中的第一个节点就匹配了，将桶中的第一个节点记录起来。
- 如果桶中的第一个节点没有匹配，且桶中结构为红黑树，则调用红黑树对应的方法插入键值对。
- 如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于等于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。
- 注意，转换为红黑树不仅要链表长度大于TREEIFY_THRESHOLD（8），且哈希表的长度必须得大于MIN_TREEIFY_CAPACITY（64），否则当只满足第一个条件时，会使用扩容的方法来减少哈希冲突避免转换为红黑树
- 如果找到了key映射的节点，且节点不为null
- 记录节点的vlaue。
- 如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换。
- 返回记录下来的节点的value。
- 如果没有找到key映射的节点（2、3步中讲了，这种情况会插入到hashMap中），插入节点后size会加1，这时要检查size是否大于临界值threshold，如果大于会使用resize方法进行扩容。
HashMap的resize扩容方法（重点）
- 对table进行初始化或者扩容。
- 如果table为null，则对table进行初始化
- 如果对table扩容，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
- 扩容步骤：
- 计算扩容后的容量，临界值。
- 将hashMap的临界值修改为扩容后的临界值
- 根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组。
- 将旧数组的元素复制到table中。
final Node<K, V>[] resize() {
//新建oldTab数组保存扩容前的数组table
Node<K, V>[] oldTab = table;
//获取原来数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原来数组扩容的临界值
int oldThr = threshold;
int newCap, newThr = 0;
//如果扩容前的容量 > 0
if (oldCap > 0) {
//如果原来的数组长度大于最大值(2^30)
if (oldCap >= MAXIMUM_CAPACITY) {
//扩容临界值提高到正无穷
threshold = Integer.MAX_VALUE;
//无法进行扩容，返回原来的数组
return oldTab;
//如果现在容量的两倍小于MAXIMUM_CAPACITY且现在的容量大于DEFAULT_INITIAL_CAPACITY
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//临界值变为原来的2倍
newThr = oldThr << 1;
} else if (oldThr > 0) //如果旧容量 <= 0，而且旧临界值 > 0
//数组的新容量设置为老数组扩容的临界值
newCap = oldThr;
else { //如果旧容量 <= 0，且旧临界值 <= 0，新容量扩充为默认初始化容量，新临界值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
newCap = DEFAULT_INITIAL_CAPACITY;//新数组初始容量设置为默认值
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//计算默认容量下的阈值
}
// 计算新的resize上限
if (newThr == 0) {//在当上面的条件判断中，只有oldThr > 0成立时，newThr == 0
//ft为临时临界值，下面会确定这个临界值是否合法，如果合法，那就是真正的临界值
float ft = (float) newCap * loadFactor;
//当新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY，新的临界值为ft，否则为Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//将扩容后hashMap的临界值设置为newThr
threshold = newThr;
//创建新的table，初始化容量为newCap
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
//修改hashMap的table为新建的newTab
table = newTab;
//如果旧table不为空，将旧table中的元素复制到新的table中
if (oldTab != null) {
//遍历旧哈希表的每个桶，将旧哈希表中的桶复制到新的哈希表中
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
//如果旧桶不为null，使用e记录旧桶
if ((e = oldTab[j]) != null) {
//将旧桶置为null
oldTab[j] = null;
//如果旧桶中只有一个node
if (e.next == null)
//将e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置
newTab[e.hash & (newCap - 1)] = e;
//如果旧桶中的结构为红黑树
else if (e instanceof TreeNode)
//将树中的node分离
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { //如果旧桶中的结构为链表,链表重排，jdk1.8做的一系列优化
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
//遍历整个链表中的节点
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {// 原索引+oldCap
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结
HashMap是一个在Java8中以数组、链表和红黑树为基础构建的一个键值对存储数据的一个数据结构，支持快速随机访问，不支持同步，允许null作为键和值，但null键只能有一个，null值可以重复。