HashMap 详解

// 传统方式：hash % length（取模，效率低）
int index = hash % length;

// HashMap 方式：hash & (length - 1)（位与，效率高）
// 仅在 length = 2^n 时等价于 hash % length
int index = hash & (length - 1);

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

// JDK 8: 尾插法
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);  // 追加到尾部
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);  // 达到阈值，树化
        break;
    }
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
        break;  // 找到相同 key，替换
    p = e;
}

// JDK 7: 头插法（有死循环风险）
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);  // 新节点插入头部
    size++;
}

static final int TREEIFY_THRESHOLD = 8;   // 链表长度 ≥ 8 触发树化判断
static final int MIN_TREEIFY_CAPACITY = 64; // 数组长度 ≥ 64 才真正树化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();  // 数组太小 → 优先扩容而非树化
    // ... 真正树化
}

// 正确的重写方式（飞翔科技员工类）
class Employee {
    private String id;    // 工号，唯一标识
    private String name;

    @Override
    public int hashCode() {
        return Objects.hash(id);  // 只使用决定唯一性的字段
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee)) return false;
        Employee other = (Employee) o;
        return Objects.equals(this.id, other.id);
    }
}

// JDK 8 resize() 中节点迁移的核心代码
Node<K,V> loHead = null, loTail = null;  // 保持原索引的链表
Node<K,V> hiHead = null, hiTail = null;  // 移动到新索引（index + oldCap）的链表

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        // hash & oldCap == 0 → 索引不变
        if (loTail == null) loHead = e;
        else loTail.next = e;
        loTail = e;
    } else {
        // hash & oldCap != 0 → 索引变为 index + oldCap
        if (hiTail == null) hiHead = e;
        else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

newTab[j] = loHead;           // 原位置
newTab[j + oldCap] = hiHead;  // 新位置

import java.util.*;

/**
 * 场景：飞翔科技的人事系统需要根据工号快速查找员工信息。
 * 大翔要求系统在 10 万员工规模下，查询响应时间不超过 1ms。
 * 白歌选择了 HashMap，小崔负责实现基本功能，孔蓝负责边界测试。
 */
public class FeiXiangEmployeeManager {
    // ------ 员工实体（不可变，适合做 key） ------
    static class Employee {
        private final String id;   // 工号（唯一标识）
        private final String name;
        private final String department;
        private final double salary;

        public Employee(String id, String name, String department, double salary) {
            this.id = id;
            this.name = name;
            this.department = department;
            this.salary = salary;
        }

        // hashCode 和 equals 只依赖 id —— 工号决定了员工身份
        @Override
        public int hashCode() {
            return Objects.hash(id);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Employee)) return false;
            Employee employee = (Employee) o;
            return Objects.equals(id, employee.id);
        }

        public String getId() { return id; }
        public String getName() { return name; }

        @Override
        public String toString() {
            return String.format("%s | %s | %s | ¥%.0f", id, name, department, salary);
        }
    }

    public static void main(String[] args) {
        // ========== 1. 创建 HashMap ==========
        HashMap<String, Employee> employeeMap = new HashMap<>(16, 0.75f);

        // ========== 2. put：录入员工信息 ==========
        employeeMap.put("EMP001", new Employee("EMP001", "大翔", "管理层", 80000));
        employeeMap.put("EMP002", new Employee("EMP002", "白歌", "技术部", 35000));
        employeeMap.put("EMP003", new Employee("EMP003", "小崔", "技术部", 12000));
        employeeMap.put("EMP004", new Employee("EMP004", "孔蓝", "测试部", 15000));
        employeeMap.put("EMP005", new Employee("EMP005", "Frank", "市场部", 22000));
        employeeMap.put("EMP006", new Employee("EMP006", "黄俪", "人事部", 18000));

        System.out.println("=== 飞翔科技员工信息管理系统 ===");
        System.out.println("员工总数: " + employeeMap.size());

        // ========== 3. get：根据工号查询 ==========
        System.out.println("\n--- 工号查询 ---");
        System.out.println("EMP001: " + employeeMap.get("EMP001"));
        System.out.println("EMP003: " + employeeMap.get("EMP003"));
        System.out.println("EMP999（不存在）: " + employeeMap.get("EMP999"));

        // 安全的获取方式（JDK 8）
        Employee defaultEmp = new Employee("UNKNOWN", "未知", "无", 0);
        System.out.println("EMP002 安全获取: " + employeeMap.getOrDefault("EMP002", defaultEmp));
        System.out.println("EMP999 安全获取: " + employeeMap.getOrDefault("EMP999", defaultEmp));

        // ========== 4. containsKey / containsValue ==========
        System.out.println("\n--- 存在性判断 ---");
        System.out.println("包含工号 EMP001？ " + employeeMap.containsKey("EMP001"));
        System.out.println("包含工号 EMP999？ " + employeeMap.containsKey("EMP999"));

        // ========== 5. 遍历方式对比 ==========
        System.out.println("\n=== 遍历方式 ===");

        // 方式一：entrySet —— 推荐，一次遍历拿到 key 和 value
        System.out.println("--- entrySet（推荐） ---");
        for (Map.Entry<String, Employee> entry : employeeMap.entrySet()) {
            System.out.println("  " + entry.getKey() + " → " + entry.getValue().getName());
        }

        // 方式二：JDK 8 forEach + Lambda —— 最简洁
        System.out.println("\n--- forEach（JDK 8 Lambda） ---");
        employeeMap.forEach((id, emp) ->
            System.out.println("  " + id + " → " + emp.getName())
        );

        // 方式三：keySet + get —— 不推荐（每次 get 都是一次查找）
        System.out.println("\n--- keySet + get（不推荐，多一次查找） ---");
        for (String id : employeeMap.keySet()) {
            System.out.println("  " + id + " → " + employeeMap.get(id).getName());
        }

        // ========== 6. 替换操作 ==========
        System.out.println("\n--- 替换操作 ---");
        employeeMap.replace("EMP003", new Employee("EMP003", "小崔（已晋升）", "技术部", 20000));
        System.out.println("替换后 EMP003: " + employeeMap.get("EMP003").getName());

        // 仅当旧值匹配时才替换（replace(K, V, V)）
        boolean replaced = employeeMap.replace("EMP004",
            employeeMap.get("EMP004"),
            new Employee("EMP004", "孔蓝（高级）", "测试部", 20000));
        System.out.println("条件替换结果: " + replaced);

        // ========== 7. 删除 ==========
        Employee removed = employeeMap.remove("EMP006");
        System.out.println("\n删除 EMP006: " + (removed != null ? removed.getName() : "无"));
        System.out.println("删除后员工总数: " + employeeMap.size());

        // ========== 8. 统计：技术部员工 ==========
        long techCount = employeeMap.values().stream()
            .filter(e -> "技术部".equals(e.department))
            .count();
        System.out.println("\n技术部员工数: " + techCount);
    }
}

