一、项目背景详细介绍

HashMap 是 Java 使用最广泛的集合之一，支持 以键（Key）为索引的 O(1) 平均时间复杂度 的增删查改。其高性能来自以下“底层魔法”：

  1. 数组 + 链表/树：底层是桶数组，每个桶里用链表（JDK8+ 在链表过长时转红黑树）存放冲突的键值对。

  2. 高效寻址：通过扰动函数提升 hash 分布，再用 (n-1) & hash（n 为 2 的幂）快速定位桶下标。

  3. 负载因子与阈值：当 size > capacity * loadFactor 时触发扩容，把元素再散列到新数组（rehash）。

  4. 扩容迁移优化：JDK8 利用 oldCap 的二进制位把一个桶中的节点直接拆分到新数组的 index 或 index + oldCap 两个位置，避免对每个节点重新计算完整哈希，提高扩容性能。

理解并掌握这些机制，有助于在实际开发中正确地使用 HashMap，并在必要时写出贴合业务的自定义哈希容器。

二、项目需求详细介绍

我们实现一个教学版 MyHashMap<K,V>，满足：

  • 核心操作：put(K,V)、get(K)、remove(K)、size()、containsKey(K)、containsValue(V)、clear()；

  • 泛型支持：K、V 泛型；

  • 负载因子 与 自动扩容；

  • 扰动函数 与 位运算定位桶；

  • 链地址法（单链表） 处理冲突；

  • 扩容迁移（JDK8 拆分技巧），把一个桶拆到 index 与 index + oldCap；

  • 边界处理：null key、null value、重复 put 覆盖、删除更新 size、清空等。

注：本文不实现桶内红黑树（treeify），但代码中留出扩展点。

三、相关技术详细介绍

1) 扰动函数（hash spread）

原始 key.hashCode() 高位信息弱、低位更常变化。数组寻址只看低位（(n-1)&hash），如果高位信息不用会导致碰撞增多。JDK 通过：



h ^ (h >>> 16) 


把高位扰动到低位，提高桶分布均匀性。


2) 桶数组 + 链地址法


底层是 Node<K,V>[] table，元素 hash 到某个桶，若该桶有元素则头插/尾插为链表节点（JDK8 默认头插→后改为尾插？JDK 实现细节和版本略有差异，本文采用尾插，便于阅读）。


3) 寻址 (n-1)&hash


当 n 是 2 的幂，(n-1)&hash 等价于 hash % n 且更快；要求容量始终保持 2 的幂。


4) 负载因子 loadFactor 与扩容阈值 threshold


    
 
  • 
  
    threshold = capacity * loadFactor
    • 
 
  • 
  
    当元素数 size > threshold 时，扩容为两倍，并迁移所有节点。
    • 



5) JDK8 扩容迁移拆分技巧


    
 
  • 
  
    设旧容量 oldCap，旧桶下标 i。扩容后新容量 newCap = 2*oldCap。
    • 
 
  • 
  
    旧桶的节点会分裂到 i 或 i + oldCap 两个位置：
    
  
      
   
    • 
    
      判断条件是看该节点 hash 的 oldCap 位是否为 0 或 1。
      • 
   
    • 
    
      这样无需重算完整下标，只靠一位就能把一条链拆两条链，性能更高。
      • 
  
    • 





四、实现思路详细介绍


    
 
  1. 
  
    核心存储结构
    2. 



