【源码精读】长文解析 – Hashmap

前面发了有关HashMap的内容，做一个HashMap的深度剖析，这里仅针对Java8来进行剖析（原谅我的破烂公司）

对HashMap的基础认知

在日常开发中我们用过很多次了，那可太简单了，无非就是定义一个Map，然后里面都是Key和value

HashMap的基础操作

import java.util.HashMap;publicclassMtcTest {publicstaticvoidmain(String[] args) {// 创建 HashMap 对象        HashMap<Integer, String> hashMap = newHashMap<Integer, String>();// 添加键值对        hashMap.put(1, "Sany");        hashMap.put(2, "Test");        hashMap.put(3, "Alipay");        hashMap.put(4, "GuangZhou");// 删除（一般都很少用）		hashMap.remove(4);// 删除所有		hashMap.clear();// 大小			hashMap.size();// 还有很多....        System.out.println(hashMap);    }}

‍

HashMap怎么取值

// 跟着上面的代码，不重新CV了for (Integer i : hashMap.keySet()) {// 这里循环里面获取的 i就是 map里面的key// value就是 get(i); 是不是很直观，就是跟到这个key值就能获取到对应的value// 因为hashmap里面就是一一对应的key,value}

现在正式进入源码阶段

先look look 几个核心成员变量是什么，这里可以理解为HashMap的配置参数

1. 核心常量( static final 的变量)

/** * The default initial capacity - MUST be a power of two. */// 默认的初始容量 1 << 4，源码大哥都爱用位运算符，我这种菜鸡就不爱用，下面这个aka是他们自己写的，interesting// 必须是2的幂次，这里可以用于后续的寻址优化static final int DEFAULT_INITIAL_CAPACITY=1 << 4; // aka 16/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */// 最大的容量，用来限制数组的上线，避免内存溢出static final int MAXIMUM_CAPACITY=1 << 30;/** * The load factor used when none specified in constructor. */// 默认负载因子，用于平衡空间利用率和哈希冲突的概率static final float DEFAULT_LOAD_FACTOR=0.75f;/** * The bin count threshold for using a tree rather than list for a * bin.  Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. *//** * 上面的内容大概是说当使用输而不是列表来表示桶元素的数量阈值的时候，并且桶的数量 * 已经达到需要转换的节点数量的时候就会转成树结构。并且这个值必须大于2，并且在收缩的时候必须小于8 */// 链表转红黑树的阈值，见名知义啊兄弟们，TREEIFY 变成树的门槛static finalint TREEIFY_THRESHOLD=8;/** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */// 这就是跟上面反过来的了，当这个阈值变成6了，就会降级变成链表了static final int UNTREEIFY_THRESHOLD=6;/** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */// 树化的最小数组容量，也就是数组也需要达到这个大小才会升级为红黑树的意思static final int MIN_TREEIFY_CAPACITY=64;

‍

2. 核心实例变量

/* ---------------- Fields -------------- *//** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */// 上面说的是在第一次使用的时候给我们初始化一个数组，如果满了的话就会按2的幂次方来进行扩容// 哈希桶数组，这里是存储数据的地方transient Node<K,V>[] table;/** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */// 这里可以拿到transient Set<Map.Entry<K,V>> entrySet;/** * The number of key-value mappings contained in this map. */// 存储的多少对键值对的数量HashMap所有键值对的集合transientint size;/** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash).  This field is used to make iterators on Collection-views of * the HashMap fail-fast.  (See ConcurrentModificationException). */// 结构的修改次数，这里是用于后面的快速失败机制的，当迭代器在遍历的时候结构被修改会抛出异常ConcurrentModificationExceptiontransientint modCount;/** * The next size value at which to resize (capacity * load factor). * * @serial */// (The javadoc description is true upon serialization.// Additionally, if the table array has not been allocated, this// field holds the initial array capacity, or zero signifying// DEFAULT_INITIAL_CAPACITY.)// 扩容阈值 = (capacity * load factor) 看懂了没int threshold;/** * The load factor for the hash table. * * @serial */// 负载因子finalfloat loadFactor;

‍

HashMap的高性能的soul

HashMap 高性能的查询和插入逻辑，都是依赖于均匀的哈希分布，所以源码的关键就是 哈希值的计算 和 哈希索引定位 这两个灵魂

1. Key的哈希值是怎么算的

• turn our page to int hash()

  static final int hash(Object key) {int h;// 核心逻辑：key.hashCode() 高16位异或低16位return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

  这里分析一下：

  有点抽象，举个例子

• 这个key的hashchode是一个int类型，32位的值，比如现在是0x0001FFFF转成 二进制：00000000 00000001 11111111 11111111

• 当我们右移16位，也就是0x00000001，二进制是：00000000 00000000 00000000 00000001

• 异或结果是：0x0001FFFE（00000000 00000001 11111111 11111110）

• 也就是说，原本仅高位有差异的哈希值，经过计算后也会产生差异，那他们就会避免了哈希碰撞。

• h = key.hashCode() ：获取传进来的key原生的哈希值

• h >>> 16：将哈希值右移动16位，把高位移动到低16位的位置

• ^ ：异或运算，让高16位和低16位的特征混合，也就是相同位位0，不同位1

1. 数组索引定位（i = (n – 1) & hash）：计算hash值对应的HashMap的底层数组的下标

   这样说好像有点抽象，在get和put方法中，都有用到这个公式来记性计算key对应的数组的索引。

   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) { // ！！！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);        }    }returnnull;}

   这里分析下（i = (n – 1) & hash）

1. 这里的n是数组的容量，并且必须是2的幂次，为什么？

   n – 1 的二进制是全1的，此时 & 运算等价于取模运算（hash % n），但 & 运算的效率远高于取模，这是 HashMap 的性能优化点）

2. then为什么不使用取模？

   计算机对位运算的支持更加底层，性能更高

‍

‍

核心操作方法

由于我的懒惰，我就挑三个核心的方法来重点说一下

get(Object key)：查询键对应的值

1. 这个流程还是挺好懂的，虽然上面已经有代码了，但我还是重新贴一次

/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}.  (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */public V get(Object key) {    Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}/** * Implements Map.get and related methods. * * @param hash hash for key key是经过了HashMa.has() 方法计算后的哈希值的 * @param key the key 要查询的key * @return the node, or null if none */final Node<K,V> getNode(int hash, Object key) {// tab：引用当前 HashMap 的哈希桶数组 table// first：当前哈希桶数组中，对应索引位置的首节点（可能是 Node 或 TreeNode）// e：遍历过程中用于临时存储的节点// n：哈希桶数组的长度    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// step1. 校验// 1. 先判断 table是不是null，数组是否已经初始化了// 2. n = tab.length > 0 也是一样的判空的作用// 3. first = tab[(n - 1) & hash]) != null 对应索引的位置是否有节点if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {// step2. 检查第一个节点是否就是你想要查的节点（满足最理想情况）if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 如果key相等了就返回首节点，查找结束// step3. 第一个节点不是目标节点，判断是不是需要后续遍历节点if ((e = first.next) != null) {// 场景1: 如果已经转成了红黑树了，就要用红黑树来进行高效查找if (first instanceof TreeNode)// 这个getTreeNode我就不展开了，懒惰发力了,（二分查找思想）返回目标节点O(log n) 时间复杂度）return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {// 场景2: 首节点事普通链表的时候，采用线性遍历查找if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))return e;            } while ((e = e.next) != null); // 遍历链表，直到到链表的末尾，也就是 next = null        }    }returnnull;}

1. 这里还能同时衍生出几个面试可能会问的问题：

• 为什么 key 的匹配条件是哈希值相等 + (== 或 equals) ？

• 当 key 为 null 的时候要怎么处理？

• 为什么需要优先判断主节点，再遍历后续节点呢？

• 在遍历链表的时候为什么用do-while而不用while？

  这些需要先思考一下，后面会输出一篇单独来解决这些问题

在说put()方法之前，我们还需要先了解一下hashmap的resize()

1. resize的方法有两个调用到的场景

   还有就是在 resize() 方法被 put() 方法调用时，也被 treeifyBin() 方法给间接调用了，链表树化前如果数组的容量不足，会优先扩容而不是树化

• 在put 键值对的时候，table 为 null 或长度为 0，此时 resize() 负责初始化哈希桶数组

• HashMap 中 size ≥ threshold（扩容阈值）时，resize() 负责扩容（数组容量翻倍）+ 旧节点迁移到新数组

2. 进入正题看看源码

• step 1：需要计算新的容量和新的阈值

• 场景1：旧数组已经初始化的情况下 -> 这个时候时需要扩容的，也就是数组里已经是有数据的意思

• 场景2：旧数组没有初始化 -> 这个时候其实就是用户传了初始容量创建了hashMap，比如：new HashMap(100)

• 场景3：旧数组没有初始化，并且 oldThr = 0，也就是日常我们梭哈的 new HashMap();

final Node<K,V>[] resize() {// 1. 保存旧数组       	Node<K,V>[] oldTab = table;intoldCap= (oldTab == null) ? 0 : oldTab.length;intoldThr= threshold;// 2. 定义新的数组int newCap, newThr = 0;// 现在开始分场景进行操作了// 3.场景1：旧数组已经初始化，说明现在这里的操作时扩容的操作了if (oldCap > 0) {// 3.1 旧容量已经大于等于最大的容量了，所以无法再扩容了if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE; // 阈值设置为Interge的最大值，后续就不会继续扩容了return oldTab; // 返回旧的数组            }// 3.2 旧容量翻倍的情况下，没有超过最大容量的情况elseif ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)// 新阈值也翻倍，这里的比例是跟上面的 oldCap是一样的                newThr = oldThr << 1; // double threshold        }// 4. 场景2：旧数组没有初始化, 并且oldThr > 0elseif (oldThr > 0) // initial capacity was placed in threshold// 新容量 = 旧阈值            newCap = oldThr; // 5. 场景3：旧数组没有初始化，并且 oldThr = 0else {               // zero initial threshold signifies using defaults            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }// 6.计算新阈值，这里是处理场景2的情况下，newThr如果是0的情况下if (newThr == 0) {floatft= (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }// 7.再更新扩容之后的阈值为新的阈值        threshold = newThr;// 8. 创建新的哈希桶数组，并把新的newCap放到这里@SuppressWarnings({"rawtypes","unchecked"})        Node<K,V>[] newTab = (Node<K,V>[])newNode[newCap];        table = newTab;// 9. 如果旧数组不为空，说明当前是扩容的，所以需要将旧的节点数据转移到这里if (oldTab != null) {// 9.1 遍历旧数组的每个哈希桶for (intj=0; j < oldCap; ++j) {                Node<K,V> e;// 9.2 判断当前桶是否有节点，没有就跳过if ((e = oldTab[j]) != null) {                    oldTab[j] = null; // 这里是释放引用，方便GC的// 9.3 桶只有单个节点（无链表/红黑树），直接迁移if (e.next == null)                        newTab[e.hash & (newCap - 1)] = e;// 9.4 如果是红黑树节点，就需要拆分这个树进行迁移了elseif (e instanceof TreeNode)                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 9.5 那最后就只剩下普通链表了，也就是拆分链表并迁移就可以了else { // preserve order// lo = low 低位子链表                        Node<K,V> loHead = null, loTail = null;// hi = high 高位子链表                        Node<K,V> hiHead = null, hiTail = null;                        Node<K,V> next;// 开始遍历旧的链表do {                            next = e.next;// 这里是通过 hash & oldCa 可以判断出现在节点是属于高还是低链表的// 0 就是低链表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);// 把低位子链表放入到新数组的索引j的位置if (loTail != null) {                            loTail.next = null;                            newTab[j] = loHead;                        }// 把高位子链表放入到新数组 j + oldCap 索引的位置if (hiTail != null) {                            hiTail.next = null; // 切断链表尾部，避免套娃                            newTab[j + oldCap] = hiHead;                        }                    }                }            }        }return newTab;    }

最后一个put()

1. 插入：如果key不存在，创建新的节点

2. 更新：如果key存在，则覆盖这个key的旧value，并返回旧value

3. 后续：插入节点后可能会出发数组/ 链表初始化或者是扩容等操作

/**     * Associates the specified value with the specified key in this map.     * If the map previously contained a mapping for the key, the old     * value is replaced.     *     * @param key key with which the specified value is to be associated     * @param value value to be associated with the specified key     * @return the previous value associated with {@code key}, or     *         {@code null} if there was no mapping for {@code key}.     *         (A {@code null} return can also indicate that the map     *         previously associated {@code null} with {@code key}.)     */public V put(K key, V value) {return putVal(hash(key), key, value, false, true);    }/**     * Implements Map.put and related methods.     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab：引用 HashMap 的哈希桶数组 table// p：临时保存哈希桶数组中对应索引的首节点// n：哈希桶数组的长度// i：计算出的数组索引位置        Node<K,V>[] tab; Node<K,V> p; int n, i;// 1. 哈希桶未初始化的情况if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length; // resize完成初始化会返回新数组，并获取新数组的长度// 2. 计算数组索引，判断是否为空if ((p = tab[i = (n - 1) & hash]) == null)// 空的话旧直接创建新的节点丢进去了，也不需要处理哈希冲突            tab[i] = newNode(hash, key, value, null);else {// 3. 索引位置不为空的情况，也就是发生了哈希冲突             Node<K,V> e; K k;// 4. 首节点就是目标节点的时候，直接匹配，是不是很熟悉if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;// 5. 首节点是红黑树，则用红黑树的方法插入数据elseif (p instanceof TreeNode)                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 6. 普通链表的时候，遍历数组链表处理else {for (intbinCount=0; ; ++binCount) {if ((e = p.next) == null) {// 尾插法                        p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash); // 这里会尝试树化，容量如果大于等于64就会树化，不然的话就会直接扩容break;                    }// 如果在遍历过程中找到匹配的节点if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))break;// 找不到则直接把 p更新为下一个节点                    p = e;                }            }if (e != null) { // existing mapping for keyVoldValue= e.value;// 7. 允许覆盖旧值if (!onlyIfAbsent || oldValue == null)                    e.value = value;// 后置处理（HashMap 中为空实现，LinkedHashMap 用于维护访问顺序）                afterNodeAccess(e);return oldValue;            }        }// 处理 key 不存在的场景        ++modCount;// 判断当前元素数量是否超过扩容阈值，超过则调用 resize() 扩容if (++size > threshold)            resize();// 后置处理（HashMap 中为空实现，LinkedHashMap 用于维护访问顺序）        afterNodeInsertion(evict);returnnull;    }

写完了让AI帮我收尾

结尾升华：从源码中提炼设计思想与实战建议

这部分是文章的「拔高」，让读者不仅能看懂源码，还能将知识运用到实际开发中。

1. 核心设计思想：

• 空间换时间：通过哈希桶数组和额外的链表 / 红黑树，换取高效的查询 / 插入效率。

• 平衡思想：通过负载因子、阈值等参数，平衡空间利用率和性能。

• 懒加载思想：哈希桶数组、entrySet 等均为懒加载，减少初始化时的资源消耗。

2. 实际开发中的注意事项：

• 合理设置初始容量：如果已知存储数据量，建议设置初始容量为 (预计数据量 / 负载因子) + 1，且向上取整为 2 的幂次，避免频繁扩容。

• 重写 key 类的 hashCode() 和 equals() 方法：必须保证「相等的 key 具有相等的 hashCode」，否则会导致查询不到数据；同时 equals() 要满足自反性、对称性、传递性。

• 避免在并发场景下使用 HashMap：优先选择 ConcurrentHashMap。

• 避免使用可变对象作为 key：如果 key 对象被修改，会导致 hashCode() 和 equals() 结果变化，无法正常查询到对应值。

done

‍