import java.util.*;

/**
 * 场景：白歌让小崔验证 HashMap 的树化过程和扩容行为。
 * 大翔看到验证结果后，对 JDK 8 的优化表示认可。
 */
class PoorHashKey {
    private final int id;

    public PoorHashKey(int id) { this.id = id; }

    // 故意制造哈希冲突：所有对象返回相同的 hashCode
    @Override
    public int hashCode() { return 1; }  // 全部落入同一桶！

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof PoorHashKey)) return false;
        return id == ((PoorHashKey) o).id;
    }

    @Override
    public String toString() { return "Key#" + id; }
}

public class HashMapTreeifyDemo {
    public static void main(String[] args) {
        // ========== 演示一：链表 → 红黑树 ==========
        System.out.println("=== 演示一：链表增长 → 触发树化 ===");
        HashMap<PoorHashKey, String> map = new HashMap<>();

        for (int i = 1; i <= 12; i++) {
            map.put(new PoorHashKey(i), "Value" + i);
            if (i == 8) {
                System.out.println("  添加第 " + i + " 个元素（达到 TREEIFY_THRESHOLD = 8）");
            }
            if (i == 9) {
                System.out.println("  添加第 " + i + " 个元素（容量 >= 64 时链表转为红黑树）");
            }
        }
        System.out.println("  最终 size: " + map.size());
        System.out.println("  所有元素在同一桶中（hashCode 均为 1）");

        // 验证数据完整性
        for (int i = 1; i <= 12; i++) {
            String value = map.get(new PoorHashKey(i));
            System.out.println("    get(Key#" + i + ") = " + value);
        }

        // ========== 演示二：扩容阈值观察 ==========
        System.out.println("\n=== 演示二：负载因子 0.75 下的扩容行为 ===");
        HashMap<Integer, String> demo = new HashMap<>(4, 0.75f);
        int lastCap = getCapacity(demo);

        System.out.println("初始容量: " + lastCap + "，触发扩容阈值: " + (int)(lastCap * 0.75));

        for (int i = 0; i < 30; i++) {
            demo.put(i, "V" + i);
            int currentCap = getCapacity(demo);
            if (currentCap != lastCap) {
                System.out.println("  size=" + demo.size()
                    + " → 扩容: " + lastCap + " → " + currentCap
                    + " (threshold=" + (int)(currentCap * 0.75) + ")");
                lastCap = currentCap;
            }
        }

        System.out.println("\n最终容量: " + getCapacity(demo) + "，元素数: " + demo.size());

        // ========== 演示三：JDK 8 putIfAbsent / computeIfAbsent ==========
        System.out.println("\n=== 演示三：JDK 8 新增方法 ===");

        HashMap<String, List<String>> deptMap = new HashMap<>();

        // computeIfAbsent：键不存在时才计算并插入
        deptMap.computeIfAbsent("技术部", k -> new ArrayList<>()).add("白歌");
        deptMap.computeIfAbsent("技术部", k -> new ArrayList<>()).add("小崔");
        deptMap.computeIfAbsent("测试部", k -> new ArrayList<>()).add("孔蓝");
        deptMap.computeIfAbsent("市场部", k -> new ArrayList<>()).add("Frank");

        deptMap.forEach((dept, members) ->
            System.out.println("  " + dept + ": " + members)
        );

        // merge：合并值
        HashMap<String, Integer> salaryMap = new HashMap<>();
        salaryMap.put("技术部", 35000);
        salaryMap.merge("技术部", 12000, Integer::sum);
        salaryMap.merge("测试部", 15000, Integer::sum);
        System.out.println("\n部门工资汇总: " + salaryMap);
    }

