哈希表与集合：从原理到实战

哈希表这东西，说白了就是「用空间换时间」的典型代表。我刚开始学算法时，总觉得它就是个高级数组，后来踩过坑才明白——它背后的设计哲学，远比想象中精妙。

一、哈希表的核心原理

哈希表本质上是一个键值对存储结构。你给它一个 key，它通过哈希函数计算出一个位置，然后把 value 存过去。取的时候也一样，用同一个哈希函数算位置，直接拿数据。

这个过程的时间复杂度，理想情况下是 O(1)。为什么是理想情况？因为哈希冲突是绕不开的问题。

二、哈希冲突与解决方案

冲突是必然的。哪怕哈希函数再完美，数组容量有限，两个不同的 key 算到同一个 index 只是时间问题。我遇到过最夸张的一次，线上服务因为哈希冲突严重，查询从微秒级退化到了毫秒级。

常见的冲突解决策略有两种：

方法	原理	优缺点
链地址法	每个槽位挂一个链表，冲突的 key 链在后面	实现简单，但链表过长时查询变慢
开放地址法	冲突后找下一个空位（线性探测、二次探测等）	空间利用率高，但删除操作麻烦

三、集合（Set）的本质

集合其实就是只存 key 不存 value 的哈希表。它的核心能力是「判断一个元素是否存在」，时间复杂度同样是 O(1)。

你想想看，很多算法题里需要去重、需要快速判断元素是否出现过——这时候用 Set 就对了。我写代码时，只要看到「唯一性」三个字，第一反应就是 Set。

四、经典例题实战

例题1：两数之和

题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

暴力解法是 O(n²)，但用哈希表可以降到 O(n)。

// 思路：遍历数组，把每个数存到哈希表里
// 同时检查 target - nums[i] 是否已经在表中
public 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[]{-1, -1};
}

例题2：最长连续序列

题目：给定一个未排序的整数数组，找出最长连续序列的长度。要求 O(n) 时间复杂度。

这题的精髓在于：用 Set 存储所有数，然后只从「连续序列的起点」开始查找。

// 思路：先全部放入 Set
// 遍历每个数，如果 num-1 不在 Set 中，说明它是起点
// 从起点开始往后数，统计连续长度
public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    
    int maxLen = 0;
    for (int num : set) {
        // 只从起点开始
        if (!set.contains(num - 1)) {
            int cur = num;
            int len = 1;
            while (set.contains(cur + 1)) {
                cur++;
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;
}

五、知识体系总览

下面这张图，是我自己总结的哈希表知识结构。你看一眼就能明白各个知识点之间的关系。

六、避坑指南

• 哈希函数别太简单：直接用 key 的 hashCode() 取模，在数据量大的时候很容易碰撞。我习惯在哈希函数里加一点扰动，比如异或高位。
• 扩容要提前规划：哈希表有一个负载因子（默认 0.75），超过这个值就会扩容。扩容时要重新哈希所有数据，这是 O(n) 操作。如果你知道数据量，最好初始化时指定容量。
• 自定义对象做 key 要小心：必须同时重写 hashCode() 和 equals()，否则两个内容相同的对象会被当成不同的 key。这个坑我至少见过三次。

---

公众号:蓝海资料掘金营，微信deep3321