CodeWalk

手写HashMap：底层数组+链表+红黑树实现

作者：Yahuda · 2026-05-30 12:55

请手写一个简化版HashMap，要求实现put、get、remove和扩容机制。底层使用数组+链表+红黑树结构。解释HashMap的核心设计要点：哈希函数的设计、链地址法解决冲突、阈值和树化、扩容机制（resize）和rehash过程。

回答

Yahuda

核心设计

public class SimpleHashMap<K, V> {
    static final int DEFAULT_CAPACITY = 16;
    static final float LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    
    Node<K,V>[] table;
    int size;
    int threshold;
    
    static class Node<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        // 构造方法、getter/setter
    }
    
    // 哈希函数
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    public V put(K key, V value) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;  // 取模优化
        
        Node<K,V> node = table[index];
        if (node == null) {
            table[index] = new Node<>(hash, key, value, null);
        } else {
            // 链表遍历
            Node<K,V> prev = null;
            while (node != null) {
                if (node.hash == hash && Objects.equals(node.key, key)) {
                    V old = node.value;
                    node.value = value;
                    return old;
                }
                prev = node;
                node = node.next;
            }
            prev.next = new Node<>(hash, key, value, null);
        }
        
        if (++size > threshold) {
            resize();
        }
        return null;
    }
    
    public V get(Object key) {
        int hash = hash(key);
        Node<K,V> node = table[(table.length - 1) & hash];
        while (node != null) {
            if (node.hash == hash && Objects.equals(node.key, key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }
    
    void resize() {
        // 扩容为2倍，rehash重新分配
        Node<K,V>[] old = table;
        table = new Node[old.length * 2];
        threshold = (int)(table.length * LOAD_FACTOR);
        
        for (Node<K,V> node : old) {
            while (node != null) {
                Node<K,V> next = node.next;
                int index = (table.length - 1) & node.hash;
                node.next = table[index];
                table[index] = node;
                node = next;
            }
        }
    }
}

关键设计要点

  1. 哈希函数：hashCode() ^ (hashCode >>> 16) 将高位扩散到低位，减少碰撞
  2. 容量为2的幂：(n - 1) & hash 替代 % n（位运算更快）
  3. 阈值：capacity * loadFactor，0.75是时间和空间的平衡
  4. 树化：链表长度>8且总容量≥64时，链表转为红黑树（O(n)→O(log n)）
  5. 扩容rehash：容量翻倍后，元素的新位置要么在原位置，要么在原位置+旧容量（利用2的幂特性优化rehash）