共计 11820 个字符，预计需要花费 30 分钟才能阅读完成。
HashMap 源码深度分析
* HashMap 底层数据结构(为什么引入红黑树、存储数据的过程、哈希碰撞相干问题)
* HashMap 成员变量(初始化容量是多少、负载因子、数组长度为什么是 2 的 n 次幂)
* HashMap 扩容机制(什么时候须要扩容？怎么进行扩容？)
* JDK7 与 Jdk8 比拟，JDK8 进行了什么优化？1 定义
HashMap 基于 哈希表 的 Map 接口实现，是以 key-value 存储模式存在，即次要用来寄存键值对。HashMap 的实现不是同步的，这意味着它不是 线程平安 的。它的 key、value 都能够为 null。此外，HashMap 中的映射不是有序的。
- JDK1.7 HashMap 数据结构：数组 + 链表
- JDK1.8 HashMap 数据结构：数组 + 链表 / 红黑树
思考：为什么 1.8 之后，HashMap 的数据结构要减少红黑树？
2 哈希表
Hash 表也称为散列表，也有间接译作哈希表，Hash 表是一种依据关键字值（key – value）而间接进行拜访的数据结构。也就是说它通过把关键码值映射到表中的一个地位来拜访记录，以此来放慢查找的速度。在链表、数组等数据结构中，查找某个关键字，通常要遍历整个数据结构，也就是 O(N)的工夫级，然而对于哈希表来说，只是 O(1)的工夫级
哈希表，它是通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度。这个映射函数叫做 散列函数 ，寄存记录的数组叫做 散列表，只须要 O(1) 的工夫级
思考：多个 key 通过散列函数会失去雷同的值，这时候怎么办？
解决：
（1）凋谢地址法
（2）链地址法
对于凋谢地址法，可能会遇到二次抵触，三次抵触，所以须要良好的散列函数，散布的越平均越好。对于链地址法，尽管不会造成二次抵触，然而如果一次抵触很多，那么会造成子数组或者子链表很长，那么咱们查找所需遍历的工夫也会很长。
3 JDK1.8 前 HashMap 的数据结构
- JDK 8 以前 HashMap 的实现是 数组 + 链表，即便哈希函数获得再好，也很难达到元素百分百均匀分布。
- 当 HashMap 中有大量的元素都寄存到同一个桶中时，这个桶下有一条长长的链表，极其状况 HashMap 就相当于一个单链表，如果单链表有 n 个元素，遍历的工夫复杂度就是 O(n)，齐全失去了它的劣势。
4 JDK1.8 后 HashMap 的数据结构
- JDK 8 后 HashMap 的实现是 数组 + 链表 + 红黑树
- 桶中的构造可能是链表，也可能是红黑树，当 链表长度大于阈值 (或者红黑树的边界值，默认为 8) 并且以后 数组的长度大于 64时，此时此索引地位上的所有数据改为应用红黑树存储。
5. 类结构器
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {JDK 为咱们提供了一个抽象类 AbstractMap，该抽象类继承 Map 接口，所以如果咱们不想实现所有的 Map 接口办法，就能够抉择继承抽象类 AbstractMap。
HashMap 汇合实现了 Cloneable 接口以及 Serializable 接口，别离用来进行对象克隆以及将对象进行序列化。
留神：HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？
据 java 汇合框架的创始人 Josh Bloch 形容，这样的写法是一个失误。在 java 汇合框架中，相似这样的写法很多，最开始写 java 汇合框架的时候，他认为这样写，在某些中央可能是有价值的，直到他意识到错了。显然的，JDK 的维护者，起初不认为这个小小的失误值得去批改，所以就这样存在下来了。6 字段属性
// 序列化和反序列化时，通过该字段进行版本一致性验证
private static final long serialVersionUID = 362498820763181265L;
// 默认 HashMap 汇合初始容量为 16（必须是 2 的倍数）static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 汇合的最大容量，如果通过带参结构指定的最大容量超过此数，默认还是应用此数
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶 (bucket) 上的结点数大于这个值时会转成红黑树(JDK1.8 新增)
static final int TREEIFY_THRESHOLD = 8;
// 当桶 (bucket) 上的节点数小于这个值时会转成链表(JDK1.8 新增)
static final int UNTREEIFY_THRESHOLD = 6;
/**(JDK1.8 新增)
* 当汇合中的容量大于这个值时，表中的桶能力进行树形化，否则桶内元素太多时会扩容，* 而不是树形化 为了防止进行扩容、树形化抉择的抵触，这个值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 初始化应用，长度总是 2 的幂
*/
transient Node<K,V>[] table;
/**
* 保留缓存的 entrySet（）*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 此映射中蕴含的键值映射的数量。（汇合存储键值对的数量）*/
transient int size;
/**
* 跟后面 ArrayList 和 LinkedList 汇合中的字段 modCount 一样，记录汇合被批改的次数
* 次要用于迭代器中的疾速失败
*/
transient int modCount;
/**
* 调整大小的下一个大小值（容量 * 加载因子）。capacity * load factor
*/
int threshold;
/**
* 散列表的加载因子。*/
final float loadFactor;上面咱们重点介绍下面几个字段：
①、Node<K,V>[] table
咱们说 HashMap 是由数组 + 链表 + 红黑树组成，这里的数组就是 table 字段。前面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 申明数组的长度总是 2 的 n 次方(肯定是合数)，为什么这里要求是合数，个别咱们晓得哈希算法为了防止抵触都要求长度是质数，这里要求是合数，上面在介绍 HashMap 的 hashCode() 办法(散列函数)，咱们再进行解说。
②、size
汇合中寄存 key-value 的实时对数。
③、loadFactor
装载因子，是用来掂量 HashMap 满的水平，计算 HashMap 的实时装载因子的办法为：size/capacity，而不是占用桶的数量去除以 capacity。capacity 是桶的数量，也就是 table 的长度 length。
默认的负载因子 0.75 是对空间和工夫效率的一个均衡抉择，倡议大家不要批改，除非在工夫和空间比拟非凡的状况下，如果内存空间很多而又对工夫效率要求很高，能够升高负载因子 loadFactor 的值；相同，如果内存空间缓和而对工夫效率要求不高，能够减少负载因子 loadFactor 的值，这个值能够大于 1。
④、threshold
计算公式：capacity * loadFactor。这个值是以后已占用数组长度的最大值。过这个数目就从新 resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍
7 构造函数
①、默认无参构造函数
/**
* 默认构造函数，初始化加载因子 loadFactor = 0.75
*/
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;}②、指定初始容量的构造函数
/**
*
* @param initialCapacity 指定初始化容量
* @param loadFactor 加载因子 0.75
*/
public HashMap(int initialCapacity, float loadFactor) {
// 初始化容量不能小于 0，否则抛出异样
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" +
initialCapacity);
// 如果初始化容量大于 2 的 30 次方，则初始化容量都为 2 的 30 次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 如果加载因子小于 0，或者加载因子是一个非数值，抛出异样
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 返回大于等于 initialCapacity 的最小的二次幂数值。// >>> 操作符示意无符号右移，高位取 0。// | 按位或运算
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}8 确定哈希桶数组索引地位
后面咱们解说哈希表的时候，咱们晓得是用散列函数来确定索引的地位。散列函数设计的越好，使得元素散布的越平均。HashMap 是数组 + 链表 + 红黑树的组合，咱们心愿在无限个数组地位时，尽量每个地位的元素只有一个，那么当咱们用散列函数求得索引地位的时候，咱们能马上晓得对应地位的元素是不是咱们想要的，而不是要进行链表的遍历或者红黑树的遍历，这会大大优化咱们的查问效率。咱们看 HashMap 中的哈希算法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
i = (table.length - 1) & hash;// 这一步是在前面增加元素 putVal()办法中进行地位的确定次要分为三步：
①、取 hashCode 值：key.hashCode()
②、高位参加运算：h>>>16
③、取模运算：(n-1) & hash
这里获取 hashCode() 办法的值是变量，然而咱们晓得，对于任意给定的对象，只有它的 hashCode() 返回值雷同，那么程序调用 hash(Object key) 所计算失去的 hash 码 值总是雷同的。
为了让数组元素散布平均，咱们首先想到的是把取得的 hash 码对数组长度取模运算(hash%length)，然而计算机都是二进制进行操作，取模运算绝对开销还是很大的，那该如何优化呢？
HashMap 应用的办法很奇妙，它通过 hash & (table.length -1)来失去该对象的保留位，后面说过 HashMap 底层数组的长度总是 2 的 n 次方，这是 HashMap 在速度上的优化。当 length 总是 2 的 n 次方时，hash & (length-1)运算等价于对 length 取模，也就是 hash%length，然而 & 比 % 具备更高的效率。比方 n % 32 = n & (32 -1)
这也解释了为什么要保障数组的长度总是 2 的 n 次方。
再就是在 JDK1.8 中还有个高位参加运算，hashCode() 失去的是一个 32 位 int 类型的值，通过 hashCode()的高 16 位 异或 低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，次要是从速度、效用、品质来思考的，这么做能够在数组 table 的 length 比拟小的时候，也能保障思考到高下 Bit 都参加到 Hash 的计算中，同时不会有太大的开销。
上面举例说明下，n 为 table 的长度：
9 增加元素
//hash(key)就是下面讲的 hash 办法，对其进行了第一步和第二步解决
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
/**
*
* @param hash 索引的地位
* @param key 键
* @param value 值
* @param onlyIfAbsent true 示意不要更改现有值
* @param evict false 示意 table 处于创立模式
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果 table 为 null 或者长度为 0，则进行初始化
//resize()办法原本是用于扩容，因为初始化没有理论调配空间，这里用该办法进行空间调配，前面会具体解说该办法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 留神：这里用到了后面解说取得 key 的 hash 码的第三步，取模运算，上面的 if-else 别离是 tab[i] 为 null 和不为 null
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//tab[i] 为 null，间接将新的 key-value 插入到计算的索引 i 地位
else {//tab[i] 不为 null，示意该地位曾经有值了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 节点 key 曾经有值了，间接用新值笼罩
// 该链是红黑树
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);
// 链表长度大于 8，转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key 曾经存在间接笼罩 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;// 用作批改和新增疾速失败
if (++size > threshold)// 超过最大容量，进行扩容
resize();
afterNodeInsertion(evict);
return null;
}①、判断键值对数组 table 是否为空或为 null，否则执行 resize()进行扩容；
②、依据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，间接新建节点增加，转向⑥，如果 table[i]不为空，转向③；
③、判断 table[i]的首个元素是否和 key 一样，如果雷同间接笼罩 value，否则转向④，这里的雷同指的是 hashCode 以及 equals；
④、判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对，否则转向⑤；
⑤、遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 曾经存在间接笼罩 value 即可；
⑥、插入胜利后，判断理论存在的键值对数量 size 是否超过了最大容量 threshold，如果超过，进行扩容。
⑦、如果新插入的 key 不存在，则返回 null，如果新插入的 key 存在，则返回原 key 对应的 value 值（留神新插入的 value 会笼罩原 value 值）
留神 1：其中代码：
if (++size > threshold)// 超过最大容量，进行扩容
resize();这里有个考点，咱们晓得 HashMap 是由数组 + 链表 + 红黑树（JDK1.8）组成，如果在增加元素时，发生冲突，会将抵触的数放在链表上，当链表长度超过 8 时，会主动转换成红黑树。
那么有如下问题：数组上有 5 个元素，而某个链表上有 3 个元素，问此 HashMap 的 size 是多大？
咱们剖析代码，很容易晓得，只有是调用 put() 办法增加元素，那么就会调用 ++size(这里有个例外是插入反复 key 的键值对，不会调用，然而反复 key 元素不会影响 size), 所以，下面的答案是 7。
10 扩容机制
扩容（resize），咱们晓得汇合是由数组 + 链表 + 红黑树形成，向 HashMap 中插入元素时，如果 HashMap 汇合的元素曾经大于了最大承载容量 threshold（capacity * loadFactor），这里的 threshold 不是数组的最大长度。那么必须扩充数组的长度，Java 中数组是无奈主动扩容的，咱们采纳的办法是用一个更大的数组代替这个小的数组，就好比以前是用小桶装水，当初小桶装不下了，咱们应用一个更大的桶。
JDK1.8 融入了红黑树的机制，比较复杂，这里咱们先介绍 JDK1.7 的扩容源码，便于了解，而后在介绍 JDK1.8 的源码。
// 参数 newCapacity 为新数组的大小
void resize(int newCapacity) {Entry[] oldTable = table;// 援用扩容前的 Entry 数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {// 扩容前的数组大小如果曾经达到最大 (2^30) 了
threshold = Integer.MAX_VALUE;/// 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity];// 初始化一个新的 Entry 数组
transfer(newTable, initHashSeedAsNeeded(newCapacity));// 将数组元素转移到新数组外面
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;
if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);// 从新计算每个元素在数组中的索引地位
e.next = newTable[i];// 标记下一个元素，增加是链表头增加
newTable[i] = e;// 将元素放在链上
e = next;// 拜访下一个 Entry 链上的元素
}
}
}通过办法咱们能够看到，JDK1.7 中首先是创立一个新的大容量数组，而后顺次从新计算原汇合所有元素的索引，而后从新赋值。如果数组某个地位产生了 hash 抵触，应用的是单链表的头插入方法，同一地位的新元素总是放在链表的头部，这样与原汇合链表比照，扩容之后的可能就是倒序的链表了。
上面咱们在看看 JDK1.8 的。
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 原数组如果为 null，则长度赋值 0
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {// 如果原数组长度大于 0
if (oldCap >= MAXIMUM_CAPACITY) {// 数组大小如果曾经大于等于最大值(2^30)
threshold = Integer.MAX_VALUE;// 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
return oldTab;
}
// 原数组长度大于等于初始化长度 16，并且原数组长度扩充 1 倍也小于 2^30 次方
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 阀值扩充 1 倍
}
else if (oldThr > 0) // 旧阀值大于 0，则将新容量间接等于就阀值
newCap = oldThr;
else {// 阀值等于 0，oldCap 也等于 0（汇合未进行初始化）newCap = DEFAULT_INITIAL_CAPACITY;// 数组长度初始化为 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 阀值等于 16*0.75=12
}
// 计算新的阀值下限
if (newThr == 0) {float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个 bucket 都挪动到新的 buckets 中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {oldTab[j] = null;// 元数据 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 { // preserve order
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;
}
// 原索引 +oldCap
else {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;
}该办法分为两局部，首先是计算新桶数组的容量 newCap 和新阈值 newThr，而后将原汇合的元素从新映射到新汇合中。
相比于 JDK1.7，1.8 应用的是 2 次幂的扩大(指长度扩为原来 2 倍)，所以，元素的地位要么是在原地位，要么是在原地位再挪动 2 次幂的地位。咱们在裁减 HashMap 的时候，不须要像 JDK1.7 的实现那样从新计算 hash，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”。
11 删除元素
HashMap 删除元素首先是要找到 桶的地位，而后如果是链表，则进行链表遍历，找到须要删除的元素后，进行删除；如果是红黑树，也是进行树的遍历，找到元素删除后，进行均衡调节，留神，当红黑树的节点数小于 6 时，会转化成链表。
public V get(Object key) {
Node<K,V> e;
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) {
// 依据 key 计算的索引查看第一个索引
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 不是第一个节点
if ((e = first.next) != null) {if (first instanceof TreeNode)// 遍历树查找元素
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;
}12 查找元素
①、通过 key 查找 value
首先通过 key 找到计算索引，找到桶地位，先查看第一个节点，如果是则返回，如果不是，则遍历其前面的链表或者红黑树。其余状况全副返回 null。
public V get(Object key) {
Node<K,V> e;
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) {
// 依据 key 计算的索引查看第一个索引
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 不是第一个节点
if ((e = first.next) != null) {if (first instanceof TreeNode)// 遍历树查找元素
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;
}总结
①、基于 JDK1.8 的 HashMap 是由数组 + 链表 + 红黑树组成，当链表长度超过 8 时会主动转换成红黑树，当红黑树节点个数小于 6 时，又会转化成链表。绝对于晚期版本的 JDK HashMap 实现，新增了红黑树作为底层数据结构，在数据量较大且哈希碰撞较多时，可能极大的减少检索的效率。
②、容许 key 和 value 都为 null。key 反复会被笼罩，value 容许反复。
③、非线程平安
④、无序（遍历 HashMap 失去元素的程序不是依照插入的程序）
如果本文对您有帮忙，欢送
关注和点赞`，您的反对是我保持创作的能源。转载请注明出处！
