数组哈希、集合哈希、映射哈希，各有适用场景。
原理
（1）哈希表原理
哈希函数将传入的值映射为符号表的索引。
一般来说哈希表都是用来快速判断一个元素是否出现集合里。
（2）哈希碰撞
当不同的值映射为相同的索引时就出现了哈希碰撞。
一般解决方法：
（3）常用的哈希表数据结构
数组哈希
概念阐述
数组可以作为简单的哈希表，哈希函数可以就是简单的恒等映射。
（1）数组作哈希表的场景，一般用在元素值范围已知，并且元素个数均衡的情况。
场景：只有小写字母的字符串
（2）不足
稀疏时（元素个数远小于元素范围），空间利用率低
元素个数远大于范围时，哈希碰撞率大
对于哈希碰撞处理能力低（只有线性探测、二次探测）
相关题目
字符串排列
https://leetcode.cn/problems/MPnaiL/description/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean checkInclusion(String s1, String s2) {
if(s1.length()> s2.length()) return false;
int[] map1 = new int[26];
int[] map2 = new int[26];
for(int i=0; i<s1.length(); ++i){
map1[s1.charAt(i)-'a']++;
map2[s2.charAt(i)-'a']++;
}
if(Arrays.equals(map1, map2)) return true;
for(int i=s1.length(); i<s2.length(); ++i){
map2[s2.charAt(i-s1.length())-'a']--;
map2[s2.charAt(i)-'a']++;
if(Arrays.equals(map1, map2)) return true;
}
return false;
}
}
|
刚好全是英文小写字母，可以用数组哈希。
滑动窗口法。
在判断两个数组是否相同时还可以优化，记录两个数组的差异度，见滑动窗口法。
两数之和被k整除的方案数
https://www.nowcoder.com/questionTerminal/52f9ae6aa2ac4b2684af50f15bd897ac
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
sc.nextLine();
String s2 = sc.nextLine();
String[] ss2 = s2.split("\\s");
long [] tong = new long[k];
long re = 0;
for (int i = 0; i < n; i++) {
tong[Integer.parseInt(ss2[i]) % k]++;
}
for (int i = 1; i < k / 2; i++) {
re += tong[i] * tong[k - i];
}
re += tong[0] * (tong[0] - 1) / 2;
if (k % 2 == 0) {
re += tong[k / 2] * (tong[k / 2] - 1) / 2;
}
System.out.println(re);
}
}
|
给定一个 n 个元素组成的数组，和一个正整数 k 。求取两个数之和能被 k 整除的方案数（即两数之和为k的倍数的方案数）。
这题比较巧妙，利用了同余的思想，设置了K个桶。能被K整除的两个数，余数肯定是互补的。
特别要注意余数为0和K为偶数的情况。
集合哈希
概念阐述
Set是不包含重复元素的集合。
（1）集合用作哈希表，适合元素范围不知道的情况。
典型的使用方法是判断一个元素是否在集合内。
（2）不足
- 输出结果可能无序
- 只能用来判断是否在集中，无法存储其他信息
Java相关API
Java的Set接口有多个实现类，其中比较常用的有HashSet、LinkedHashSet和TreeSet。
HashSet：基于哈希表实现，没有固定的顺序，可以快速添加、删除和查找元素。
它最适合用于不需要保持顺序的场景。
LinkedHashSet：具有可预测的迭代顺序，它通过链表维护元素的插入顺序。
在迭代访问时，效率略低于HashSet，但在插入和删除时性能较好。
TreeSet：基于红黑树实现，元素按照自然顺序或自定义顺序进行排序。
它提供了一些额外的方法来获取第一个元素、最后一个元素、小于某个值的最大元素、大于某个值的最小元素等。
相关题目
求两个数组的交集
https://leetcode.cn/problems/intersection-of-two-arrays/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0)
return new int[0];
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
for (int i : nums1) {
set1.add(i);
}
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
return resSet.stream().mapToInt(x -> x).toArray();
}
}
|
映射哈希
概念阐述
数组作为哈希表的局限：无法处理稀疏情况，空间浪费。
集合作为哈希表的局限：集合只能存放一个key，无法记录个数或下标位置信息。
这就引出了map，它是一种<key, value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。
Java相关API
1
2
| Map<String, Integer> map = new HashMap<>();
Map<String, Integer> map = new TreeMap<>();
|
插入put、得到get、包含键containsKey、包含值containsValue、大小size、判空isEmpty
1
2
3
4
5
6
7
8
9
10
|
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("Key: " + key + ", Value: " + value);
}
map.forEach(
(k, v) -> {
);
|
相关题目
两数之和
https://leetcode.cn/problems/two-sum/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] ans = new int[2];
for(int i=0; i<nums.length; ++i){
if(map.containsKey(target - nums[i])){
ans[0] = i;
ans[1] = map.get(target-nums[i]);
break;
}
map.put(nums[i], i);
}
return ans;
}
}
|
这道题还是非常巧妙的，利用一个数和target已知的条件，快速确定另外一个数的值。
还有一个点是，不需要预先初始化map，查找过程中，未找到则插入。
单词规律
https://leetcode.cn/problems/word-pattern/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character, String> p2s = new HashMap<>();
Map<String, Character> s2p = new HashMap<>();
String[] strs = s.split(" ");
if(pattern.length()!=strs.length) return false;
for(int i=0; i<strs.length; ++i){
char ch = pattern.charAt(i);
String word = strs[i];
if(p2s.containsKey(ch)){
if(!p2s.get(ch).equals(word)) return false;
}else{
if(s2p.containsKey(word)) return false;
s2p.put(word, ch);
p2s.put(ch, word);
}
}
return true;
}
}
|
判断双射的逻辑，pattern没出现，那么word也不应该出现
和为K的子数组
https://leetcode.cn/problems/subarray-sum-equals-k/description/
（1）暴力搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int subarraySum(int[] nums, int k) {
int ans = 0;
for(int i=0; i<nums.length; ++i){
int sum = 0;
for(int j=i; j<nums.length; ++j){
sum+=nums[j];
if(sum==k) ans++;
}
}
return ans;
}
}
|
（2）前缀和优化
我们知道前缀和这一技巧计算某个区间的和只需要O（1）时间。
那么题目转化为：求有多少个区间【l，r】和为K，其中l和r范围是0～N-1，且l<r。
具体的解题过程就变成了两层循环：
1
2
3
4
5
6
| for(int r=0; r<N; ++r){
for(int l=0; l<=r; ++l){
}
}
|
但是时间复杂度并没有减少，因为枚举区间范围还是N^ 2。
（3）前缀和+哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int subarraySum(int[] nums, int k) {
int N = nums.length;
int[] preSum = new int[N];
preSum[0] = nums[0];
for(int i=1; i<N; ++i){
preSum[i] = preSum[i-1]+nums[i];
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int ans = 0;
for(int j=0; j<N; ++j){
if(map.containsKey(preSum[j]-k)) {
ans += map.get(preSum[j]-k);
}
map.put(preSum[j], map.getOrDefault(preSum[j], 0)+1);
}
return ans;
}
}
|
计算公式：$presum[j] - presum[i] = k$ ，那么 $presum[j] -k = presum[i]$
转换思路：考虑以$j$为右端点的区间，其区间和为K的个数。这等价于求多少个$i<j$，满足 $presum[i] = presum[j] -k $
等等，这个公式有点熟悉？力扣梦开始的地方，力扣第一题，两数之和
接下来的思路就很明朗了，空间换时间，利用哈希表提前存每个presum[i]。
细节注意：前缀和的下标对应问题，比如preSum[i+1] 为从0到i得区间和。
map.put(0, 1); 的作用：其实还是前缀和下标对应的问题。当我们要计算第一个区间，即[0,0]的区间和时，我们采用了preSum[0]-0的实现。