理论
参考的这篇原地址
首先什么是 哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
哈希表是根据关键码的值而直接进行访问的数据结构。
这么这官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。
哈希表中关键码就是数组的索引下表，然后通过下表直接访问数组中的元素，如下图所示：
那么哈希表能解决什么问题呢，「一般哈希表都是用来快速判断一个元素是否出现集合里。」
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1) 就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了「hash function ，也就是哈希函数」。
哈希函数
哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下表快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？
此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。
此时问题又来了，哈希表我们刚刚说过，就是一个数组。
如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下表的位置。
接下来「哈希碰撞」登场
哈希碰撞
如图所示，小李和小王都映射到了索引下表 1的位置，「这一现象叫做哈希碰撞」。
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
拉链法
刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了
（数据规模是dataSize， 哈希表的大小为tableSize）
其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示
其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。
常见的哈希结构
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
第一章 数组哈希
刷题第一站
242. 有效的字母异位词
这道题有两种解法，一种就是排序
题解中对这种算法的空间复杂度分析，我不理解。
class Solution {public boolean isAnagram(String s, String t) {char[] str1 = s.toCharArray();char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}}
另一种是哈希表，这里的哈希表用的是数组，我们发现用这种的一般都是原数据是字符的。
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false; // 这句话必须写，上一个写法可以不写
int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
table[t.charAt(i) - 'a']--;
if (table[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
49. 字母异位词分组
这道题是和242相似的题目。
解法一：排序后作为键
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
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);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
解法二：计数作为哈希表的键
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
438. 找到字符串中所有字母异位词
这道题和242相似。
时间复杂度是O(s.length()*p.length())
空间复杂度是O(26)，可以说是常数项。不知道你会不会认为是O(s.length())。
你也可以把下面的代码理解成滑动窗口，只是这个窗口是固定大小的。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<Integer>();
if (s == null || p == null || s.length() < p.length()) return list;
int sL = s.length();
int pL = p.length();
for (int i = 0; i < sL - pL + 1; i++) {
if (checkIsAnagram(s, i, pL, p)) {
list.add(i);
}
}
return list;
}
private boolean checkIsAnagram(String s, int index, int pL, String p) {
int[] table = new int[26];
for (int i = index; i < index + pL; i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < pL; i++) {
table[p.charAt(i) - 'a']--;
if (table[p.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
567. 字符串的排列
该题类似于438.
方法一：滑动窗口
由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<Integer>();
if (s == null || p == null || s.length() < p.length()) return list;
int sL = s.length();
int pL = p.length();
for (int i = 0; i < sL - pL + 1; i++) {
if (checkIsAnagram(s, i, pL, p)) {
list.add(i);
}
}
return list;
}
private boolean checkIsAnagram(String s, int index, int pL, String p) {
int[] table = new int[26];
for (int i = index; i < index + pL; i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < pL; i++) {
table[p.charAt(i) - 'a']--;
if (table[p.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
383. 赎金信
因为题目所只有小写字母，那可以采用空间换取时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数。
然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
依然是数组在哈希法中的应用。
一些同学可能想，用数组干啥，都用map完事了，「其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数。所以数组更加简单直接有效！」
这道题和242一模一样！
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] table = new int[26];
for (int i = 0; i < magazine.length(); i++) {
table[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
table[ransomNote.charAt(i) - 'a']--;
if (table[ransomNote.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
HashSet
刷题第一站
349. 两个数组的交集
注意题目特意说明：「输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序」
这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。
可以发现，貌似用数组做哈希表可以解决这道题目，把nums1的元素，映射到哈希数组的下表上，然后在遍历nums2的时候，判断是否出现过就可以了。
但是要注意，「使用数据来做哈希的题目，都限制了数值的大小，例如LeetCode 242 题目中只有小写字母，或者数值大小在[0- 10000] 之内等等。」
而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
「而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。」
此时就要使用另一种结构体了，set
方法一：两个集合
计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。假设数组 nums1 和 nums2 的长度分别是 m 和 n，则遍历数组 nums1 需要 O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间，因此总时间复杂度是 O(mn)。
如果使用哈希集合存储元素，则可以在 O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。
首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
set2.add(num);
}
return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
if (set1.size() > set2.size()) { // 这个是真的秒啊
return getIntersection(set2, set1);
}
Set<Integer> intersectionSet = new HashSet<Integer>();
for (int num : set1) {
if (set2.contains(num)) {
intersectionSet.add(num);
}
}
int[] intersection = new int[intersectionSet.size()];
int index = 0;
for (int num : intersectionSet) {
intersection[index++] = num;
}
return intersection;
}
}
方法二：排序+双指针
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[length1 + length2];
int index = 0, index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
// 保证加入元素的唯一性
if (index == 0 || num1 != intersection[index - 1]) {
intersection[index++] = num1;
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
202. 快乐数
方法一：set
class Solution {
public boolean isHappy(int n) {
if (n < 1) return false;
Set<Integer> set = new HashSet<>();
while (true) {
int next = getNext(n);
if (next == 1) {
return true;
}
if (set.contains(next)) {
return false;
}
set.add(next);
n = next;
}
}
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
}
HashMap
刷题第一站
LeetCode 1 两数之和，这道题已经完成了。
LeetCode 454 也是使用HhashMap的！！已完成过了！
总结
若有收获，就点个赞吧
0 人点赞
