文章目录
数据结构
此图为JDK1.8以后，HashMap的数据结构图。JDK1.7以前（包含），HashMap里只有链表，在JDK1.8引入了红黑树，当数组长度大于等于64并且链表的长度大于等于8之后，会将链表转为红黑树。红黑树是一个自平衡的二叉查找树，查找效率会从链表的O(n)降为O(logn)，效率有非常大的提高。
这里有一个疑问，为什么不一开始就存红黑树呢？
- 红黑树的数据结构相较于链表来说比较复杂，需要维持红黑树的性质，在插入时需要左旋右旋等，整体效率来说，可能还比链表慢。
- 当Map中的节点达到一定程度时，会执行resize扩容，在resize时，会对红黑树进行拆分重新哈希，并在新的位置上进行重组，这也是比链表耗时的一个过程，所以设置一定的阈值是有必要的。
源码分析
1. 类结构
2. 类注释
- 允许NULL值，NULL键
- 不要轻易改变负载因子，负载因子过高会导致链表过长，查找键值对时间复杂度就会增高，负载因子过低会导致hash桶的数量过多，空间复杂度会增高
- Hash表每次会扩容长度为以前的2倍
- HashMap是多线程不安全的，在 JDK1.7 进行多线程put操作，可能会造成链表闭环，导致CPU飙到100%，会出现节点或value丢失的情况，而在 JDK1.8 中进行多线程操作只会出现节点和value值丢失，为什么 JDK1.8 多线程操作不会出现链表闭环呢？是因为 JDK1.8 的作者对resize方法进行了优化，不会产生链表闭环。
- 尽量设置HashMap的初始容量，尤其在数据量大的时候，防止多次resize
3. 类常量
//默认hash桶初始长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//hash表最大容量2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表的数量大于等于8个并且桶的数量大于等于64时链表树化
static final int TREEIFY_THRESHOLD = 8;
//hash表某个节点链表的数量小于等于6时树拆分
static final int UNTREEIFY_THRESHOLD = 6;
//树化时最小桶的数量
static final int MIN_TREEIFY_CAPACITY = 64;
4. 实例变量
//hash表，在第一次使用时才初始化，长度是2的整数幂
transient Node<K,V>[] table;
//键值对的数量
transient int size;
//HashMap结构修改的次数
transient int modCount;
//扩容的阈值，当键值对的数量超过这个阀值会产生扩容
int threshold;
//负载因子，默认为 DEFAULT_LOAD_FACTOR
final float loadFactor;
5.构造函数
/**
* 使用该构造函数，会初始化两个变量：loadFactor、threshold
* threshold会通过传入的initialCapacity参数在tableSizeFor方法中计算得出。
* 而table在resize()方法中进行初始化，首次长度为threshold
* tatble初始化后，会将该threshold变为table.length * loadFactor。
* 这也是为什么这里threshold没有 * loadFactor的原因。具体逻辑可以看resize()方法分析
*/
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
hash表没有在构造函数中进行初始化，而是在第一次put操作时进行初始化和resize。
构造函数中有一个方法：tableSizeFor(initialCapacity)，这个方法的作用是用你传入的initialCapacity进行计算，返回一个大于等于initialCapacity & 最小的2的整数幂值。所以这个操作保证了无论你传入的initialCapacity为多少，hash表的初始长度都是2的整数幂次方。比如initialCapacity = 6，则计算出来的hash表长度为8.
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
6. 插入方法——put()
public V put(K key, V value) {
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;
// 当table为空时，初始化table（不是通过构造函数初始化，而是在插入时通过扩容初始化，有效防止了初始化HashMap没有数据插入造成空间浪费，可能造成内存泄露的情况）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果table的目标位置没有元素，则直接放入一个新建的node，否则进入else代码块
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// table的第一个节点的key = 传入的key，则将该节点复制给e（不需要进入红黑树和链表里找）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果table的第一个节点是TreeNode，则进入红黑树的查找，没有则新增，有则返回旧节点并赋值给e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 不是上面两种情况，则现在是链表，直接遍历链表，如果不存在则在队尾新增节点，如果存在则将该节点赋值给e
else {
for (int binCount = 0; ; ++binCount) {
// 在队尾新增节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表的长度 >= 8 && table数组的长度 >= 64（在treeifyBin方法中判断） 将链表树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果链表中存在则跳出循环，e的值已在上一个if中赋值了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果在当前map中存在旧的key，则将该节点的值赋值为新值，并返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 开放接口，给LinkedHashMap使用
return oldValue;
}
}
// map的调整次数+1
++modCount;
// 键值对的数量达到阈值时扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 开放接口，给LinkedHashMap使用
return null;
}
流程
（1）如果table没有初始化，则初始化table。
（2）是新的键值对
- 如果table中相应的位置没有节点，则该键值对作为头结点；
- 如果是链表则放在队尾，如果达到一定条件，将链表转为红黑树；
- 如果是红黑树，则进行相应的插入操作。
（3）如果已经有相应的键存在，则更新键值对的值，并返回旧值。
然后我们再看看hash方法，它是如何找寻table中相对应的位置
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从方法得知，HashMap通过将key的hashCode无符号右移16位后再与hashCode异或得到这个key在HashMap中的hash值，然后再在putVal()方法中通过 (n - 1) & hash 计算，得到table的索引位置。这里延伸出两个问题。
（1）为什么要两次hash，而不直接使用hashCode？
首先，通常HashMap的table的长度一般都很小，即n一般都很小，而hashCode的值是int类型，有32位，需要当n的值大于2的16次方+1时，才会使用到hashCode的高16位。通常来说，HashMap的n的值大于2的16次方的情况是很少的，即那么就会出现下面这种情况。
我们假设n当前的大小为：2^16
当hashCode = 2^16 - 1时，(n - 1) & hashCode = 2^16 - 1
当hashCode = 2^17 - 1时，(n - 1) & hashCode = 2^16 - 1
当hashCode = 2^18 - 1时，(n - 1) & hashCode = 2^16 - 1
当hashCode = 2^19 - 1时，(n - 1) & hashCode = 2^16 - 1
如果不知道怎么算出来的，自己换成二进制计算哈
通过上面的例子可以看出，当hashCode的低16位相同时，不管hashCode的高16位是多少，都会使这些键值对指向同一个table的索引，照常hash冲突，从而导致链表的长度变长或者红黑树的深度变深。而通过二次hash之后，将hashCode的高16位参与后面的与运算，尽可能的让key均匀的分布在table的数组上，避免造成Hash堆积。
（2）为什么不用 hash % n？
其实 hash % n 与 hash & (n - 1) 的结果是等价的，但是&位运算的效率比%高，因为&运算是使用二进制直接运算，而计算机天生就认识二进制。所以使用hash & (n - 1)效率更高。
7. 扩容机制——resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 1. 这里计算出新的table的长度与threshold的值
// 第一种情况，已经跑了一段时间后，需要扩容，即oldCap > 0，oldThr > 0
if (oldCap > 0) {
// 如果table的长度已经达到最大值，直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则newCap = 2 * oldCap，当oldCap >= 16时
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 第二种情况，使用有initialCapacity参数的构造函数 & 第一次put数据，此时oldCap = 0，oldThr > 0
else if (oldThr > 0)
// 将旧的threshold赋值给newCap，这种情况newThr = 0，newThr在后面进行赋值
newCap = oldThr;
// 第三种情况，使用空参构造方法 & 第一次put数据，此时时oldCap = 0，oldThr = 0
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 在上面第二种情况的时候，newThr = 0，这时候需要去给newThr赋值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新threshold的值为newThr
threshold = newThr;
// 新建一个table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果就的table不为空，将旧的table上的键值对重新映射到新table上
if (oldTab != null) {
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);
// 该桶是链表，将原链表拆分为两个链表，两个链表的索引位置，一个为原索引，一个为原索引加上旧Hash桶长度的偏移量，下面会进行说明（这也是JDK1.8的优化，不会造成闭环）
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;
}
// 高位链表
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;
}
// 如果高位链表不为空，赋值到“原索引+旧table长度”的索引上
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容的时间点
- 第一次put操作
- HashMap的size大于threshold，threshold = size * loadFactor
流程
（1）计算新table的容量与阈值，初始化新table
（2）如果旧table上有数据，则将旧table上的键值对映射到新table上
链表在映射时的巧妙之处
table的长度总会是2的整数幂，而每次扩容，新table的长度总为旧table长度的2倍，根据这种现象，作者实现了一种非常巧妙的算法，他将新的table分为2半，高位与低位，然后计算 hash & oldCap，如果为0则放在低位，为1则放在高位，具体算法可以看上面的逻辑，那他为什么可以这么做呢？我们来看下面这张图
而这种做法，大大提高了链表在迁移过程中的效率，因为不需要再一个节点一个节点进行rehash。
8. JDK1.7造成链表闭环原因
为什么JDK1.7的HashMap在多线程环境下，会出现闭环，导致CPU跑满，使用率飙到100%呢？我们先来看看JDK1.7中HashMap的resize代码。
void resize(int newCapacity) {
Entry[] oldTable = table;
// 获取旧table的长度——capacity
int oldCapacity = oldTable.length;
// 如果旧table的capacity已经达到了最大，则修改阈值，直接返回，不进行扩容
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 用新的capacity创建一个新的table数组
Entry[] newTable = new Entry[newCapacity];
// 将旧table中的键值对迁移到新table中，initHashSeedAsNeeded方法用于判断是否需要进行rehash
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将信的table数组赋值给HashMap对象实例变量中，供外界使用
table = newTable;
// 修改下一次扩容所需的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 将旧table中的键值对迁移到新table中
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;
// 如果需要rehash，则重新计算当前节点的hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 定位当前节点在新table中的索引
int i = indexFor(e.hash, newCapacity);
// 将当前元素的next指针，指向新表中目标索引的链表的头结点，然后将当前节点放到目标索引位置，相当于头插法
e.next = newTable[i];
newTable[i] = e;
// 继续下一个元素
e = next;
}
}
}
// 根据Hash值和table的大小定位索引
static int indexFor(int h, int length) {
return h & (length-1);
}
这个扩容的过程这里不细说，在单线程模式下，扩容前与扩容后的结果是这样的。
而造成闭环的原因也是因为扩容，发生在transfer方法在转移节点的时候，在下面这段代码中。
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;
}
我们来看看是怎么造成闭环的。
这张图可以很好的说明是怎么产生闭环的，具体过程，大家可以跟着代码进行模拟。
在JDK1.8中为什么不会产生闭环呢？
首先，改进后的resize方法在迁移过程中，使用了高位与地位两个链表对原链表进行拆分，而且使用的是尾插法，这种方式，始终不会造成在转移前后链表倒置，更不会因为多线程扩容而导致闭环。虽然HashMap解决了闭环问题，但是HashMap还是多线程环境下不安全的，数据丢失与覆盖的问题，仍然存在。
9. 清除方法——clear()
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
HashMap其实这段代码特别简单，为什么贴出来呢？到底是clear好还是新建一 个HashMap好？我认为clear()比新建一个HashMap好。下面从空间复杂度和时间复杂度来解释一下。
从时间角度来看，这个循环是非常简单无复杂逻辑，并不十分耗资源。而新建一个HashMap，首先他在在堆内存中年轻代中查看是否有足够空间能够存储，如果能够存储，那么创建顺利完成，但如果HashMap非常大，年轻代很难有足够的空间存储，如果老年代中有足够空间存储这个HashMap，那么jvm会将HashMap直接存储在老年代中，如果老年代中空间不够，这时候会触发一次minor gc，会产生小规模的gc停顿，如果发生minor gc之后仍不能存储HashMap，那么会发生整个堆的gc，也就是full gc，这个gc停顿是很恐怖的。实际上的gc顺序就是这样的，并且可能发生多次minor gc和full gc,如果发现年轻代和老年代均不能存储HashMap，那么就会触发OOM，而clear()是肯定不会触发OOM的，所以数据里特别大的情况下，千万不要创建一个新的HashMap代替clear()方法。
从空间角度看，原HashMap虽然不用，如果数据未被清空，是不可能被jvm回收的，因为HashMap是强引用类型的，从而造成内存泄漏。所以综上所述我是不建议新建一个HashMap代替clear()的，并且很多源码中clear()方法很常用，这就是最好的证明。