// JDK21 HashMap.java 源码关键常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16，为什么不直接写16？位运算快

static final int MAXIMUM_CAPACITY = 1 << 30;  // 最大容量10亿级别

static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子，这个值是时间/空间的经验最优解

// 链表转红黑树的阈值：链表节点数 > 8
static final int TREEIFY_THRESHOLD = 8;

// 红黑树退化回链表的阈值：红黑树节点数 < 6
static final int UNTREEIFY_THRESHOLD = 6;

// 树化的最小数组长度：数组长度 < 64时优先扩容而不是树化
static final int MIN_TREEIFY_CAPACITY = 64;

负载因子0.75是怎么来的？官方文档的解释是：根据二项式分布统计，0.75是查找性能和空间利用率的最佳平衡点。更小的负载因子（如0.5）空间浪费多，更大的（如1.0）冲突严重。

三、核心源码完整实现解析

3.1 hash()扰动函数——最容易被忽视的细节

package com.laozhang.hashmap;

/**
 * HashMap hash扰动函数深度解析
 * 
 * JDK8的hash()源码只有一行，但里面藏了很多学问
 */
public class HashMapHashDemo {

    /**
     * JDK8 HashMap.hash() 源码复刻
     * 
     * 为什么要做 h ^ (h >>> 16) ？
     * 
     * 原因：HashMap的数组下标计算是 (n-1) & hash
     * 当数组长度n较小（比如默认16）时，(n-1)只有低4位是1，
     * 高位的hash信息完全被丢弃，导致只有低位参与寻址，冲突率极高。
     * 
     * 扰动函数把高16位异或到低16位，让高位信息也参与到下标计算中，
     * 用一次异或操作就大幅降低了哈希冲突概率。
     */
    static final int hash(Object key) {
        int h;
        // null的hash固定为0，所以null键永远在桶0
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 演示扰动函数的效果
     */
    public static void main(String[] args) {
        // 假设数组长度16，下标计算 = (16-1) & hash = 15 & hash
        int n = 16;
        
        String key1 = "name";
        String key2 = "age";
        
        int rawHash1 = key1.hashCode();
        int rawHash2 = key2.hashCode();
        
        int disturbedHash1 = hash(key1);
        int disturbedHash2 = hash(key2);
        
        System.out.println("=== 扰动函数效果演示 ===");
        System.out.printf("key='%s' rawHash=%d rawIndex=%d disturbedHash=%d disturbedIndex=%d%n",
                key1, rawHash1, (n-1) & rawHash1, disturbedHash1, (n-1) & disturbedHash1);
        System.out.printf("key='%s' rawHash=%d rawIndex=%d disturbedHash=%d disturbedIndex=%d%n",
                key2, rawHash2, (n-1) & rawHash2, disturbedHash2, (n-1) & disturbedHash2);

        // 演示为什么数组长度必须是2的幂
        // (n-1) & hash 等价于 hash % n，但位运算比取模快3-4倍
        System.out.println("\n=== 为什么数组长度必须是2的幂 ===");
        for (int cap = 1; cap <= 32; cap++) {
            // HashMap.tableSizeFor() 的逻辑：找到 >= cap 的最小2的幂
            System.out.printf("输入容量=%d 实际容量=%d%n", cap, tableSizeFor(cap));
        }
    }

    /**
     * JDK8 HashMap.tableSizeFor() 源码复刻
     * 
     * 经典的位运算技巧：把最高有效位以下的所有位都填充为1，然后+1
     * 例如：输入10（1010），经过处理变成15（1111），再+1=16（10000）
     */
    static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        // JDK8原始写法更直观：
        // 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;
    }

    static final int MAXIMUM_CAPACITY = 1 << 30;
}

3.2 put()方法完整流程解析

package com.laozhang.hashmap;

import java.util.HashMap;
import java.util.concurrent.ThreadLocalRandom;

/**
 * HashMap put操作全流程模拟
 * 
 * 通过自定义hashCode制造冲突，观察链表转红黑树的过程
 */
public class HashMapPutDemo {

    /**
     * 恶意hashCode类：所有实例返回相同hashCode
     * 用于模拟哈希冲突场景
     */
    static class BadKey {
        private final int id;
        
        BadKey(int id) {
            this.id = id;
        }
        
