数据结构与算法 - Hash 专题

哈希表（Hash Table）是一种常用的数据结构，使用键值对（key-value pair）的形式存储数据。通过一个散列函数（Hash Function），它将键映射到一个数组中的位置，从而能够高效地进行插入、删除和查找操作。以下是哈希表及其常用算法的总结：

一、基本概念

哈希函数（Hash Function）：将键转换为数组索引的函数。一个好的哈希函数应该尽可能均匀地分布数据以减少冲突。
哈希冲突（Hash Collision）：不同的键被哈希函数映射到相同的数组索引位置。
装载因子（Load Factor）：哈希表中元素数量与数组大小的比值，装载因子越大，冲突的可能性越高。

二、哈希表的操作

插入（Insert）：将一个键值对插入哈希表。哈希函数计算键的索引，将值存储在该索引位置。
查找（Search）：通过键找到对应的值。哈希函数计算键的索引，从该索引位置获取值。
删除（Delete）：从哈希表中删除一个键值对。哈希函数计算键的索引，将该索引位置的值删除。

三、哈希冲突解决方法

链地址法（Chaining）：
- 每个数组元素作为链表的头节点，所有映射到同一索引的元素都存储在该链表中。
- 插入、查找和删除操作需要遍历链表，时间复杂度为O(n/k)，其中n是元素数量，k是数组大小。
开放地址法（Open Addressing）：
- 当冲突发生时，寻找下一个空闲位置存储元素。
- 常见的探测方法：
  - 线性探测（Linear Probing）：如果索引i发生冲突，则尝试i+1, i+2, …位置。
  - 二次探测（Quadratic Probing）：尝试i+1^2, i+2^2, …位置。
  - 双重哈希（Double Hashing）：使用第二个哈希函数计算步长。

四、哈希表的优缺点

优点：

插入、删除、查找的平均时间复杂度为O(1)。
编程简单，实现方便。

缺点：

在最坏情况下（例如所有元素都冲突），时间复杂度可能为O(n)。
需要良好的哈希函数设计，以减少冲突。
内存消耗较大，特别是在装载因子较低时。

五、常见应用

缓存（Cache）：快速存取数据。
集合（Set）：存储不重复的元素。
字典（Dictionary）：键值对存储和快速查找。
数据库索引：提高查询效率。

六、LeetCode 相关题目

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例:

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

解法:

创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> hashTable = new HashMap<Integer,Integer>();
        for(int i = 0; i < nums.length; i++){
            if(hashTable.containsKey(target - nums[i])){
                // 找到符合要求的组合，直接返回即可
                return new int[] {i, hashTable.get(target - nums[i])};
            }
            // 否则，将当前元素放入 hashTable
            hashTable.put(nums[i], i);
        }
        // 没有找到符合要求的组合
        return null;
    }
}

复杂度分析:

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

2. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例:

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

解法:

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // Hash 方法, 关键是如何确定 key 与 value
        // 排序 + Hash
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for(String str : strs){
            char[] array = str.toCharArray();   // 将字符串转为字符数组，以进行排序
            Arrays.sort(array);
            String key = new String(array); // 排序后的字符串作为 Hash 表中的 key
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);  // 把当前字符串放入 Hash 表对应位置
        }
        // 输出结果
        return new ArrayList<List<String>>(map.values());
    }
}

复杂度分析:

时间复杂度：O(nklog⁡k)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klog⁡k) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklog⁡k)。

空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

3. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例:

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

解法:

每个数都判断一次这个数是不是连续序列的开头那个数。怎么判断呢，就是用哈希表查找这个数前面一个数是否存在，即 num-1 在序列中是否存在。存在那这个数肯定不是开头，直接跳过。因此只需要对每个序列开头的数进行循环，直到这个序列不再连续，因此复杂度是O(n)。

class Solution {
    public int longestConsecutive(int[] nums) {
        // Hash 方法，先去重，然后依次判断每个数字是否是可能的序列头；若是，计算最长序列；若不是，直接跳过。
        // 去重
        Set<Integer> numSet = new HashSet<Integer>();
        for(int num : nums) numSet.add(num);
        // 判断每个元素
        int res = 0;
        for(Integer num : numSet){
            if(!numSet.contains(num - 1)){
                // 是序列头，计算该序列最大长度
                int curNum = num;
                int curCount = 1;
                while(numSet.contains(++curNum)) curCount++;
                // 更新当前结果
                res = Math.max(res, curCount);
            }
            // 不是序列头，直接跳过
        }
        // 返回结果
        return res;
    }
}

复杂度分析:

时间复杂度：O(n)，其中 n 为数组的长度。

空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n) 的空间。

Parker's Blog

数据结构与算法 - Hash 专题

一、基本概念

二、哈希表的操作

三、哈希冲突解决方法

四、哈希表的优缺点

五、常见应用

六、LeetCode 相关题目

1. 两数之和

2. 字母异位词分组

3. 最长连续序列