哈希表原理与实战（哈希碰撞 · 常见题型）

哈希表核心原理

哈希函数

将 key 映射到数组下标：index = hashCode(key) % capacity

好的哈希函数要求：

1. 确定性：相同输入必须产生相同输出
2. 均匀分布：减少碰撞
3. 高效计算：O(1)

哈希碰撞处理

链地址法（Separate Chaining）：

• 每个槽位存储链表（或红黑树）
• Java HashMap 采用此方案
• 负载因子（Load Factor）= n/capacity，默认 0.75

开放寻址法（Open Addressing）：

• 线性探测 / 二次探测 / 双重哈希
• Python dict 采用此方案

Java HashMap 关键特性

• 初始容量：16，负载因子：0.75
• 扩容：容量 × 2，重新哈希
• Java 8+：链表长度 ≥ 8 时转红黑树（防止 Hash DoS）
• 线程不安全 → 需要 ConcurrentHashMap

手写哈希表（链地址法）

class MyHashMap {
    private static final int SIZE = 1000;
    private LinkedList<int[]>[] table;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        table = new LinkedList[SIZE];
    }

    public void put(int key, int value) {
        int idx = key % SIZE;
        if (table[idx] == null) table[idx] = new LinkedList<>();
        for (int[] pair : table[idx]) {
            if (pair[0] == key) { pair[1] = value; return; }
        }
        table[idx].add(new int[]{key, value});
    }

    public int get(int key) {
        int idx = key % SIZE;
        if (table[idx] == null) return -1;
        for (int[] pair : table[idx]) {
            if (pair[0] == key) return pair[1];
        }
        return -1;
    }

    public void remove(int key) {
        int idx = key % SIZE;
        if (table[idx] == null) return;
        table[idx].removeIf(pair -> pair[0] == key);
    }
}

常见哈希题型

两数之和（LeetCode 1）

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) return new int[]{map.get(complement), i};
        map.put(nums[i], i);
    }
    return new int[]{};
}

有效的字母异位词（LeetCode 242）

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    for (char c : t.toCharArray()) {
        count[c - 'a']--;
        if (count[c - 'a'] < 0) return false;
    }
    return true;
}

字母异位词分组（LeetCode 49）

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

前 K 个高频元素（LeetCode 347）

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    // 桶排序：按频率放入桶
    List<Integer>[] buckets = new List[nums.length + 1];
    freq.forEach((num, count) -> {
        if (buckets[count] == null) buckets[count] = new ArrayList<>();
        buckets[count].add(num);
    });
    int[] result = new int[k];
    int idx = 0;
    for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
        if (buckets[i] != null) {
            for (int n : buckets[i]) { result[idx++] = n; if (idx == k) break; }
        }
    }
    return result;
}