Java 源码重读系列之 HashMap
0. 成员变量
首先我们先看一下 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，就是map里的元素值超过 75% 就会触发扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//下面还有三个树化的参数
//如果哈希值相同的元素超过 8 个，则树化
static final int TREEIFY_THRESHOLD = 8;
//树的节点小于 6 个，则转成链表
static final int UNTREEIFY_THRESHOLD = 6;
//如果 map 的元素小于 64，即便是 哈希值相同的元素超过 8 个了，也不树化，会扩容
static final int MIN_TREEIFY_CAPACITY = 64;
下面还有一个 Node 类，这个类就是 HashMap 存储元素的容器，其实很简单
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//... ...
}
没有多少复杂的内容，类似于链表的Node节点，key、value、next，因为大量的地方都需要用到对象的 hash 值，所以又记录了下 key 的 hash 值。
1. hash()
继续往下看
//求 key 的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
也没什么好说的，就是通过对象的 hashCode 计算出一个 int 值。
2. comparableClassFor()
下面有个 comparableClassFor 方法，这个方法的主要是判断入参 x 是否实现了 Comparable 接口。不过写的格式有点紧凑，我们需要展开以下。
static Class<?> myComparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c = x.getClass();
// 获取 x 实现的所有接口
Type[] ts = c.getGenericInterfaces();
Type[] as;
Type t;
ParameterizedType p;
//如果 x 是 String 类型 直接返回
if (c == String.class) {
return c;
}
if (ts != null) {
// 遍历实现的所有接口
for (int i = 0; i < ts.length; ++i) {
t = ts[i];
// 如果接口有泛型
if (t instanceof ParameterizedType) {
p = (ParameterizedType) t;
// 如果泛型对象是 Comparable
if (p.getRawType() == Comparable.class) {
as = p.getActualTypeArguments();
// 只有一个泛型参数，且参数类型是 x.class
if (as != null && as.length == 1 && as[0] == c) {
return c;
}
}
}
}
}
}
return null;
}
举个例子:
class MyTest implements Comparable<MyTest> {}
会返回 MyTest.class
class MyTest implements Comparable<Integer> {}
会返回 null
这个方法就结束了，如果还是不能理解，可以将代码复制出来，打个断点跑一下。继续往下看。
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
这个方法有意思，注释是说，如果 x 是 kc 的类型，返回 k.compareTo(x) （k 是筛选过的比较类）。如果你查找下这个方法的使用地方就会发现，kc 这个参数就是上面 comparableClassFor 返回的类型。
这么一看是不是就清晰了？ comparableClassFor(x) 拿到类型，然后传入 compareComparables(kc,k,x) 去比较。
3. tableSizeFor()
下面又是一个方法：
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;
}
这个方法也很有意思，看着很复杂，其实功能很简单，返回第一个大于等于 cap 的 2 的幂值。还是那句话， main 方法试试就知道了。不多说。
4. table、threshold、loadFactor
再往下就是一些变量了。其中最核心的变量就是 table
transient Node<K,V>[] table;
通过注释我们就可以知道这个是存储 HashMap 元素的数组，在第一次使用时被初始化，并且根据需要调整大小，长度适中是 2 的幂。
table 数组就是存储 HashMap 元素的底层结构，具体怎么存储我们后面再看。不过需要注意的是这个变量使用了一个 transient 修饰符，这在我们平常的编码中是很少见到的。这个修饰符的作用是在序列化时跳过该属性。是跟 Serializable 相对应的。其实就是当一个 HashMap 对象被序列化到文件中时，其中的元素是没有写到文件里的。所以通过反序列化也是拿不到元素的。
我们知道了它的功能，但是 HashMap 为什么要这么做呢？其实这个是跟 HashMap 的 put 方法有关系，我们稍后再说。继续往下看。
下面还有一些其他的属性，其中有两个比较重要。
int threshold;
final float loadFactor;
threshold 是下次扩容时 HashMap 的容量。 loadFactor 是加载因子，当 HashMap 的容量达到总容量的一定比例就会触发扩容。这两个字段都跟扩容有关，等看到扩容时再说。
再往下就是几个构造方法了，前面三个构造方法都只是在确定 threshold、loadFactor 这两个属性的默认值。没有什么好说的
threshold 如果初始化时没有传值就是 0 ，loadFactor 默认值是 DEFAULT_LOAD_FACTOR = 0.75f。也就是说，如果 HashMap 的当前容量达到总容量的 75% 就会触发扩容。
5. putMapEntries()
后面还有一个构造方法是传入了一个 Map 集合，它会把入参中集合里的元素 put 到当前的 HashMap 集合中。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
这个构造方法首先初始化了 loadFactor 属性，然后调了putMapEntries 方法，这个方法就在下面。同样格式有点乱，没关系，我们先调整下格式。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s <= 0){
return;
}
if (table == null) {
float ft = ((float)s / loadFactor) + 1.0F;
int t;
if (ft < (float)MAXIMUM_CAPACITY){
t = (int)ft;
}else {
t = MAXIMUM_CAPACITY
}
if (t > threshold){
threshold = tableSizeFor(t);
}
}
else if (s > threshold){
resize();
}
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);
}
}
如果 map 里没有元素，直接结束。因为我们是构造方法进入到这个方法里的，所以 table 一定为 null，然后计算了一下 ft ，表示放入 m 个元素后，HashMap 的最大容量，（如果 s = 75,那 ft = 101）。
然后计算了一下 t 就是 map 需要的最大容量。并且判断一下是否超限。然后判断了一下是否要更新 threshold ，因为我们是构造方法进来的，所以一定是需要更新的。更新结束后就是 for 循环依次调用 putVal 将元素放入到当前的 HashMap 里。
6. putVal()
然后我们跳到 putVal 方法。这个方法的格式依然不太好阅读，我们需要修改下。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K, V> e;
K k;
if (p.hash == hash) {
k = p.key;
if (k == key || key != null && key.equals(k)) {
e = p;
}
} else {
if (p instanceof HashMap.TreeNode) {
e = ((HashMap.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) {
treeifyBin(tab, hash);
}
break;
}
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 是否进行了初始化，没有的话进行 resize， 这个方法我们一会再看。它的作用就是返回一个 Node 数组，数组的长度就是 threshold。初始化好之后就是判断下这个数组的(n - 1) & hash 位置是否有值，没有值的话直接创建一个 Node 存到数组里就结束了。其实 (n - 1) & hash 相当于 hash % (n-1) 的作用，但是与操作的效率比取模的效率高。二者达到的效果是一样的。
如果有值，并且 key 相等，说明是同一个元素，这个时候 e 就是 HashMap 里的元素，后面对 e 的判断就会直接返回 e 对应的 value。
如果 key 不相等，说明发生了 hash 冲突。两个 hash 值不一样的元素应该存储到数组的同一个位置。这个时候判断了一下 Node 的类型。如果是 TreeNode 那么调用 putTreeVal 方法。
如果不是，则依次遍历当前位置节点的 next 指针，直到为空，插入新节点。其实就是讲新节点挂到了已当前节点为表头的链表尾部。插入成功之后判断了一下链表的长度，如果需要则进行树化。将当前链表转成一个红黑树。这个主要是解决链表太长，查询效率低的问题。而且在遍历链表期间依然判断了 key 是否相等，相等则直接返回旧元素的 value。
好像也不是很难，这个就是 HashMap 最核心的方法之一了。从这个方法中也可以知道，HashMap 的底层存储结构是一个数组。如果发生 hash 冲突后，会采用链表的方式存储，当链表长度过长时，会将链表转成红黑树结构，提高查询效率。
7. resize()
下面我们看一下resize() 方法
final HashMap.Node<K, V>[] resize() {
HashMap.Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.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 HashMap.TreeNode)
((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
HashMap.Node<K, V> loHead = null, loTail = null;
HashMap.Node<K, V> hiHead = null, hiTail = null;
HashMap.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;
}
resize() 方法的主要作用就是当 table 数组中的元素超过一定的数量后，对 table 数组进行扩容，以便减少 hash 碰撞发生的概率。
最前面一大串的 if 、else 判断主要是为了确定两个变量的值 newCap 和 newThr 。newCap 是指扩容后新的 table 数组的长度。newThr 是指新数组的元素超过多少时需要扩容。
计算的方式分几种场景。第一种 oldCap > 0: 这种是正常扩容，oldTable 已经有元素了，而且元素的数量也达到了扩容的数量。这时 newCap 和 newThr 是原来数值的 2 倍（<< 是右移操作）
而且判断了下是否超过了最大值。如果 oldCap 已经大于等于最大值了，那直接把下次扩容的阈值调整到最大就结束了，因为 table 数组已经无法扩容了。
(newCap = oldCap << 1) < MAXIMUM_CAPACITY 这一行代码很有意思它的执行逻辑是，先将 oldCap 右移一位后的数值赋值给 newCap，然后判断 newCap 是否超过了 MAXIMUM_CAPACITY 。有意思的点在于，它没有关注 newCap 的溢出情况！！这个其实也是 HashMap 的的容量永远都是 2 的整数次幂的原因。因为，把一个2 的整数次幂的数值右移一位后，依然是一个2 的整数次幂，而 MAXIMUM_CAPACITY 就是允许的最大的 2的整数次幂。因为之前已经判断过是否等于 MAXIMUM_CAPACITY 了。所以，oldCap 右移后，最大只能是等于 MAXIMUM_CAPACITY ，不会溢出。而且，当 newCap 等于 MAXIMUM_CAPACITY 是没有对 newThr 赋值的，对 newThr 赋值的逻辑是在下面的 if (newThr == 0) 的地方。
第二个场景 else if (oldThr > 0) 执行到这个 if 里的情况是，初始化的时候传了 initialCapacity 这个参数。还记得之前初始化时 threshold 的赋值逻辑么？
this.threshold = tableSizeFor(initialCapacity)
当初始时传了 initialCapacity 参数，在第一次 put 操作时，就会触发首次扩容（或者说初始化 table 数组）。
这里有个小知识点：我们在平时写代码使用到 HashMap 时，为了提高效率，不让 HashMap 触发扩容，都会指定 HashMap 的容量，比如：
Map<String, String> map = new HashMap<>(40);
这个时候我们往 Map 里放 5 个元素，应该是只扩容一次即初始化 table 那次。好像没有什么问题。这时因为在第一次初始化时 tableSizeFor 这个参数返回的是大于等于 initialCapacity 的最小的 2 的整数幂的值。比如你传 50，初始化的结果是 64 。而默认的 loadFactor 是 0.75，也就是在元素达到 48 时才会触发扩容。
但是，如果你给的值是 48 以上的呢? 或者说恰好是 64 的时候。这个时候就会在插入第 49 个元素时再次触发一次扩容。所以，如果你明确的知道元素的容量的话，可以初始化 2 倍元素容量的 HashMap ，这样就不会触发两次扩容了。
继续往下说，计算好 newCap 和 newThr 的值后，就创建了一个 newTab，然后就是遍历 oldTab 不断的将元素转移到 newTab 里去。
首先将 oldTab 的引用置为 null，避免内存泄露。然后当前元素会有三种情况：
第一种 e.next == null 就是当前位置只有这一个元素，没有发生 hash 冲突。这种最简单，直接放到 newTab 里就可以了。
第二种 e instanceof TreeNode，就是发生了 hash 冲突，且已经把链表转成了红黑树的结构了（还记的 putVal 方法么？）。这种就需要按照红黑树的操作，把 e 这个节点从 oldTab 上摘下来，挂到 newTab 上去（有点复杂，已经超过了本文的内容。需要了解的可以搜一下红黑树）。
第三种，就是发生了 hash 冲突，但是存储结构还是链表的情况。这种情况如果按照正常的思路的话，无非就是遍历链表，依次将链表的元素放入到 newTab 就好了。但是这样就会有一个问题，就是链表上的元素依然有可能出现 hash 冲突，如果在遍历链表期间多个元素发生了 hash 冲突怎么办呢？
很显然，从代码上来看，并没有按照我们的思路来。代码逻辑是根据元素的 hash 值将一个链表分成了两个链表。loHead 和 hiHead。等拆分完成后，直接将链表的表头保存到了 newTab 的两个元素里。是不是很神奇？？就好像是在说，扩容前发生了 hash 冲突的元素，那么扩容后也有可能发生 hash 冲突，并且这些元素一定应该放到 newTab[j] 或者是 newTab[j+oldCap] 这两个位置。事实就是这样！！
其实，你可以写代验证下，扩容前发生 hash 冲突的元素，如果 (e.hash & oldCap) == 0 那么它一定会落在 newTab[j]上，否则一定落在 newTab[j+oldCap] 上。数学就是这么完美~~
好了，resize()方法到这里就结束了。我们回到 putMapEntries() 方法这里继续往下看。
再往下，szie() 和 isEmpty() 都没有什么好说的，下面是 get(Object key) 方法，这个是 HashMap 最常用的方法之一。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
好像也没有特别复杂，计算 key 的 hash 值，然后通过 getNode 方法获取 node 对象，找不到就返回 null，找到了就返回对应的 value。getNode()方法就在下面。
8. getNode()
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) {
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;
}
如果你对 putVal() 方法已经非常熟悉了，其实 getNode() 就非常清晰了。首先判断了 table 是否为空，不为空的话就通过 hash 找对应位置的元，如果对应的位置有值，就判断 key 是否相等。相等直接返回。
如果不相等，则判断当前位置是否有其他元素，如果是 TreeNode 则从红黑树里找，如果是链表则遍历链表找。
这里需要注意下，还记得之前我们说过 table 这个变量加了 transient 修饰符么，就是为了不让 table 元素进行序列化。其实是跟hash(key) 这个方法有关系。你可以翻看下hash() 这个方法，里面有这样一段 h = key.hashCode()。这里的 hashCode() 你找到它的定义会发现是下面这样的,
public native int hashCode();
这是一个本地方法。这个方法在不同的 JVM 上可能会有不同的实现，所以，就有可能出现，序列化前和序列化后的对象 hashCode() 方法返回的值不同。但是在序列化后，HashMap 保存在 table 中的位置没有变，就会出现找不到的情况，这就是 HashMap 中的一些元素不能序列化的原因。
继续往下就没有什么好说的了，剩下的除了像 clear()、remove() 这种比较简单的方法外，就剩一个最复杂的treeify和untreeify。这个是 HashMap 里最复杂的部分，都是 TreeNode 里的方法，已经超出了本文的内容。