    /** 通过反射获取 HashMap 内部 table 数组的长度 */
    private static int getCapacity(HashMap<?, ?> map) {
        try {
            java.lang.reflect.Field field = HashMap.class.getDeclaredField("table");
            field.setAccessible(true);
            Object[] table = (Object[]) field.get(map);
            return table == null ? 0 : table.length;
        } catch (Exception e) {
            return -1;
        }
    }
}

// ❌ 错误：将可变对象作为 HashMap 的 key，修改后无法找到
class MutableKey {
    String id;
    MutableKey(String id) { this.id = id; }

    @Override
    public int hashCode() { return Objects.hash(id); }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof MutableKey)) return false;
        return Objects.equals(id, ((MutableKey) o).id);
    }
}

HashMap<MutableKey, String> cache = new HashMap<>();
MutableKey key = new MutableKey("user_001");
cache.put(key, "小崔的信息");

key.id = "user_002";  // 修改了 key 的 hashCode！
System.out.println(cache.get(key));  // null！数据丢失！
// 甚至无法 remove(key)，造成"内存泄漏"

// ✅ 正确：使用不可变类作为 key
String key = "user_001";
cache.put(key, "小崔的信息");
// String 不可变，hashCode 永远不会变化

// ❌ 错误：多线程并发 put 导致数据丢失
HashMap<Integer, String> map = new HashMap<>();
CountDownLatch latch = new CountDownLatch(2);

new Thread(() -> {
    for (int i = 0; i < 1000; i++) map.put(i, "A");
    latch.countDown();
}).start();

new Thread(() -> {
    for (int i = 0; i < 1000; i++) map.put(i, "B");
    latch.countDown();
}).start();

latch.await();
System.out.println("期望: 1000, 实际: " + map.size());  // 可能 < 1000 甚至异常

// ✅ 方案一：使用 ConcurrentHashMap（推荐）
ConcurrentHashMap<Integer, String> concurrentMap = new ConcurrentHashMap<>();
// 内部使用 CAS + synchronized，线程安全且高效

// ✅ 方案二：使用 Collections.synchronizedMap
Map<Integer, String> syncMap = Collections.synchronizedMap(new HashMap<>());
// 所有操作都有 synchronized 保护，但遍历时需手动加锁

// ❌ 错误：只重写了 equals，未重写 hashCode
class BadEmployee {
    String id;
    String name;

    BadEmployee(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BadEmployee)) return false;
        BadEmployee e = (BadEmployee) o;
        return Objects.equals(id, e.id);
    }
    // 未重写 hashCode！继承 Object 的 hashCode（基于内存地址）
}

// 测试
HashMap<BadEmployee, String> map = new HashMap<>();
BadEmployee e1 = new BadEmployee("001", "小崔");
map.put(e1, "小崔的信息");

BadEmployee e2 = new BadEmployee("001", "小崔");
System.out.println(e1.equals(e2));         // true —— equals 认为相等
System.out.println(map.get(e2));            // null —— hashCode 不同，找不到！
System.out.println(e1.hashCode() == e2.hashCode()); // false —— 违反了契约！

// ✅ 正确：equals 和 hashCode 保持一致性
class GoodEmployee {
    String id;
    String name;

    GoodEmployee(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof GoodEmployee)) return false;
        GoodEmployee e = (GoodEmployee) o;
        return Objects.equals(id, e.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);  // 使用与 equals 相同的字段
    }
}

// ❌ 错误：直接使用 map.remove 会抛 ConcurrentModificationException
HashMap<String, String> map = new HashMap<>();
map.put("A", "1"); map.put("B", "2"); map.put("C", "3");

for (Map.Entry<String, String> entry : map.entrySet()) {
    if ("B".equals(entry.getKey())) {
        map.remove(entry.getKey());  // ConcurrentModificationException！
    }
}

// ✅ 使用迭代器的 remove 方法
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, String> entry = it.next();
    if ("B".equals(entry.getKey())) {
        it.remove();  // 安全删除
    }
}

// ✅ JDK 8 更简洁的方式
map.entrySet().removeIf(entry -> "B".equals(entry.getKey()));