Java 源码重读系列之 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;// 如果泛型对象是 Comparableif (p.getRawType() == Comparable.class) {as = p.getActualTypeArguments();// 只有一个泛型参数，且参数类型是 x.classif (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) 去比较。

1. 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 方法试试就知道了。不多说。
2. table、threshold、loadFactor再往下就是一些变量了。其中最核心的变量就是 tabletransient 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% 就会触发扩容。

1. 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 里。

1. 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;}复制代码首先判断了 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 冲突后，会采用链表的方式存储，当链表长度过长时，会将链表转成红黑树结构，提高查询效率。

1. 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 thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = 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 orderHashMap.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;elseloTail.next = e;loTail = e;} else {if (hiTail == null)hiHead = e;elsehiTail.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()方法就在下面。

1. 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 里的方法，已经超出了本文的内容。