哈希表理论知识：
链接：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
哈希表解决的问题：一般哈希表都是用来快速判断一个元素是否出现集合里
哈希函数（hash function ）：通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了
如果hashCode得到的数值大于哈希表大小，也就是大于tableSize了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作
哈希碰撞：有几位学生的名字同时映射到哈希表同一个索引下标的位置
解决方法：
1. 拉链法
发生冲突的元素都被存储在链表中：其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间
2. 线性探测法
使用线性探测法，一定要保证tableSize（哈希表大小）大于dataSize（数据规模）：需要依靠哈希表中的空位来解决碰撞问题
常见的三种哈希结构
1. 数组
2. set（集合）
3. map（映射）
unordered_set和unordered_map：底层实现为哈希表，当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset
set、multiset、map、multimap：底层实现为红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，且key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加；map是key value的结构中，对key有限制，但是对value没有限制
java里：HashMap和TreeMap
242.有效的字母异位词
题目链接：https://leetcode.cn/problems/valid-anagram/
这道题目用数组来解，数组也可以看作是哈希表，其下标是key，元素是value
需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值
三个两个并列的for循环可以解决此题，时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)
注意⚠️：在Java中，String中取元素用的是s.charAt(i)，且String的大小是s.length()，String的大小是固定的，如果需要改变字符串大小，需要用StringBuffer或者StringBuilder
349. 两个数组的交集
题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/
解答：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html
这道题用set来解决，没有特殊要求就用unordered_set，即Java中用HashMap来实现
要求：输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序，所以选择set数据结构也是合适的，set可以自动去重
先将nums1转化为unordered_set（set1），再逐个查找nums2的字母是否存在于unordered_set，如果存在，则添加到另一个unordered_set（resSet）中
for (int i: nums1){
set1.add(i);
}
for (int i : nums2){
if (set1.contains(i))
resSet.add(i);
}
最后再将resSet转化为数组：
方法1:
return resSet.stream().mapToInt(x->x).toArray();
方法2:
int[] arr = new int[resSet.size()];
int j = 0;
for(int i : resSet){
arr[j++] = i;
}
202. 快乐数
题目链接：https://leetcode.cn/problems/happy-number/
解答：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html
题目的关键点：“也可能是 无限循环 但始终变不到 1”；题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止
“对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和” 需要单独写一个函数来实现，函数体里面：
int ans=0;
while (n >0){
int temp = n%10;
ans = ans + temp*temp;
n = n/10;
}
return ans;
循环体中，条件是n！=1并且n不属于哈希表（record），此时将n加入到哈希表中，并让n替换为它每个位置上的数字的平方和，然后继续判断，直到n==1或者n属于哈希表，则停止循环
1. 两数之和
题目链接：https://leetcode.cn/problems/two-sum/
解答：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html
本题需要一个集合来存放遍历过的的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过；并且本题不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适
再来看一下使用数组和set来做哈希法的局限。
（1）数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
（2）set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用
这道题目中并不需要key有序，所以使用底层实现为哈希表的map结构效率更高
这道题 我们需要“给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。”
那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标
所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}
Map<Integer, Integer> map = new HashMap<>();
map.containsKey(key) 查询key是否存在
map.put(x,y) 将x和y作为key和value添加到map中
map.get(x) 取key为x的value值
由于题目条件中写了“你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现“因此只要找到一组元素，就可以break循环并返回了
主体：
for (int i=0; i<nums.length;i++){
int temp = target -nums[i];
if(record.containsKey(temp)){
res[1] =i;
res[0] = record.get(temp);
break;
}
record.put(nums[i], i);
}