static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
private Node<K,V>[] table;
private int size;
private int threshold;
private final float loadFactor;



    
 
  1. 
  
    初始化与容量扩容
    
  
      
   
    • 
    
      默认容量 DEFAULT_INITIAL_CAPACITY = 16（2 的幂），默认负载因子 0.75f；
      • 
   
    • 
    
      threshold = capacity * loadFactor；
      • 
   
    • 
    
      resize()：新建 2 倍数组，逐桶执行“低位链/ 高位链”拆分并安放。
      • 
  
    2. 
 
  2. 
  
    hash 扰动
    
  
    
  
    static final int spread(int h) { return h ^ (h >>> 16); } 
    3. 
 
  3. 
  
    put
    
  
      
   
    • 
    
      初始化表；
      • 
   
    • 
    
      计算 hash 和 index；
      • 
   
    • 
    
      若桶空，直接放；
      • 
   
    • 
    
      若桶内有链：
      
    
        
     
      • 
      
        链上查找相同 key（== 或 equals）；
        • 
     
      • 
      
        已存在则覆盖；
        • 
     
      • 
      
        不存在则尾插；
        • 
    
      • 
   
    • 
    
      插入后检查 size > threshold 则 resize()。
      • 
  
    4. 
 
  4. 
  
    get
    
  
      
   
    • 
    
      定位桶，遍历链；
      • 
   
    • 
    
      hash 相等 + key 相等（== 或 equals）即返回 value。
      • 
  
    5. 
 
  5. 
  
    remove
    
  
      
   
    • 
    
      定位桶，遍历链，维护前驱删除；
      • 
   
    • 
    
      删除成功 size--。
      • 
  
    6. 
 
  6. 
  
    containsKey / containsValue
    
  
      
   
    • 
    
      containsKey：借助 get(key) != null（注意 null value 的场景，需精确匹配 key）。
      • 
   
    • 
    
      containsValue：遍历数组 + 链。
      • 
  
    7. 
 
  7. 
  
    clear
    
  
      
   
    • 
    
      Arrays.fill(table, null); size=0;（保留容量与阈值，便于复用）。
      • 
  
    8. 





五、完整实现代码


// 文件：MyHashMap.java
import java.util.Arrays;
import java.util.Objects;

public class MyHashMap<K, V> {

    /** 默认初始容量（必须是2的幂） */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    /** 最大容量（与JDK一致的上限选择，可按需调整） */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /** 默认负载因子 */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** 桶数组（哈希表） */
    transient Node<K, V>[] table;
    /** 已存放的键值对数量 */
    transient int size;
    /** 扩容阈值 = capacity * loadFactor */
    int threshold;
    /** 负载因子 */
    final float loadFactor;

