哈希表
- 什么是哈希表
哈希表是根据关键码的值而直接进行访问的数据结构。
简单的例子：数组
-
什么时候想到用哈希法
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。 -
哈希碰撞
元素通过哈希函数被映射到同一个索引下标位置
解决方法：
- 拉链法
从发生冲突的位置拉出一条链表，发生冲突的元素都被存储在链表中。
- 线性探测法
要保证tabelSize大于dataSize, 我们需要依靠哈希表中的空位来解决碰撞问题。
如果位置i冲突，就向下找i+1来存储另一个数据。
- 常见的三种哈希结构
数组、set(集合)、map（映射）
C++中，std::unordered_set、std::unordered_map底层实现为哈希表
242.有效的字母异位词
内容：给定两个字符串 s和t，编写一个函数来判断t是否是s的字母异位词。
题目链接：https://leetcode.cn/problems/valid-anagram/
思路：定义一个大小为26的数组，记录各个字母出现的次数。
小技巧：一个record数组，一次遍历次数++，一次遍历次数--，就不需要定义两个record数组了。
349. 两个数组的交集
内容：
给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是唯一 的。我们可以 不考虑输出结果的顺序。
链接：https://leetcode.cn/problems/intersection-of-two-arrays/
思路：要学会使用一种哈希数据结构：unordered_set，对于没有限制数值大小的题目，不能用数组。
202. 快乐数
链接：https://leetcode.cn/problems/happy-number/
思路：题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止
1. 两数之和
链接：https://leetcode.cn/problems/two-sum/
思路：因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。