哈希表
哈希表（Hash table），也称作散列表，是一种通过哈希函数将键（key）映射到存储位置（索引）来访问数据的数据结构。它提供了快速的数据查找、插入和删除操作。
哈希函数
哈希函数的作用是将键值映射到哈希表上的索引。通过计算键的哈希值，然后将哈希值映射到哈希表（通常是数组）的某个位置，从而实现快速访问。
如果哈希函数计算得到的哈希值（hashCode）超出了哈希表的大小（tableSize），通常会通过取模运算 (hashCode % tableSize) 将其映射到哈希表内的有效索引范围。
然而，当存储的数据量较大时，即使哈希函数设计得再好，也可能出现不同的键被映射到哈希表同一个索引位置的情况。这就是哈希碰撞。
哈希碰撞
如上图所示，小李和小王都被映射到了索引下标 1 的位置，这种现象称为哈希碰撞。
解决哈希碰撞的常见方法有两种：拉链法和线性探测法。
拉链法 (Separate Chaining)
拉链法通过在哈希表的每个索引位置存储一个链表（或其它数据结构），将所有映射到该索引的元素都存储在这个链表中。
选择合适的哈希表大小（tableSize）非常重要。一个合适的 tableSize 既能避免因数组空值而浪费大量内存，也能避免因链表过长而导致查找效率降低。
线性探测法 (Linear Probing)
线性探测法在发生碰撞时，会向后查找哈希表中的下一个空闲位置来存储冲突的元素。因此，使用线性探测法时，必须保证哈希表的大小 (tableSize) 大于实际存储的数据量 (dataSize)，以确保总能找到空位。
常见哈希结构对比 (C++)
在 C++ 中，set 和 map 分别提供了基于红黑树和哈希表的多种数据结构。
集合 (Set)
| 集合 | 底层原理 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
std::multiset | 红黑树 | 有序 | 是 | 否 | O(log n) | O(log n) |
std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
补充：红黑树是一种平衡二叉搜索树，因此其键（key）是有序的。但键本身不可修改，因为修改键值会导致整棵树的结构错乱，只能通过删除旧键再插入新键的方式进行“修改”。
映射 (Map)
| 映射 | 底层原理 | 是否有序 | 键是否可以重复 | 键能否修改 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
std::map | 红黑树 | 键有序 | 否 | 否 | O(log n) | O(log n) |
std::multimap | 红黑树 | 键有序 | 是 | 否 | O(log n) | O(log n) |
std::unordered_map | 哈希表 | 键无序 | 否 | 否 | O(1) | O(1) |
应用示例
用 Set 判断快乐数
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True；不是，则返回 False。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1解题思路：
- 在求解快乐数的计算过程中，若出现非快乐数计算结果重复，意味着已经陷入循环，断然不是快乐数。
- 同时，非快乐数的计算最终都会进入
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4的循环中。
import java.util.HashSet;
import java.util.Set;
class Solution {
/**
* 计算一个数的每个位上的数字的平方和
* @param n 输入的整数
* @return 平方和
*/
public int getSum(int n) {
int sum = 0;
int temp = 0;
while (n > 0) {
temp = n % 10; // 取出个位数
sum += temp * temp; // 平方并累加
n /= 10; // 去掉个位数
}
return sum;
}
/**
* 判断一个数是否为快乐数
* @param n 输入的整数
* @return 如果是快乐数返回 true，否则返回 false
*/
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>(); // 用于检测循环
while (n != 1 && !set.contains(n)) { // 如果不是 1 且没有出现循环
set.add(n); // 将当前数加入集合
n = getSum(n); // 计算下一个数
}
return n == 1; // 如果最终变为 1，则是快乐数
}
}两数之和
注意：target 为任意值。
这是一个简单的哈希表应用，利用哈希表键的唯一性来快速查找目标值。
import java.util.HashMap;
import java.util.Map;
class Solution {
/**
* 在数组中找到两个数，使其和等于目标值
* @param nums 整数数组
* @param target 目标和
* @return 两个数的索引，如果不存在则返回空数组
*/
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashTable = new HashMap<>(); // 存储数值和其索引
for (int i = 0; i < nums.length; ++i) {
// 检查 target - 当前数 是否存在于哈希表中
if (hashTable.containsKey(target - nums[i])) {
return new int[]{i, hashTable.get(target - nums[i])};
}
// 将当前数和其索引放入哈希表
hashTable.put(nums[i], i);
}
return new int[0]; // 未找到
}
}四数相加 II
这道题目与 三数之和 和 四数之和 有所不同。它要求找到四个独立数组 A, B, C, D 中，使得 A[i] + B[j] + C[k] + D[l] = 0 的元组数量。不需要考虑重复的四个元素相加等于 0 的情况。
解题思路：
- 首先定义一个
HashMap，key存储nums1和nums2中任意两数之和，value存储该和出现的次数。 - 遍历
nums1和nums2数组，统计所有可能的两数之和及其出现次数，并存入HashMap。 - 定义一个
int变量count，用来统计a + b + c + d = 0出现的总次数。 - 遍历
nums3和nums4数组，计算c + d。然后查找HashMap中是否存在-(c + d)这个键。 - 如果存在，则将
HashMap中该键对应的value（即出现次数）累加到count中。 - 最后返回统计值
count。
import java.util.HashMap;
import java.util.Map;
class Solution {
/**
* 计算四个数组中和为 0 的元组数量
* @param nums1 数组1
* @param nums2 数组2
* @param nums3 数组3
* @param nums4 数组4
* @return 和为 0 的元组数量
*/
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> hashMap = new HashMap<>();
int tempSum = 0;
int count = 0;
// 统计 nums1 和 nums2 中所有两数之和的频率
for (int i : nums1) {
for (int j : nums2) {
tempSum = i + j;
hashMap.put(tempSum, hashMap.getOrDefault(tempSum, 0) + 1);
}
}
// 遍历 nums3 和 nums4，查找是否存在对应的和
for (int k : nums3) {
for (int l : nums4) {
tempSum = k + l;
// 如果 hashMap 中存在 -(tempSum)，则累加其频率
if (hashMap.containsKey(-tempSum)) {
count += hashMap.get(-tempSum);
}
}
}
return count;
}
}赎金信
这是一个典型的哈希表应用，用于统计字符频率。
使用原生哈希表 (Map)
import java.util.HashMap;
import java.util.Map;
class Solution {
/**
* 判断赎金信能否由杂志中的字母构成
* @param ransomNote 赎金信字符串
* @param magazine 杂志字符串
* @return 如果能构成返回 true，否则返回 false
*/
public boolean canConstruct(String ransomNote, String magazine) {
// 统计 ransomNote 中字符的频率
Map<Character, Integer> ransomMap = new HashMap<>();
for (char c : ransomNote.toCharArray()) {
ransomMap.put(c, ransomMap.getOrDefault(c, 0) + 1);
}
// 统计 magazine 中字符的频率
Map<Character, Integer> magazineMap = new HashMap<>();
for (char c : magazine.toCharArray()) {
magazineMap.put(c, magazineMap.getOrDefault(c, 0) + 1);
}
// 检查 ransomNote 中的每个字符是否都能在 magazine 中找到足够的数量
for (char c : ransomMap.keySet()) {
if (!magazineMap.containsKey(c) || magazineMap.get(c) < ransomMap.get(c)) {
return false;
}
}
return true;
}
}使用数组作为哈希表
考虑到题目中测试用例通常只涉及小写字母（共 26 个），可以使用数组来模拟哈希表，这样可以获得更好的性能，因为数组的访问速度比 HashMap 更快，且避免了哈希函数计算和处理碰撞的开销。
class Solution {
/**
* 判断赎金信能否由杂志中的字母构成（使用数组作为哈希表）
* @param ransomNote 赎金信字符串
* @param magazine 杂志字符串
* @return 如果能构成返回 true，否则返回 false
*/
// 时间复杂度: O(m + n)，m 为 ransomNote 长度，n 为 magazine 长度
// 空间复杂度：O(1)，因为数组大小固定为 26
public boolean canConstruct(String ransomNote, String magazine) {
int[] charCounts = new int[26]; // 存储 magazine 中每个字符的频率
// 统计 magazine 中每个字符的频率
for (char c : magazine.toCharArray()) {
charCounts[c - 'a']++;
}
// 遍历 ransomNote，检查所需字符是否足够
for (char c : ransomNote.toCharArray()) {
// 如果当前字符在 magazine 中数量不足，或者根本不存在
if (charCounts[c - 'a'] <= 0) {
return false;
}
charCounts[c - 'a']--; // 使用一个字符，频率减一
}
return true;
}
}贡献者
jiechen