    /** 链表节点结构（教学版，不实现树节点） */
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override public String toString() {
            return key + "=" + value;
        }
    }

    // ===== 构造与初始化 =====
    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(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;
        int cap = tableSizeFor(initialCapacity); // 向上取最近2的幂
        this.threshold = (int) (cap * loadFactor);
        this.table = (Node<K, V>[]) new Node[cap];
    }

    /** 计算 >= cap 的最小2的幂（与JDK类似） */
    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;
    }

    /** 扰动函数：将高位参与到低位，改善分布 */
    static final int spread(int h) {
        return h ^ (h >>> 16);
    }

    // ===== 基本API =====

    /** 放入键值对（存在则覆盖），返回旧值或null */
    public V put(K key, V value) {
        return putVal(spread(hash(key)), key, value);
    }

    /** 根据 key 获取 value（找不到返回null） */
    public V get(Object key) {
        Node<K, V> e = getNode(spread(hash(key)), key);
        return e == null ? null : e.value;
    }

    /** 删除键，返回旧值或null */
    public V remove(Object key) {
        Node<K, V> e = removeNode(spread(hash(key)), key);
        return e == null ? null : e.value;
    }

    /** 是否包含指定key（注意：即便value为null也能通过key定位） */
    public boolean containsKey(Object key) {
        return getNode(spread(hash(key)), key) != null;
    }

    /** 是否包含某个value（需要全表扫描） */
    public boolean containsValue(Object value) {
        Node<K, V>[] tab = table;
        if (tab == null) return false;
        for (Node<K, V> head : tab) {
            for (Node<K, V> e = head; e != null; e = e.next) {
                if (Objects.equals(e.value, value)) return true;
            }
        }
        return false;
    }

    /** 当前键值对数量 */
    public int size() { return size; }

    /** 是否为空 */
    public boolean isEmpty() { return size == 0; }

    /** 清空但保留容量与阈值 */
    public void clear() {
        Node<K, V>[] tab = table;
        if (tab != null && size > 0) {
            Arrays.fill(tab, null);
            size = 0;
        }
    }

    // ===== 内部核心实现 =====

    /** 统一计算 hash（支持 null key，仿照JDK把 null 定位到 0 桶） */
    static final int hash(Object key) {
        return (key == null) ? 0 : key.hashCode();
    }

    /** put 内核 */
    private V putVal(int hash, K key, V value) {
        Node<K, V>[] tab = table;
        if (tab == null || tab.length == 0) {
            tab = resize(); // 惰性初始化
        }
        int n = tab.length;
        int i = (n - 1) & hash; // 位运算定位桶
        Node<K, V> first = tab[i];
        if (first == null) {
            // 桶为空，直接放
            tab[i] = new Node<>(hash, key, value, null);
            if (++size > threshold) resize();
            return null;
        } else {
            // 桶非空，遍历链查重或尾插
            Node<K, V> e = first;
            Node<K, V> last = null;
            // 查找是否已存在相同key
            while (e != null) {
                if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                    V old = e.value;
                    e.value = value;
                    return old;
                }
                last = e;
                e = e.next;
            }
            // 未命中，执行尾插
            last.next = new Node<>(hash, key, value, null);
            if (++size > threshold) resize();
            return null;
        }
    }

    /** get 内核：根据 hash 和 key 在桶内找节点 */
    private Node<K, V> getNode(int hash, Object key) {
        Node<K, V>[] tab = table;
        if (tab == null || tab.length == 0) return null;
        int n = tab.length;
        Node<K, V> e = tab[(n - 1) & hash];
        while (e != null) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                return e;
            }
            e = e.next;
        }
        return null;
    }

    /** remove 内核：删除节点并返回它 */
    private Node<K, V> removeNode(int hash, Object key) {
        Node<K, V>[] tab = table;
        if (tab == null || tab.length == 0) return null;
        int n = tab.length;
        int idx = (n - 1) & hash;
        Node<K, V> prev = null, e = tab[idx];
        while (e != null) {
            Node<K, V> next = e.next;
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                if (prev == null) tab[idx] = next; else prev.next = next;
                size--;
                e.next = null;
                return e;
            }
            prev = e;
            e = next;
        }
        return null;
    }

    /** 扩容：2倍容量 + 按 JDK8 思路拆分迁移（低/高位链） */
    private Node<K, V>[] resize() {
        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 {
                newCap = oldCap << 1; // *2
                newThr = (int) (newCap * loadFactor);
            }
        } else {
            // 首次初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int) (DEFAULT_INITIAL_CAPACITY * loadFactor);
        }

        threshold = newThr;
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        table = newTab;

        // 迁移：把每个桶拆成低位链/高位链
        if (oldTab != null) {
            for (int i = 0; i < oldCap; i++) {
                Node<K, V> e = oldTab[i];
                if (e == null) continue;
                oldTab[i] = null; // 帮助GC

                // 如果该桶只有一个节点，直接放
                if (e.next == null) {
                    int idx = (e.hash & (newCap - 1));
                    newTab[idx] = e;
                } else {
                    // 把旧链拆成两条：低位链(lo) 和 高位链(hi)
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        // 关键：用 oldCap 位判断新位置是 i 还是 i + oldCap
                        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;
                        }
                        e = next;
                    } while (e != null);

                    if (loTail != null) {
                        loTail.next = null;
                        newTab[i] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[i + oldCap] = hiHead;
                    }
                }
            }
        }
        return newTab;
    }

    @Override
    public String toString() {
        if (table == null) return "{}";
        StringBuilder sb = new StringBuilder("{");
        boolean first = true;
        for (Node<K, V> head : table) {
            for (Node<K, V> e = head; e != null; e = e.next) {
                if (!first) sb.append(", ");
                sb.append(e.key).append("=").append(e.value);
                first = false;
            }
        }
        return sb.append("}").toString();
    }

    // ===== 简单测试 =====
    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>(4, 0.75f);

        System.out.println("== put ==");
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);
        map.put("D", 4); // 触发扩容在插入E/F后更明显
        map.put("E", 5);
        map.put("F", 6);

        System.out.println("size = " + map.size());
        System.out.println("map  = " + map);

        System.out.println("\n== get ==");
        System.out.println("get A -> " + map.get("A"));
        System.out.println("get Z -> " + map.get("Z"));

        System.out.println("\n== overwrite ==");
        System.out.println("put A=100 (old=" + map.put("A", 100) + ")");
        System.out.println("get A -> " + map.get("A"));
        System.out.println("size = " + map.size());

        System.out.println("\n== remove ==");
        System.out.println("remove C -> " + map.remove("C"));
        System.out.println("remove C -> " + map.remove("C"));
        System.out.println("size = " + map.size());
        System.out.println("map  = " + map);

        System.out.println("\n== contains ==");
        System.out.println("containsKey(B) -> " + map.containsKey("B"));
        System.out.println("containsValue(6) -> " + map.containsValue(6));
        System.out.println("containsValue(3) -> " + map.containsValue(3));

        System.out.println("\n== null key/value ==");
        map.put(null, 999);
        map.put("NULLV", null);
        System.out.println("get null -> " + map.get(null));
        System.out.println("get NULLV -> " + map.get("NULLV"));
        System.out.println("map = " + map);

        System.out.println("\n== clear ==");
        map.clear();
        System.out.println("size = " + map.size());
        System.out.println("map  = " + map);
    }
}