        @Override
        public int hashCode() {
            // 故意让所有key的hash相同，强制走同一个桶
            return 42;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof BadKey)) return false;
            return id == ((BadKey) o).id;
        }
        
        @Override
        public String toString() {
            return "BadKey(" + id + ")";
        }
    }

    /**
     * 观察HashMap内部结构变化
     * 
     * 注意：这里用反射获取内部状态，仅供学习，生产代码别这么干
     */
    public static void observeHashMapStructure() throws Exception {
        // 初始容量64，确保满足树化条件（MIN_TREEIFY_CAPACITY=64）
        HashMap<BadKey, String> map = new HashMap<>(64);
        
        System.out.println("=== 向同一个桶插入数据，观察链表->红黑树转化 ===");
        
        for (int i = 1; i <= 12; i++) {
            map.put(new BadKey(i), "value-" + i);
            System.out.printf("插入第%d个元素后，map.size()=%d%n", i, map.size());
            
            // 第8->9个元素时，会触发treeifyBin()
            if (i == 8) {
                System.out.println(">>> 下一次插入将触发树化检查！");
            }
        }
        
        // 通过反射查看桶0的节点类型
        var tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);
        
        if (table != null) {
            for (int i = 0; i < table.length; i++) {
                if (table[i] != null) {
                    // 判断是TreeNode还是Node
                    String nodeType = table[i].getClass().getSimpleName();
                    System.out.printf("桶[%d]: 节点类型=%s%n", i, nodeType);
                }
            }
        }
    }

    /**
     * 演示resize扩容时的rehash过程
     * 
     * JDK8的扩容优化：不需要重新计算hash，只需看原hash的新增高位是0还是1
     * - 新增位=0：节点留在原位置
     * - 新增位=1：节点移动到 原位置+oldCap
     */
    public static void demonstrateResize() {
        System.out.println("\n=== 扩容时的节点分布规律 ===");
        System.out.println("原数组长度=16，扩容后=32");
        System.out.println("扩容前后下标变化规律：");
        
        // 模拟几个key在扩容前后的位置变化
        String[] keys = {"hello", "world", "java", "hashmap", "resize"};
        int oldCap = 16;
        int newCap = 32;
        
        for (String key : keys) {
            int h = key.hashCode() ^ (key.hashCode() >>> 16);
            int oldIndex = (oldCap - 1) & h;
            int newIndex = (newCap - 1) & h;
            
            // 关键判断：h & oldCap == 0 说明新增高位是0，位置不变
            boolean staysInPlace = (h & oldCap) == 0;
            
            System.out.printf("key='%s' 旧位置=%d 新位置=%d 位置变了=%b（预期:%s）%n",
                    key, oldIndex, newIndex, !staysInPlace,
                    staysInPlace ? "不变(应=" + oldIndex + ")" : "移动到=" + (oldIndex + oldCap));
        }
    }

    /**
     * 性能基准测试：不同初始容量对put性能的影响
     * 
     * 结论：如果你知道大概要放多少数据，预设容量能节省大量扩容开销
     */
    public static void benchmarkInitialCapacity() {
        int dataSize = 100_000;
        
        // 不预设容量，会经历 16->32->64->...->131072 多次扩容
        long start = System.nanoTime();
        HashMap<Integer, String> map1 = new HashMap<>();
        for (int i = 0; i < dataSize; i++) {
            map1.put(i, "v" + i);
        }
        long cost1 = System.nanoTime() - start;
        
        // 预设合理容量：dataSize/0.75 + 1 ≈ 133334
        // 实际给 dataSize * 4/3 + 1，让HashMap自己调整到最近的2的幂
        start = System.nanoTime();
        HashMap<Integer, String> map2 = new HashMap<>(dataSize * 4 / 3 + 1);
        for (int i = 0; i < dataSize; i++) {
            map2.put(i, "v" + i);
        }
        long cost2 = System.nanoTime() - start;
        
        System.out.printf("%n=== 初始容量对put性能的影响（插入%d个元素）===%n", dataSize);
        System.out.printf("默认容量（会多次扩容）: %.2f ms%n", cost1 / 1_000_000.0);
        System.out.printf("预设合理容量（避免扩容）: %.2f ms%n", cost2 / 1_000_000.0);
        System.out.printf("性能提升: %.1f%%%n", (cost1 - cost2) * 100.0 / cost1);
        // 据我测试，这个场景下预设容量大约能快20-35%
    }

    public static void main(String[] args) throws Exception {
        observeHashMapStructure();
        demonstrateResize();
        benchmarkInitialCapacity();
    }
}

