深入理解 Java 中的哈希表 (Hash Table)

在计算机科学中，哈希表（Hash Table） 是一种极其重要的数据结构。它提供了接近 O(1) 的时间复杂度来进行数据的插入、删除和查找操作。在 Java 中，最常用的哈希表实现就是 java.util.HashMap。
本篇博客将带你深入了解哈希表的工作原理、Java 中的实现细节以及使用时的最佳实践。

1. 什么是哈希表？
哈希表本质上是一个 键值对（Key-Value） 映射的容器。它通过一个 哈希函数（Hash Function） 将**键（Key）**映射到数组的一个索引位置上，从而实现快速访问。
核心概念：
**Key (键)：**用于唯一标识数据的值（例如身份证号、学号）。
**Value (值)：**与键关联的实际数据。
**Hash Function (哈希函数)：**将 Key 转换为数组下标的算法。
**Bucket (桶)：**数组中的每一个位置被称为一个"桶"。

2. 哈希表的工作原理
当我们向哈希表中存入数据时，过程如下：
计算哈希值：调用 Key 的 hashCode() 方法，得到一个整数。
定位桶：通过哈希值与数组长度取模（或位运算），确定该键值对应该存放在数组的哪个位置（哪个桶）。
处理冲突 (Collision)：如果两个不同的 Key 计算出了相同的桶位置，就会发生"哈希冲突"。常见的解决方法有 链地址法（Chaining） 和 开放地址法（Open Addressing）。Java 的 HashMap 使用的是链地址法**（结合红黑树优化）**。

3. Java 中的 HashMap
HashMap 是 Java 集合框架中最常用的实现。
基本用法

import java.util.HashMap;
import java.util.Map;

public class HashTableDemo {
    public static void main(String[] args) {
        // 创建一个 HashMap
        Map<String, Integer> scores = new HashMap<>();

        // 1. 插入数据 (put)
        scores.put("Alice", 90);
        scores.put("Bob", 85);
        scores.put("Charlie", 92);

        // 2. 获取数据 (get)
        int aliceScore = scores.get("Alice");
        System.out.println("Alice's Score: " + aliceScore);

        // 3. 检查是否包含 Key
        if (scores.containsKey("Bob")) {
            System.out.println("Bob exists.");
        }

        // 4. 遍历
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

深入内部机制 (JDK 8+)
在 JDK 8 及以后版本中，HashMap 的结构是 “数组 + 链表 + 红黑树”。
3.1 数组 (Node[] table)
这是 HashMap 的主体结构，每个位置就是一个"桶"。默认初始容量是 16，负载因子是 0.75。当元素数量超过 容量 × 负载因子 时，数组会扩容为原来的 2 倍。
3.2 链表 (Linked List)
当发生哈希冲突时（多个 Key 映射到同一个桶），HashMap 会在该桶位置形成一条链表，将冲突的元素依次串联起来。

链表的结构：

桶[index] → Node1 → Node2 → Node3 → null

每个 Node 包含四个字段：

static class Node<K,V> {
    final int hash;    // Key 的哈希值
    final K key;       // 键
    V value;           // 值
    Node<K,V> next;    // 指向下一个节点
}

链表的特点：
插入速度快（头插法/ 尾插法）
查找速度慢，时间复杂度 O(n)
当链表长度较短时，性能影响不大

3.3 红黑树 (Red-Black Tree)
当链表长度超过阈值（默认为 8）且数组长度达到 64 时，链表会转换为红黑树。
红黑树的结构：
红黑树是一种自平衡的二叉搜索树，具有以下性质：
每个节点要么是红色，要么是黑色
根节点是黑色
所有叶子节点（NIL）是黑色
红色节点的两个子节点必须是黑色（不能有连续的红节点）
从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点
为什么需要红黑树？
当链表过长（比如有大量哈希冲突），查询效率会退化为 O(n)。红黑树能将查询效率提升到 O(log n)。

转换条件：
链表长度 > 8 且 数组长度 >= 64 → 链表转红黑树
红黑树节点数 < 6 → 红黑树退化为链表

**// HashMap 中的关键常量
static final int TREEIFY_THRESHOLD = 8;      // 链表转红黑树的阈值
static final int UNTREEIFY_THRESHOLD = 6;    // 红黑树退化为链表的阈值
static final int MIN_TREEIFY_CAPACITY = 64;  // 转红黑树的最小数组容量**

4. 哈希冲突的处理方式

4.1 什么是哈希冲突？

当两个不同的 Key 经过哈希函数计算后，得到相同的数组索引位置，就发生了哈希冲突。

// 伪代码示例
hash("Alice") % 16 = 5
hash("Bob")   % 16 = 5  // 冲突！

4.2 常见的冲突解决方法
方法一：链地址法（Separate Chaining）
这是 Java HashMap 使用的方法。每个桶维护一个链表（或红黑树），冲突的元素都存在同一个桶的链表中。
优点：
实现简单
负载因子可以大于 1
删除操作简单
缺点：
需要额外的指针空间
缓存不友好（链表节点分散在内存中）

方法二：开放地址法（Open Addressing）
当发生冲突时，按照某种探测规则寻找下一个空闲位置。常见变体：
线性探测：依次检查下一个位置 (hash + 1) % capacity
二次探测：按 1², 2², 3²… 的步长探测
双重哈希：使用第二个哈希函数计算步长
优点：
数据存在数组中，缓存友好
不需要额外指针空间
缺点：
负载因子不能太高（通常 < 0.7）
删除操作复杂（需要标记删除）
容易产生"聚集"现象

方法三：再哈希法（Rehashing）
使用多个哈希函数，当第一个哈希函数发生冲突时，依次尝试其他哈希函数。
4.3 HashMap 如何优化哈希冲突？
扰动函数
HashMap 对 Key 的 hashCode 进行了二次处理，让高位也参与运算，减少冲突：

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

h >>> 16 将高 16 位移到低 16 位，然后与原值异或，让高低位都参与索引计算。
容量始终为 2 的幂
HashMap 的容量总是 2 的幂次方（16, 32, 64…），这样可以用位运算代替取模：

// 等价于 hash % capacity，但效率更高
index = (capacity - 1) & hash

5. 为什么重写 equals 必须重写 hashCode？
这是 Java 中的经典问题。如果你自定义了一个对象作为 HashMap 的 Key，你必须同时重写这两个方法。
规则：如果 obj1.equals(obj2) 为 true，那么它们的 hashCode() 必须相等。
原因：HashMap 先通过 hashCode 定位到具体的桶。如果两个对象逻辑上相等（equals），但 hashCode 不同，它们就会被放入两个不同的桶中，导致 HashMap 认为它们是两个不同的键，这违背了业务逻辑。

class User {
    String id;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

总结
哈希表是 Java 开发者工具箱中最强大的武器之一。理解其背后的数组、链表、红黑树结构以及哈希冲突的处理方式，能帮助你写出更高效、更安全的代码。

希望这篇博客对你有帮助！