六、代码详细解读（逐方法/逐机制）


1) 构造与初始化


    
 
  • 
  
    tableSizeFor(cap)：把任意初始容量上调为最近的 2 的幂，以便后续 (n-1)&hash。
    • 
 
  • 
  
    threshold = capacity * loadFactor：控制扩容时机。
    • 
 
  • 
  
    默认构造器使用 DEFAULT_LOAD_FACTOR，并在首次 put 时触发 resize() 进行惰性初始化。
    • 



2) 扰动函数 spread(int h)




h ^ (h >>> 16) 


    
 
  • 
  
    把高位信息 XOR 到低位，改善桶分布；
    • 
 
  • 
  
    与 JDK 的思想一致，避免仅用 hashCode 低位导致的碰撞集中。
    • 



3) put 流程（putVal）


    
 
  • 
  
    定位桶：int i = (n - 1) & hash;
    • 
 
  • 
  
    桶为空：新建节点放入；
    • 
 
  • 
  
    桶非空：
    
  
      
   
    • 
    
      遍历链，若找到同 key，直接覆盖 value 返回旧值；
      • 
   
    • 
    
      否则 尾插 新节点；
      • 
  
    • 
 
  • 
  
    越过阈值：size++ 后判断 > threshold 则 resize()。
    • 




 
备注：JDK 里有“treeifyBin”的逻辑（当桶内链表长度超过 8 且容量达到 64 以上时转红黑树），本文为了教学简化未实现，便于专注哈希与扩容机制。




4) get 流程（getNode）


    
 
  • 
  
    通过 (n-1)&hash 定位桶，遍历链；
    • 
 
  • 
  
    相等判断：先比 hash，再比 ==，最后 equals；
    • 
 
  • 
  
    支持 null key，hash(null)=0，定位到 0 桶。
    • 



5) remove 流程（removeNode）


    
 
  • 
  
    定位桶、遍历链并维护 prev；
    • 
 
  • 
  
    断链、size--、返回被删节点；
    • 
 
  • 
  
    若重复删除同键，第二次返回 null。
    • 



6) 扩容 resize（JDK8 拆分迁移）


    
 
  • 
  
    新容量 newCap = oldCap << 1；
    • 
 
  • 
  
    拆分：旧桶链表按 (e.hash & oldCap) 拆成低位链（落到原 i）和高位链（落到 i + oldCap）。
    
  
      
   
    • 
    
      原理：当容量从 oldCap 翻倍到 newCap=oldCap*2 时，只有一个新高位参与索引，即 oldCap 位。如果该位为 0，索引不变；若为 1，新索引 = 原索引 + oldCap。
      • 
  
    • 
 
  • 
  
    这样避免为每个节点完全重算 (newCap-1)&hash，性能优雅。
    • 



7) 其它 API


    
 
  • 
  
    containsKey：通过 getNode 精确匹配 key；
    • 
 
  • 
  
    containsValue：全表扫描，Objects.equals 比较 value；
    • 
 
  • 
  
    clear：仅清表与置 size=0，保留容量与阈值，后续复用数组避免频繁分配。
    • 