3.3 get()方法——链表与红黑树的不同查找路径

package com.laozhang.hashmap;

import java.util.HashMap;
import java.lang.reflect.Method;

/**
 * 深入理解 HashMap.get() 的完整查找链路
 * 
 * JDK21中 get() 的核心逻辑（精简注释版）：
 * 
 * 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;
 *     // 1. 数组非空且对应桶非空
 *     if ((tab = table) != null && (n = tab.length) > 0 &&
 *         (first = tab[(n - 1) & hash]) != null) {
 *         
 *         // 2. 先检查第一个节点（最常见情况，链表头就是目标）
 *         if (first.hash == hash &&
 *             ((k = first.key) == key || (key != null && key.equals(k))))
 *             return first;
 *         
 *         // 3. 链表/红黑树中继续查找
 *         if ((e = first.next) != null) {
 *             // 3a. 如果是红黑树节点，走树的查找逻辑
 *             if (first instanceof TreeNode)
 *                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
 *             
 *             // 3b. 否则遍历链表
 *             do {
 *                 if (e.hash == hash &&
 *                     ((k = e.key) == key || (key != null && key.equals(k))))
 *                     return e;
 *             } while ((e = e.next) != null);
 *         }
 *     }
 *     return null;
 * }
 */
public class HashMapGetDemo {

    /**
     * 演示equals和hashCode契约对HashMap行为的影响
     * 
     * 经典陷阱：只重写hashCode不重写equals，或者只重写equals不重写hashCode
     */
    
    // 反例1：只重写hashCode，不重写equals
    static class OnlyHashCode {
        private final int value;
        
        OnlyHashCode(int value) {
            this.value = value;
        }
        
        @Override
        public int hashCode() {
            return value;
        }
        // 没有重写equals，使用Object默认的引用比较
    }
    
    // 反例2：只重写equals，不重写hashCode
    static class OnlyEquals {
        private final int value;
        
        OnlyEquals(int value) {
            this.value = value;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof OnlyEquals)) return false;
            return value == ((OnlyEquals) o).value;
        }
        // 没有重写hashCode，使用Object默认的内存地址哈希
    }
    
    // 正例：同时正确重写hashCode和equals
    static class ProperKey {
        private final int value;
        
        ProperKey(int value) {
            this.value = value;
        }
        
        @Override
        public int hashCode() {
            return Integer.hashCode(value);
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof ProperKey)) return false;
            return value == ((ProperKey) o).value;
        }
    }

    public static void main(String[] args) {
        System.out.println("=== hashCode/equals契约验证 ===\n");
        
        // 测试反例1：只有hashCode
        HashMap<OnlyHashCode, String> map1 = new HashMap<>();
        OnlyHashCode k1a = new OnlyHashCode(1);
        OnlyHashCode k1b = new OnlyHashCode(1); // value相同，但是不同对象
        map1.put(k1a, "first");
        map1.put(k1b, "second"); // 因为equals用引用比较，k1a != k1b，会新增一条记录
        System.out.println("只重写hashCode - map.size()=" + map1.size()); // 输出2，意料之外
        System.out.println("get(k1a)=" + map1.get(k1a)); // first
        System.out.println("get(new OnlyHashCode(1))=" + map1.get(new OnlyHashCode(1))); // null！找不到
        
        // 测试反例2：只有equals
        HashMap<OnlyEquals, String> map2 = new HashMap<>();
        OnlyEquals k2a = new OnlyEquals(1);
        OnlyEquals k2b = new OnlyEquals(1);
        map2.put(k2a, "first");
        map2.put(k2b, "second"); // hashCode不同，落到不同桶，不会覆盖
        System.out.println("\n只重写equals - map.size()=" + map2.size()); // 输出2
        // 虽然k2a.equals(k2b)是true，但HashMap找不到k2b，因为先用hashCode定位桶
        
        // 测试正例
        HashMap<ProperKey, String> map3 = new HashMap<>();
        ProperKey k3a = new ProperKey(1);
        ProperKey k3b = new ProperKey(1);
        map3.put(k3a, "first");
        map3.put(k3b, "second"); // 正确覆盖
        System.out.println("\n正确实现hashCode+equals - map.size()=" + map3.size()); // 输出1
        System.out.println("get(new ProperKey(1))=" + map3.get(new ProperKey(1))); // second，符合预期
    }
}

四、踩坑实录

坑1：并发修改HashMap引发CPU 100%

报错现象：

