#HashMap 源码深度解析

// JDK 7 HashMap 核心结构
transient Entry<K, V>[] table;

static class Entry<K, V> implements Map.Entry<K, V> {
    final K key;
    V value;
    Entry<K, V> next;  // 链表指针
    int hash;          // key 的 hash 值
}

// JDK 8 HashMap 核心结构
transient Node<K, V>[] table;

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red;
}

// 最坏情况：所有 key 都 hash 到同一个桶
Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put(0, "value" + i); // 所有 key 的 hash 都是 0
}
// 此时 get/put 都是 O(n)，10000 次操作

// JDK 8 HashMap.hash()
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 假设 key 的 hashCode 是 0xAAAAAAAA = 10101010101010101010101010101010
// 直接用 hash & (n-1) 取模

// 如果 n = 16，n-1 = 0xF = 00001111
// hash & 0xF 只会用到 hash 的低 4 位！

// 结果：无论高位如何，只有低 4 位参与运算
// 冲突严重！

// (h = key.hashCode()) ^ (h >>> 16)
// 高 16 位和低 16 位异或
// 让高位也参与到 index 计算中

// 举例：
// hashCode = 0xAAAA0000
// hash = 0xAAAA0000 ^ 0x0000AAAA = 0xAAA0AAAA
// 现在高低位混合了

// HashMap 构造函数可以指定容量
public HashMap(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

// 但 HashMap 会把容量调整为 2 的幂次
public HashMap(int initialCapacity, float loadFactor) {
    // ...
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;  // 找第一个 >= initialCapacity 的 2 的幂次
    // initialCapacity=10 → capacity=16
    // initialCapacity=15 → capacity=16
    // initialCapacity=16 → capacity=16
    // initialCapacity=17 → capacity=32
}

// index 计算方式
int index = (n - 1) & hash;

// n = 16 = 0b10000
// n - 1 = 15 = 0b01111

// 如果 n 是 2 的幂次，n-1 的二进制全是 1
// 例如：
// n-1 = 15 = 0b01111 (4 个 1)
// n-1 = 31 = 0b11111 (5 个 1)

// hash & (n-1) 等价于 hash % n
// 但 & 比 % 快 10 倍！

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;

    // 1. 如果 table 为空或长度为 0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 计算 index，如果该桶为空，创建普通节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    else {
        // 3. 该桶已有元素，处理哈希冲突
        Node<K,V> e;
        K k;

        // 情况 A：桶中第一个元素的 key 和插入 key 相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // 情况 B：桶是红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // 情况 C：桶是链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 遍历到链表尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);

                    // 链表长度 >= 8，树化
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }

                // 链表中找到相同 key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;

                p = e;
            }
        }

        // 4. 找到了已存在的 key，更新 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    // 5. 修改次数 +1
    ++modCount;

    // 6. 如果 size 超过阈值，扩容
    if (++size > threshold)
        resize();

    afterNodeInsertion(evict);
    return null;
}

static final int TREEIFY_THRESHOLD = 8;   // 链表长度 >= 8，树化
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树节点 <= 6，退链表

// MIN_TREEIFY_CAPACITY = 64
// 只有容量 >= 64 时才会树化，否则只扩容

// 在负载因子 0.75 下，每个桶的平均元素数是 0.75
// 链表长度 k 的概率服从泊松分布

// P(X=k) = (λ^k * e^(-λ)) / k!
// λ = 0.75

// 计算：
// P(k=8) = (0.75^8 * e^(-0.75)) / 8!
//        ≈ 0.0000001

// 也就是说，链表长度达到 8 的概率是千万分之一！

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index;
    Node<K,V> e;

    // 如果容量 < 64，优先扩容而非树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();  // 扩容，而不是树化
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 树化
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify();
    }
}

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) {
            // 红黑树
            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;
}

static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

// threshold = capacity * loadFactor
// 默认：capacity=16, loadFactor=0.75 → threshold=12

// 什么时候扩容？
// size = 13 > threshold = 12 → 扩容

// ❌ 错误 1：循环内不预设容量
Map<String, Order> orders = new HashMap<>();
for (Order order : orderList) {
    orders.put(order.getId(), order);
}
// 触发多次扩容，每次都要 rehash

// ✅ 正确：预设容量
Map<String, Order> orders = new HashMap<>(orderList.size());

// ❌ 错误 2：用可变对象作 key
Map<List<Integer>, String> map = new HashMap<>();
List<Integer> key = new ArrayList<>();
key.add(1);
map.put(key, "value");
key.add(2); // 修改了 key！
// map.get(key) 找不到值了！

// ✅ 正确：用不可变对象作 key
Map<String, String> map = new HashMap<>();

// 恶意攻击：构造大量 hash 相同的 key
for (int i = 0; i < 100000; i++) {
    map.put(hackKey(i), "value");
}

// JDK 8 解决方案：
// 1. 当链表长度 >= 8 时树化
// 2. 防止链表退化到 O(n)
// 3. 但仍然消耗 CPU

// ✅ 好 key 的特点：
// 1. hashCode() 计算简单，分布均匀
// 2. equals() 比较高效
// 3. 不可变（hashCode 不会变）

// 推荐用作 key 的类型：
// - String
// - Integer/Long 等包装类型
// - 不可变的自定义类（所有字段 final）

// 不推荐用作 key 的类型：
// - 可变对象（ArrayList 等）
// - 复杂的自定义对象