七、项目详细总结


    
 
  • 
  
    我们从零实现了一个教学版 HashMap，覆盖了 JDK HashMap 的核心思想：
    
  
      
   
    1. 
    
      扰动函数 改善桶分布；
      2. 
   
    2. 
    
      数组 + 链表 解决冲突；
      3. 
   
    3. 
    
      位运算寻址 (n-1)&hash（容量 2 的幂）；
      4. 
   
    4. 
    
      负载因子 & 扩容阈值 控制扩容时机；
      5. 
   
    5. 
    
      JDK8 拆分迁移 在扩容时将旧桶链表按 oldCap 位切分到 i 与 i+oldCap，高效 rehash。
      6. 
  
    • 
 
  • 
  
    运行 main 可检验 插入 / 覆盖 / 查找 / 删除 / 扩容 / null key/value / 清空 的行为。
    • 
 
  • 
  
    与工业级 JDK HashMap 相比，我们移除了树化，以换取可读性与教学性；但保留了最关键的性能思路。
    • 





八、常见问题（FAQ）


Q1：为什么容量必须是 2 的幂？

  A：为了使用 (n-1)&hash 快速、均匀地取模；若容量非 2 的幂，分布会变差且不能用简单位运算。


Q2：为什么需要扰动函数？

  A：仅用 hashCode 的低位寻址可能导致碰撞集中，扰动把高位混合到低位，使分布更均匀。


Q3：负载因子设多少合适？

  A：0.75 是经验上性能与空间的均衡点；越大空间更省但碰撞更多，越小碰撞更少但空间更费。


Q4：为什么不实现树化（红黑树）？

  A：教学版更关注哈希与扩容的底层机制。树化是针对极端碰撞的尾部优化，实现较复杂，可作为后续扩展。


Q5：containsKey 用 get(key) != null 会误判吗？

  A：若允许 null value，get(key) 可能返回 null（键存在但值为 null），因此本实现使用 getNode 精确判断键是否存在，避免误判。


Q6：扩容为什么会“重新散列”？

  A：因为索引是 (capacity-1)&hash，当容量变化后，同一 hash 的索引也会改变，必须迁移到新桶。




九、扩展方向与性能优化


    
 
  1. 
  
    桶内红黑树（Treeify/Untreeify）
    
  
      
   
    • 
    
      当单桶链表长度超过阈值（如 8）且容量足够（如 ≥64），把链表转为红黑树；
      • 
   
    • 
    
      当删除后树节点变少可退回链表；
      • 
   
    • 
    
      可显著改善极端碰撞场景。
      • 
  
    2. 
 
  2. 
  
    并发支持
    
  
      
   
    • 
    
      基于段（Segment）或分区锁实现 ConcurrentHashMap 风格的并行扩展；
      • 
   
    • 
    
      读写时防止数据竞争与指令重排带来的可见性问题。
      • 
  
    3. 
 
  3. 
  
    定制哈希策略
    
  
      
   
    • 
    
      为热路径对象定制更好的 hashCode() 或单独的 Hasher；
      • 
   
    • 
    
      对热点 key 做缓存（如二级索引）。
      • 
  
    4. 
 
  4. 
  
    对象池/内存复用
    
  
      
   
    • 
    
      大量短生命周期的 map 可配合对象池减少 GC 压力；
      • 
   
    • 
    
      节点结构压缩（如 key/value primitive 专用实现）以提高缓存友好性。
      • 
  
    5. 
 
  5. 
  
    溢出/攻击防护
    
  
      
   
    • 
    
      防止恶意构造大量碰撞 key（DoS），必要时强制树化或切换更强 hash。
      • 
  
    6. 

 
  

        # 哈希算法
      
        # 算法
      
        # java
      
  
 
 Logo 
AI Agent技术社区
 
Agent 垂直技术社区，欢迎活跃、内容共建。
 
 
  
更多推荐
  
cover
 
Hermes Agent 搭建全流程：从本机试跑到可持续运行的个人 AI Agent
 
 
avatar AI Agent技术社区
 
cover
 
AI Agent 工程实践（06）：Knowledge 如何演化成 Rules？
 
 
avatar AI Agent技术社区
 
cover
 
OpenClaw登顶GitHub之后：AI Agent的“平民化”时刻来了吗？
 
 
avatar AI Agent技术社区