本文章已授权微信公众号郭霖（guolin_blog）转载。
本文章讲解的内容是Android中的HashMap源码分析。
本文章分析的HashMap源码是基于Android SDK（版本为28）。
要注意的是，Android SDK 28和JDK 1.8对HashMap的底层实现进行了优化，例如：引入了红黑树的数据结构和扩容的优化等。
概述
HashMap的UML类图如下所示：
AUMLClassDiagramForAHashMap.png
HashMap是基于哈希表实现的Map接口。此实现提供了所有可选的映射操作，并且允许空键和空值，要注意的是，最多允许一条记录的键是空，允许多条记录的值是空。它不保证映射的顺序随着时间保持不变。
HashMap为基本操作（get和put）提供了恒定时间的性能，假设哈希函数将元素正确地分散在桶（bucket）中。对集合视图的迭代需要的时间与HashMap实例的容量（桶的数量）加上它的大小（键值映射的数量）成正比。如果对迭代的性能有要求的话，就不要将初始容量（initial capacity）设置得太高（或者负荷系数（load factor）太低。
HashMap实例有两个影响其性能的参数：初始容量（initial capacity）和负荷系数（load factor）。容量是哈希表中的桶数，初始容量就是创建哈希表时的容量。负荷系数是一种度量方法，用来衡量在自动增加哈希表的容量之前，哈希表允许达到的满度。当哈希表中的条目数量超过当前容量和负荷系数的乘积时，哈希表将被重新散列（即重新构建内部数据结构），也就是扩容，这样哈希表的桶数大约是原来的两倍。
通常，默认的负荷系数（0.75）在时间和空间成本之间提供了一个很好的权衡，在大部分下情况下，不建议修改该值。如果设为较高的值，可以减少空间开销，但是会增加查找成本（反映在HashMap类的大多数操作中，包括get方法和put方法）。threshold是HashMap所能容纳的最大数据量的节点（Node）个数，在设置初始容量时，应该考虑映射中的最大条目数及其负荷系数，以便减少扩容的次数。如果初始容量大于threshold除以负荷系数，则不会发生重新散列操作，也就是不会发生扩容。
如果要在一个HashMap实例中存储许多映射，那么以足够大的容量创建它将比根据需要让映射执行自动重新散列以增长表更有效地存储映射。要注意的是，在同一个哈希码（HashCode）使用多个键肯定会降低任何散列表的性能。为了改善影响，当键是可比较时，这个类可以使用键之间的比较顺序。
要注意的是，HashMap是线程不安全的。如果多个线程并发地访问一个HashMap，并且至少一个线程对它做了结构修改（结构修改是指添加或者删除一个或者多个映射，仅仅改变与实例已经包含的键相关联的值不是结构修改），那么它必须在外部同步，可以使用Collections的synchronizedMap来使HashMap具备线程安全的能力，或者使用ConcurrentHashMap。
HashMap这个类的所有集合视图方法返回的迭代器都是快速失败的：如果在迭代器创建后的任何时候映射结构被修改，除了通过迭代器自己的remove方法外，通过任何方式，迭代器都会抛出ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在未来一个不确定的时间冒任意的、不确定的行为。
要注意的是，迭代器的快速失败行为不能得到保证，因为一般来说，在存在非同步并发修改时不可能做出任何硬性保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此，如果要编写一个依赖于这个异常来保证其正确性的程序，那将是错误的，迭代器的快速失败行为应该仅用于检测错误。
源码分析
下面对HashMap进行源码分析：
字段和节点（Node）
HashMap的字段，源码如下所示：
// HashMap.java
// 序列化版本号
private static final long serialVersionUID = 362498820763181265L;
// 默认初始容量（必须是2的幂），它的值是1左移4位，也就是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，如果任何一个带参数的构造函数隐式指定了较大的值，就会使用它来比较，而且值必须是2的幂，并且小于1左移30位，也就是1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
// 在构造函数中未指定时使用的负荷系数，它的值是0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 为容器使用树而不是列表时的容器计数阈值，当向至少有这么多节点的bin中添加一个元素时，bin被转换成树，该值必须大于2，并且至少应该是8，以符合在树移除时关于在收缩时转换成普通箱的假设
static final int TREEIFY_THRESHOLD = 8;
// 在调整大小操作期间取消查询（拆分）存储箱的箱计数阈值，应小于TREEIFY_THRESHOLD，且最多为6，以便在去除时检测到收缩
static final int UNTREEIFY_THRESHOLD = 6;
// 容器变成树的最小表容量（否则，如果容器中有太多节点，就会调整表的大小），它的值是64，应该至少是4乘以TREEIFY_THRESHOLD，以避免调整大小和树调整阈值之间的冲突
static final int MIN_TREEIFY_CAPACITY = 64;
// 表，在第一次使用时初始化，并根据需要调整大小，分配时，长度总是2的幂（在某些操作中，我们也允许长度为零，以允许当前不需要的引导机制）
transient Node<K,V>[] table;
// 保存entrySet方法的缓存，要注意的是，AbstractMap的字段用于keySet方法和values方法
transient Set<Map.Entry<K,V>> entrySet;
// 此映射中包含的键值映射的数目
transient int size;
// 此字段用于使HashMap的集合视图上的迭代器快速失败，结构修改是指那些改变HashMap中映射数量或者修改其内部结构的修改（例如：重新散列）
transient int modCount;
// HashMap所能容纳的最大数据量的节点个数，调整大小的下一个大小值（容量乘以装载系数），也就是所能容纳的节点极限，Java文档描述在序列化时是正确的，另外，如果没有分配表数组，则该字段保存初始数组容量，或者表示DEFAULT_INITIAL_CAPACITY的值为零
int threshold;
// 哈希表的负荷系数
final float loadFactor;
这里有个很重要的字段table数组，类型是Node<K,V>[]，也就是哈希桶数组，table数组的初始长度是16，负荷系数（load factor）默认值是0.75f，threshold是HashMap所能容纳的最大数据量的节点（Node）个数，有如下公式：threshold = loadFactor * length，loadFactor是负荷系数，length是数组长度，也就是数组在定义好长度后，负荷系数越大，所能容量的节点就越多，前面也提到了，当节点个数超过这个数值时，HashMap就会扩容，扩容后的容量是原来的两倍
table数组的长度（length）必须是2的幂，也就是说一定是个合数，这是一种非常规的设计，常规的设计是把桶的大小设计成质数（素数），相对来说质数导致冲突的概率是小于合数，举个例子：
设有一个哈希函数为H(x) = x % n;，也就是做取模运算，当n取一个合数时，例如取2的幂，譬如取2的3次方，也就是8，例子如下所示，基本数据类型是int，也就是位数是32位：
4（十进制） = 00000000 00000000 00000000 00000100（二进制）
12（十进制） = 00000000 0000000 0000000 00001100（二进制）
20（十进制） = 00000000 00000000 00000000 00010100（二进制）
28（十进制） = 00000000 00000000 00000000 00011100（二进制）
调用哈希函数H(x)：
H(4) = 4 % 8 = 4
H(12) = 12 % 8 = 4
H(20) = 20 % 8 = 4
H(28) = 28 % 8 = 4
我们可以发现无论第四位（从右向左数）取什么值，哈希函数H(x)的值都一样，也就是从第四位左方向的位数都不参与哈希函数H(x)的运算，这就无法反应x的特性，从而增大冲突的几率，也就是说取合数会增大冲突的几率。
我们可以试下取质数，譬如取3，分别用前面提到的4、12、20和28去调用哈希函数H(x)：
H(4) = 4 % 3 = 1
H(12) = 12 % 3 = 0
H(20) = 20 % 3 = 2
H(28) = 28 % 3 = 4
我们可以发现哈希函数H(x)的值都不一样，也就是说取质数可以减少冲突的几率。
桶的大小设计为质数的例子就是Hashtable，它的初始桶大小是11，不过扩容后就不能保证还是素数了。HashMap采用这种这种非常规的设计主要目的是为了优化取模和扩容，同时为了减少冲突，HashMap在确定哈希桶索引的位置时，加入了高位参与运算。
我们看下静态内部类Node的源码，源码如下所示：
// HashMap.java
static class Node<K,V> implements Map.Entry<K,V> {
// 定位数组索引位置
final int hash;
// 键
final K key;
// 值
V value;
// 链表的下一个节点
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// 判断key和value是否都相等
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
// 如果key和value都相等，就返回true
return true;
}
// 如果key或者value不相等，就返回false
return false;
}
}
Node是HashMap的静态内部类，实现了Map.Entry<K,V>接口，本质上就是一个映射（键值对）。
HashMap使用哈希表存储数据。哈希表可以使用四种方式来解决哈希冲突，后面的题外话会有详细讲解，HashMap是使用链地址法来解决哈希冲突的，简单来说，就是数组和链表的结合，每个数组元素都是一个链表结构，首先调用key的hashCode方法得到哈希值（该方法适用于每个Java对象），然后再通过哈希算法的后两步运算（高位运算、取模运算）来定位该键值对对应的存储位置，如果两个key定位到相同的存储位置，表示发生了哈希碰撞，哈希算法的计算结果越分散均匀，哈希碰撞的几率就越低，Map的存取效率就越高。
如果哈希桶数组很大，即使较差的哈希算法计算结果相对来说比较分散均匀，出现哈希碰撞的几率也相对来说比较低；如果哈希桶数组很小，即使较好的哈希算法计算结果相对来说不够分散均匀，出现哈希碰撞的几率也相对来说比较高，所以这需要在时间成本和空间成本之间权衡，可以通过好的哈希算法和扩容机制来达到哈希桶数组占用空间少，同时出现哈希碰撞的几率也低。
构造方法
HashMap的构造方法，源码如下所示：
// HashMap.java
// 构造一个具有指定初始容量和负荷系数的空HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
// 如果指定初始容量小于0，就抛出IllegalArgumentException异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
// 如果指定初始容量大于最大容量，就取最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
// 如果负荷系数小于等于0或者不是单精度浮点数（float）就抛出IllegalArgumentException异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 将指定负荷系数赋值给成员变量loadFactor
this.loadFactor = loadFactor;
// 调用tableSizeFor方法，并且传入指定初始容量，把得到的值赋值给成员变量threshold
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
// 调用前面的方法，并且传入指定初始容量和默认的负荷系数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
// 将默认的负荷系数赋值给成员变量loadFactor，所有其他字段都是默认值
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
// 将默认的负荷系数赋值给成员变量loadFactor
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 调用putMapEntries方法，这个方法在调用putAll方法时也会调用
putMapEntries(m, false);
}
我们看下tableSizeFor方法，这个方法是返回给定目标容量的2的幂，源码如下所示：
// HashMap.java
// 返回给定目标容量的2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1; // 第一步：首先把传入的给定目标容量减1，然后赋值给n
n |= n >>> 1; // 第二步：首先n的补码无符号右移1位，然后与原来的n的补码执行或运算，最后赋值给n
n |= n >>> 2; // 第三步：首先n的补码无符号右移2位，然后与原来的n的补码执行或运算，最后赋值给n
n |= n >>> 4; // 第四步：首先n的补码无符号右移4位，然后与原来的n的补码执行或运算，最后赋值给n
n |= n >>> 8; // 第五步：首先n的补码无符号右移8位，然后与原来的n的补码执行或运算，最后赋值给n
n |= n >>> 16; // 第六步：首先n的补码无符号右移16位，然后与原来的n的补码执行或运算，最后赋值给n
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // 第七步：判断n是否小于0，如果小于0，就返回1；如果大于等于0，就判断n是否大于等于最大容量1073741824，如果大于等于最大容量，就返回最大容量；如果小于最大容量，就返回n加1
}
我们假设传入的cap的值是30，首先执行第一步，n的值就是29，29是正数，所以它的补码和原码一样，补码如下所示：
00000000 00000000 00000000 00011101
执行第二步，首先29的补码无符号右移1位，补码如下所示：
00000000 00000000 00000000 00001110
然后与第一步的补码执行或运算，补码如下所示，转成十进制是31：
00000000 00000000 00000000 00011111
执行第三步，首先31的补码无符号右移2位，补码如下所示：
00000000 00000000 00000000 00000111
然后与第二步的补码执行或运算，补码如下所示，转成十进制是31：
00000000 00000000 00000000 00011111
执行第四步，首先31的补码无符号右移4位，补码如下所示：
00000000 00000000 00000000 00000001
然后与第三步的补码执行或运算，补码如下所示，转成十进制是31：
00000000 00000000 00000000 00011111
执行第五步，首先31的补码无符号右移8位，补码如下所示：
00000000 00000000 00000000 00000000
然后与第四步的补码执行或运算，补码如下所示，转成十进制是31：
00000000 00000000 00000000 00011111
执行第六步，首先31的补码无符号右移16位，补码如下所示：
00000000 00000000 00000000 00000000
然后与第五步的补码执行或运算，补码如下所示，转成十进制是31：
00000000 00000000 00000000 00011111
执行第七步，31大于0，并且小于最大容量1073741824，所以执行如下逻辑：
31 + 1 = 32
最后返回的值就是32，它是2的幂，也就是2的5次幂。
添加
HashMap的添加方法，源码如下所示：
// HashMap.java
// 添加一个Map到HashMap，HashMap的构造函数和putAll方法都有调用这个方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
// 调用tableSizeFor方法，返回t的2的幂，并且赋值给成员变量threshold
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
// 遍历Map
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 调用putVal方法
putVal(hash(key), key, value, false, evict);
}
}
}
// 将这个HashMap中指定的键和指定的值关联，如果它之前就存在相同的键，那么就把用新值去替换它的旧值
public V put(K key, V value) {
// 调用putVal方法，这里有一个很重要的方法：hash方法，后面会详细讲解
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 如果table数组还没初始化，就调用resize方法初始化数组
n = (tab = resize()).length;
// 根据key计算出来的哈希值进行取模运算，得到要插入的元素的索引，后面会详细讲解
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果该索引所在的元素数据是空，就创建一个节点，并且把数据传进去
tab[i] = newNode(hash, key, value, null);
else {
// 如果该索引所在的元素数据不是空的，也就是发生了哈希碰撞，就执行以下逻辑
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果该索引的元素的key和要插入的元素的key是相同的，就赋值给e
e = p;
else if (p instanceof TreeNode)
// 如果该索引的元素的数据结构是树，就调用putTreeVal方法，使用红黑树插入数据，并且赋值给e
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)
// 如果binCount大于等于TREEIFY_THRESHOLD减1，也就是binCount大于等于7，链表的长度大于等于8，就把链表转化为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 如果链表中存在要插入的元素，就跳出循环
break;
// 把e赋值给p，继续执行循环
p = e;
}
}
if (e != null) {
// 如果这时候的e不为空，说明要插入的元素已经存在该HashMap，就执行以下逻辑
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 如果值是空，就把值赋值给那个元素
e.value = value;
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// modCount的值加1
++modCount;
// size的值加1
if (++size > threshold)
// 如果这时候的size大于HashMap所能容量的最大数据量的节点个数，就调用resize方法，进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果table数组已经初始化，就执行以下逻辑
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果threshold大于等于最大容量，就把threshold设为最大容量
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果新的容量（旧的容量的值的补码左移1位，也就是旧的容量的两倍）小于最大容量，并且旧的容量大于等于默认初始容量，就设新的容量是旧的容量的两倍
newThr = oldThr << 1;
}
else if (oldThr > 0)
// 如果threshold大于0，就把该值赋值给newCap
newCap = oldThr;
else {
// 如果初始容量和HashMap所能容纳的最大数据量的节点个数都是0，证明是第一次进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
// threshold的公式是负荷系数乘以数组长度
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// ft的公式是负荷系数乘以数组长度
float ft = (float)newCap * loadFactor;
// 判断初始容量是否小于最大容量，并且ft是否小于最大容量，如果是就使用ft，否则使用Integer的最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新threshold的值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 更新table数组
table = newTab;
if (oldTab != null) {
// 如果之前的数组已经存在数据，由于table的大小发生变化，所以哈希值也会发生变化，需要重新计算索引
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 如果指定索引的元素有值，就把那个值设为空
oldTab[j] = null;
if (e.next == null)
// 如果该索引的元素只有一个，就把元素放到重新计算的索引所在的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果该索引的元素的数据结构是树，就执行拆分操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 如果该索引的元素的数据结构是链表，就重新计算索引，重新分组
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 {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
// 将链表转化成红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 如果tab数组是空或者tab数组小于容器变成树的最小表容量（值是64），就进行扩容
resize();
// 根据key计算出来的哈希值进行取模运算，得到要插入的元素的索引，后面会详细讲解
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 如果tab数组不为空，并且tab数组大于等于容量变成树的最小表容量（值是64），就执行以下逻辑
TreeNode<K,V> hd = null, tl = null;
do {
// 把该节点转化为树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 将链表转化为红黑树
hd.treeify(tab);
}
}
// 将指定映射中的所有映射复制到此映射，如果它之前就存在相同的键，那么就把用新值去替换它的旧值
public void putAll(Map<? extends K, ? extends V> m) {
// 调用putMapEntries方法，前面分析过
putMapEntries(m, true);
}
总结下添加单个元素执行的逻辑：
- 判断table数组是否已经初始化，如果没有初始化，就调用resize方法初始化数组。
- 根据key计算出来的哈希值进行取模运算，得到要插入的元素的索引，并且判断该元素的值是否为空，如果是空，就创建一个节点，并且把数据传进去，然后执行步骤6。
- 判断该索引所在的元素的数据结构是否是树，如果是，就调用putTreeVal方法，使用红黑树插入数据，然后执行步骤5。
- 如果该索引所在的元素的数据结构是链表，就执行循环，判断链表是否存在要插入的元素，如果不存在，就创建一个节点，并且插入到链表中，然后判断是否需要将链表转化为红黑树，条件是链表长度是否大于等于8；如果存在，就跳出循环，最后执行步骤5。
- 判断下该元素的值是否为空，如果是空，就把值赋值给它，并且返回旧值。
- 判断数组的大小是否大于HashMap所能容纳的最大数据量的节点个数，如果是，就扩容，然后返回空。
总结下扩容执行的逻辑：
- 判断table数组是否已经初始化，如果已经初始化，就进行扩容，容量是原来的两倍；如果没有初始化，就进行初始化（更新threshold的值和更新table数组）。
- 对数组进行遍历，按顺序判断步骤3、步骤4和步骤5。
- 判断该索引的元素是否只有一个，如果是，就把元素放到重新计算的索引所在的位置。
- 判断该索引的元素的数据结构是否为树，如果是，就进行拆分操作。
- 如果该索引的元素的数据结构是否为链表，如果是，就重新计算索引，重新分组。
hash方法
我们看下hash方法，这个方法也被称为扰动函数，源码如下所示：
// HashMap.java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
判断key是否为空，如果是空，就返回0；如果不是空，就调用key的hashCode方法，如果这个对象没有重写hashCode方法，就会根据内存地址得到一个int类型的值，然后将得到的哈希值无符号右移16位，最后把得到的值的二进制补码与哈希值的二进制补码进行异或运算，这样做的目的是为了让高位和低位都参与运算，让哈希值的分布更加分散均匀。
取模运算
我们可以看到经常出现如下逻辑，源码如下所示：
// HashMap.java
p = tab[i = (n - 1) & hash]
它用来根据key计算出来的哈希值进行取模运算，得到要插入的元素的索引，目的是为了使元素的分布更加分散均匀，HashMap没有使用hash % n这样的方式进行取模运算，因为在HashMap中，容量都是2的幂，使得(n - 1) & hash等效于hash % n，同时&运算的效率高于%运算，所以HashMap选择使用(n - 1) & hash进行取模运算。
我们假设n的值是2，hash的值是4（2的2次幂），hash % n的值是0，(n - 1) & hash是多少呢？先执行n - 1，得到1，然后1和4进行与运算，因为都是正数，补码和原码一样，补码如下所示：
1（十进制） = 00000000 00000000 00000000 00000001（二进制）
4（十进制） = 00000000 00000000 00000000 00000100（二进制）
执行与运算后，补码如下所示：
00000000 00000000 00000000 00000000
转成十进制后就是0，与hash % n的结果相同。
删除
HashMap的删除方法，源码如下所示：
// HashMap.java
// 根据key删除该映射中指定的键值对（如果存在）
public V remove(Object key) {
Node<K,V> e;
// 调用removeNode方法
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 如果table数组不为空，并且table数组有元素，并且根据key计算出来的哈希值进行取模运算，得到要删除的元素的索引，该索引的元素的数据不为空
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果该索引的元素的key与要删除的元素的key相同，就赋值给node
node = p;
else if ((e = p.next) != null) {
// 如果该索引的元素有下一个节点，就执行以下逻辑
if (p instanceof TreeNode)
// 如果这个节点的数据结构是树，就调用getTreeNode方法
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 如果这个节点的数据结构是链表，就执行以下逻辑
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
// 如果在链表中能找到该节点，就赋值给node
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果能找到要删除的节点，就执行以下逻辑
if (node instanceof TreeNode)
// 如果这个节点的数据结构是树，就调用removeTreeNode方法
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 如果这个节点是链表第一个节点，就把数组的索引指向下一个位置
tab[index] = node.next;
else
// 如果这个节点不是链表的第一个节点，就从链表中删除这个节点
p.next = node.next;
// modCount的值加1
++modCount;
// size的值减1
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
查找
HashMap的查找方法，源码如下所示：
// HashMap.java
// 返回该映射中指定键的值，如果不存在，就返回空
public V get(Object key) {
Node<K,V> e;
// 调用getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果table数组不为空，并且table数组有元素，并且根据key计算出来的哈希值进行取模运算，得到要查找的元素的索引，该索引的元素的数据不为空
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
// 如果该索引的元素的key与要删除的元素的key相同，就返回该元素
return first;
if ((e = first.next) != null) {
// 如果该索引的元素有下一个节点，就执行以下逻辑
if (first instanceof TreeNode)
// 如果该节点的数据结构是树，就调用getTreeNode方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 如果该节点的数据结构是链表，就执行以下逻辑
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 如果在链表中能找到该节点，就返回该节点
return e;
} while ((e = e.next) != null);
}
}
// 如果不存在该元素，就返回空
return null;
}
题外话
常见的Map实现类
Map是一个接口，它是将键映射到值的对象，映射不能包含重复的键，每个键最多可以映射一个值，常见的Map实现类有HashMap、ConcurrentHashMap、Hashtable、LinkedHashMap和TreeMap等，它们的UML类图如下所示：
TheUMLClassDiagramOfACommonMapImplementationClass.png
ConcurrentHashMap
ConcurrentHashMap是线程安全的HashMap，在JDK 1.8之前，ConcurrentHashMap引入了分段锁，分段锁的原理是将数据分成一段一段存储，然后给每一段数据配一把锁，当一个线程访问其中一段数据的时候就会占用那把锁，但是不影响其他线程访问其他段的数据，从而提高效率；在JDK 1.8之后，抛弃了分段锁，利用内置锁synchronized和CAS（Compare And Swap）来保证线程安全。
Hashtable
Hashtable是遗留类，它和HashMap很相似，不同的是，它是继承Dictionary类，而且它是线程安全的，但是并发性不如ConcurrentHashMap，不建议使用该类，如果需要线程安全，可以选择使用ConcurrentHashMap。
LinkedHashMap
LinkedHashMap是HashMap的子类，它通过维护一个双向链表来保证迭代顺序，这个迭代顺序会根据accessOrder（布尔值）来判断是插入顺序，还是访问顺序，默认实现是按插入顺序排序的，它可以实现LRU（Least Recently Used）算法。
TreeMap
TreeMap基于红黑树的NavigableMap实现，它可以根据键的可比较的自然顺序进行排序，或者通过它在创建的时候提供的比较器（Comparator）进行排序，具体取决于使用的构造函数。
解决哈希冲突的几种方式
解决哈希冲突的四种方式：
开放地址法
开放地址法是指当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。公式是Hi(key) = (H(key) + di) mod m，其中，H(key)是key的哈希地址，di是每次再探测时的地址增量，m是哈希表的长度。
增量di可以用不同的取法，根据取法的不同有如下名称：
线性探测法
线性探测法的增量di取1, 2, 3, ……, k(k <= m - 1)的值，当发生地址冲突时，在哈希表中顺序探测下一个存储单元，直到找到空位置为止。
二次探测法
二次探测法的增量di取1^2, -1^2, 2^2, -2^2,……, k^2, -k^2(k <= m / 2)，当发生地址冲突时，在哈希表的左右进行跳跃式探测，双向探测空位置。
随机探测法
随机探测法的增量di是用随机函数计算得到，当发生地址冲突时，在哈希表中随机探测空位置。
值得一提的是，ThreadLocal的内部类ThreadLocalMap是采用开放地址法来解决哈希冲突。
链地址法
链地址法是指将所有哈希地址相同的记录都链接同一个链表中，它处理冲突简单，而且没有堆积现象，也就是非同义词绝对不会发生冲突，各链表上的节点的空间都是动态申请的，所以更加适合无法确定哈希表长度的情况。
再哈希法
再哈希法是指同时构造多个不同的哈希函数，当使用其中一个哈希函数发生冲突时，就使用另外一个哈希函数，直到不再发生冲突为止，这种方法不易产生聚集，但是会增加计算时间。
建立公共溢出区
建立公共溢出区是指将哈希表分为基本表和溢出表，凡是和基本表发生冲突的元素都会被填入溢出表，而且溢出表也可以使用同样的哈希函数，易于实现。
我的GitHub：TanJiaJunBeyond
Android通用框架：Android通用框架
我的掘金：谭嘉俊
我的简书：谭嘉俊
我的CSDN：谭嘉俊
网友评论