Exception in thread "Thread-1" java.lang.StackOverflowError
    at java.util.HashMap.get(HashMap.java:...)

或者程序没报错，但某个线程CPU占用突然飙到100%，永远不退出。

根本原因： JDK7的HashMap在扩容时使用头插法，多线程并发扩容会形成链表环。JDK8改成了尾插法，修复了成环问题，但多线程下仍然可能数据丢失。这个坑我在2019年真实踩过，一个Spring Boot服务的线程池任务往同一个HashMap里缓存数据，跑一段时间CPU就飙满，重启就好，循环往复。

具体解法：

// 方案1：换成ConcurrentHashMap（推荐）
Map<String, Object> safeMap = new ConcurrentHashMap<>();

// 方案2：Collections.synchronizedMap（性能差，不推荐）
Map<String, Object> syncMap = Collections.synchronizedMap(new HashMap<>());

// 方案3：读多写少场景用CopyOnWriteArrayList的Map版本思路，或者分段锁

坑2：用可变对象做HashMap的Key

报错现象： 不报错，但get()返回null，明明put进去了。

根本原因： 把一个对象put进HashMap后，修改了该对象影响hashCode的字段，导致下次计算出的桶位置和当初put时不同，get时在新位置找不到。

这个坑我在一个做订单系统的老项目里见过，同事用了一个包含订单状态的自定义对象做缓存Key，改了状态之后缓存永远命中不了。

// 危险示例
List<String> mutableKey = new ArrayList<>(Arrays.asList("a", "b"));
HashMap<List<String>, String> map = new HashMap<>();
map.put(mutableKey, "value");

mutableKey.add("c"); // 修改了key，hashCode变了！

System.out.println(map.get(mutableKey)); // null，找不到了！
System.out.println(map.get(Arrays.asList("a", "b"))); // null，原位置也找不到了

// 正确做法：用不可变对象做key
// String、Integer等不可变类是天然安全的key

坑3：HashMap初始容量设置不当导致频繁扩容

现象： 程序运行没问题，但GC日志里full GC频繁，内存抖动严重。

根本原因： 没有预设合理的初始容量，HashMap从16开始反复扩容，每次扩容都会创建新的数组并复制所有数据，产生大量临时对象，触发GC。

具体解法：

// 错误写法：知道要放10000个元素，但用默认容量
HashMap<String, Object> bad = new HashMap<>(); // 会扩容多次

// 正确写法：用 Guava 的 Maps.newHashMapWithExpectedSize() 
// 或者手动计算：expectedSize / 0.75 + 1
int expectedSize = 10000;
HashMap<String, Object> good = new HashMap<>((int)(expectedSize / 0.75) + 1);

// 更优雅的写法（Guava）：
// HashMap<String, Object> guavaWay = Maps.newHashMapWithExpectedSize(10000);

坑4：Integer key在[-128, 127]范围外的装箱陷阱

现象：

HashMap<Integer, String> map = new HashMap<>();
map.put(200, "hello");
// 某些情况下以下代码返回null
Integer key = 200;
System.out.println(map.get(key)); // 这个没问题
// 但如果这样写：
System.out.println(map.get(new Integer(200))); // JDK9前可能有问题

根本原因： Integer的缓存范围是[-128, 127]，范围外的Integer每次new都是新对象。但HashMap用的是equals比较，Integer.equals()比较的是值，所以其实不会有问题。

这个坑是假坑，但我见过很多人被这个问题绕晕，搞清楚HashMap用equals而不是==比较key之后就豁然开朗了。

五、总结与延伸

三条核心观点落地拿走：

1. HashMap的三层结构各司其职：数组提供O(1)定位，链表解决哈希冲突，红黑树在极端冲突时保底O(log n)。理解三层结构的协作，才能在调优时知道从哪里下手。

2. 两个关键阈值背后都有数学依据：8转树是泊松分布的极小概率点，6退化是防止链表树之间频繁震荡的缓冲区间，0.75负载因子是时间空间的经验最优解。不是随便定的。

3. 初始容量是最容易被忽视的性能优化点：如果你能预估HashMap的数据量，给一个合理的初始容量（expectedSize/0.75+1），避免多次扩容，在高并发批量写入场景下性能提升显著，GC压力也会明显降低。

下一篇我们聊ConcurrentHashMap从JDK7到JDK21的进化史，看看JDK7的分段锁是怎么被JDK8的CAS+synchronized替代的，以及JDK21里又做了哪些新优化。