哈希表原理与应用

哈希表的核心思想

哈希表（Hash Table）是一种以 O(1) 平均时间进行插入、删除、查找的数据结构，其代价是使用额外的内存空间。

核心思想是空间换时间：把键（Key）通过哈希函数映射为数组下标，直接存储和查找，免去逐个比较的 O(n) 开销。

key "alice" → hash("alice") % 8 = 3 → 存在数组[3]
key "bob"   → hash("bob") % 8 = 5 → 存在数组[5]
key "carol" → hash("carol") % 8 = 1 → 存在数组[1]

查找 "bob"：hash("bob") % 8 = 5，直接访问数组[5] → O(1)

哈希函数

好的哈希函数需要：

1. 确定性：相同的键总产生相同的哈希值
2. 均匀性：尽量将键均匀分布到整个数组范围
3. 高效性：计算速度快

常见哈希函数（整数键）：

h(k) = k mod m  （m 通常取质数，减少冲突）

Java 的 String.hashCode() 使用多项式哈希：

// Java 字符串哈希（简化版）
int hash = 0;
for (char c : s.toCharArray()) {
    hash = hash * 31 + c;
}
// 31 是质数，且 31i = 32i - i = (i<<5) - i，可以位运算加速

哈希冲突及解决方案

两个不同的键映射到同一个数组下标，称为哈希冲突（Hash Collision）。冲突不可避免（鸽巢原理），但可以控制和解决。

链地址法（Chaining）

每个数组槽位存储一个链表，冲突的元素追加到链表中。

数组[3]: → [("alice", 1)] → null
数组[5]: → [("bob", 2)] → [("eve", 7)] → null  ← 冲突！
数组[1]: → [("carol", 3)] → null

Java 的 HashMap 使用此方法，并做了优化：
链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转为红黑树，将最坏查找从 O(n) 降至 O(log n)。

// HashMap 源码中的阈值常量
static final int TREEIFY_THRESHOLD = 8;  // 链表转红黑树的阈值
static final int UNTREEIFY_THRESHOLD = 6;  // 红黑树转链表的阈值
static final int MIN_TREEIFY_CAPACITY = 64;  // 最小转树化容量

开放地址法（Open Addressing）

发生冲突时，在数组中寻找下一个空槽位。

线性探测：冲突时往后一位一位找空槽
数组: [_, _, alice, _, bob, eve, _, _]
              ^2        ^4  ^5
冲突时：5→6→7→0→...直到找到空位

开放地址法的缺点是"聚集"问题——冲突形成连续的簇，使后续冲突更频繁。

负载因子（Load Factor）

负载因子 = 已存储元素数 / 数组容量。

Java HashMap 的默认负载因子是 0.75：当元素数量超过容量的 75% 时，触发扩容（Resize）——将数组容量翻倍，并重新哈希所有元素（O(n)）。

0.75 是时间和空间的平衡点：太低（如 0.5）浪费空间，太高（如 0.9）冲突频繁、性能下降。

Java HashMap 内部实现

// HashMap 默认初始容量 16（2 的幂，方便位运算取模）
// h & (capacity - 1) 等价于 h % capacity（当 capacity 是 2 的幂时）

为什么容量总是 2 的幂？
取模 h % m 可用位运算 h & (m-1) 代替（当 m 是 2 的幂时），性能更好。

HashMap 的 put 流程：

1. 计算 key 的 hash 值：(h = key.hashCode()) ^ (h >>> 16)  // 高低位混合，减少冲突
2. 计算数组下标：hash & (capacity - 1)
3. 若该槽空，直接插入
4. 若该槽不空：
   a. 若 key 相同（equals），更新 value
   b. 若 key 不同，且槽是链表，追加到链表尾（Java 8 后）
   c. 若 key 不同，且槽是红黑树，插入树中
5. 若元素数超过阈值（capacity * loadFactor），扩容

Java 常用哈希结构

HashMap：键值对映射

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.getOrDefault("b", 0);   // 不存在时返回默认值
map.merge("a", 1, Integer::sum);  // a 存在则相加，不存在则设为 1
map.containsKey("a");
map.entrySet();  // 遍历键值对

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

HashSet：元素去重

Set<Integer> set = new HashSet<>();
set.add(1);
set.contains(1);   // O(1)
set.remove(1);

LinkedHashMap：保持插入顺序

Map<String, Integer> lruMap = new LinkedHashMap<>(16, 0.75f, true) {
    // accessOrder=true 则按访问顺序排序（LRU Cache 的基础）
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 10;  // 超过 10 个时自动移除最旧的
    }
};

TreeMap：按键有序

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "c");
treeMap.put(1, "a");
treeMap.firstKey();   // 1（最小键）
treeMap.floorKey(2);  // 1（≤2 的最大键）
treeMap.ceilingKey(2); // 3（≥2 的最小键）
// 底层是红黑树，查询 O(log n)

哈希表的架构应用模式

模式一：两数之和（查找补数）

// 时间 O(n)，空间 O(n)
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(nums[i], i);
    }
    return new int[]{};
}

思路：遍历时用哈希表记录"已见过的元素及其下标"，对每个新元素查找其补数是否已出现。

模式二：字符频次统计

// 判断 t 是否是 s 的异位词（字母完全相同但顺序不同）
boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];  // 26 个字母时，数组比 HashMap 更快
    for (char c : s.toCharArray()) count[c - 'a']++;
    for (char c : t.toCharArray()) count[c - 'a']--;
    for (int n : count) if (n != 0) return false;
    return true;
}

模式三：分组（按特征聚合）

// 分组字谜：把互为异位词的单词归为一组
List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);                    // 排序后异位词的 key 相同
        String key = new String(chars);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

模式四：计数/滑动窗口中的频次

// 找所有字母异位词（滑动窗口 + 频次哈希）
List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int[] pCount = new int[26], wCount = new int[26];
    for (char c : p.toCharArray()) pCount[c - 'a']++;

    for (int i = 0; i < s.length(); i++) {
        wCount[s.charAt(i) - 'a']++;             // 右边界加入
        if (i >= p.length()) {
            wCount[s.charAt(i - p.length()) - 'a']--;  // 左边界移出
        }
        if (Arrays.equals(pCount, wCount)) result.add(i - p.length() + 1);
    }
    return result;
}

复杂度总结

哈希表的 O(1) 是均摊平均，不是绝对保证。在极端情况（故意制造哈希冲突）下，性能退化。Java 的 HashMap 用随机种子（Java 8+）和红黑树兜底，实际工程中基本不需要担心。

小结

哈希表的本质是：用哈希函数把任意 key 映射为整数下标，直接索引。

关键设计选择：

• 链地址法 vs 开放地址法：链地址法实现简单，开放地址法内存局部性好
• 扩容阈值：Java HashMap 是 0.75，触发后 O(n) 重建
• Java 8 优化：链表超过 8 个节点转红黑树，最坏从 O(n) 降至 O(log n)

工程实践中哈希表的万能口诀："需要快速查找某个值是否出现过，或记录它的某个属性，用 HashMap"。