1. 哈希表基础
1.1 概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( 
)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快
找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
- 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
1.2 冲突-概念
对于两个数据元素的关键字 和 (i != j)，有!= ，但有：Hash( ) == Hash( )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
1.3 冲突-解决
解决哈希冲突两种常见的方法是：闭散列和开散列
1.4 冲突-解决-闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
线性探测
比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入：
- 通过哈希函数获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
1.5冲突-解决-开散列/哈希桶
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了
2. LeetCode 242.有效的字母异位
2.1 思路
- 本题全由小写字母组成，“a-z”，ASCII码值是连续的，那么a可以对应到数组下标为0的位置，z可以对应到数组下标为25的位置，因此定义一个哈希数组长度为26即可
- 先用数组统计第一个字符串每一个字母出现的频率，在数组做对应的加法
- 再用数组统计第二个字符串每一个字母出现的频率，在数组做对应的减法
- 如果最后遍历数组所有位置的值都为0那说明对了
- 关于哈希表什么时候用数组、set、map？哈希值比较小且范围小可控用数组，数值很大用set，有k对应value就用map
2.2 代码
/** * 242. 有效的字母异位词 字典解法 * 时间复杂度O(m+n) 空间复杂度O(1) */ class Solution { public boolean isAnagram(String s, String t) { int[] record = new int[26]; for (int i = 0; i < s.length(); i++) { record[s.charAt(i) - 'a']++; // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了 } for (int i = 0; i < t.length(); i++) { record[t.charAt(i) - 'a']--; } for (int count: record) { if (count != 0) { // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。 return false; } } return true; // record数组所有元素都为零0，说明字符串s和t是字母异位词 } }
3. LeetCode 349. 两个数组的交集
3.1 思路
- 为什么用哈希表？哈希表最擅长于解决给你一个元素判断在这个集合里是否出现过这种情况，就用数组或者map或者set
- 数值很大的话做哈希映射时用数组就不合适了，太浪费了，就用set做（什么时候用map后面说）
- 把nums1里的所有数值放入set1中，然后遍历nums2，遍历时去set1里查询是否出现过，如果出现过再放入set2中，这个集合是去重（因为Set不允许有相同的元素出现）的（两个2的话就只有一个1）
3.2 代码
import java.util.HashSet; import java.util.Set; 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<>(); //遍历数组1 for (int i : nums1) { set1.add(i); } //遍历数组2的过程中判断哈希表中是否存在该元素 for (int i : nums2) { if (set1.contains(i)) { resSet.add(i); } } //方法1：将结果集合转为数组 return resSet.stream().mapToInt(x -> x).toArray(); //方法2：另外申请一个数组存放setRes中的元素,最后返回数组 int[] arr = new int[resSet.size()]; int j = 0; for(int i : resSet){ arr[j++] = i; } return arr; } }
4. LeetCode 202. 快乐数
4.1 思路
- 通过set判断n是否在一个集合里
- 关键点：将n转化为各个位上的平方和，先%10方式求得最后一位上的数，然后平方加到result上，然后n/10将最后一位上的数去掉，这样就求得各个位上的平方和
- 判断条件：n!=1并且n没有进入过set集合中，如果进入过还进去就陷入无限循环了
4.2 代码
class Solution { public boolean isHappy(int n) { Set<Integer> set=new HashSet<>(); //如果这个数不是1并且set里没有这个数（有的话还进去就无限循环了） while(n!=1&&!set.contains(n)){ set.add(n); n=getNextNum(n); } return n==1; } public static int getNextNum(int n){ int result=0; int temp=0; //将n替换为各个位上的平方和 while(n>0){ temp=n%10; result+=temp*temp; n/=10; } return result; } }
5. LeetCode 1. 两数之和
5.1 思路
- 什么时候用哈希表？给你一个元素判断在这个集合里是否出现过，这题里遍历一个元素的时候我们判断另一个需要的元素是否遍历保存过，比如这题target是9，你遍历到3时就要判断是否遍历保存过6，因为3+6=9
- 什么时候用数组还是set还是map？这题里我们想要找一个元素，这个元素出现过，同时还要知道这个元素在数组里的下标，即需要<元素，下标>，用数组和set都不行了，就用map的key和value
- 又因为我们要查找的是元素是否出现过，因此把元素作为key，下标作为value
5.2 代码
public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; if(nums == null || nums.length == 0){ return res; } Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ int temp = target - nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key if(map.containsKey(temp)){ res[1] = i; res[0] = map.get(temp); break; } map.put(nums[i], i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中 } return res; }
