哈希表

• 什么是哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。

简单的例子：数组

• 什么时候想到用哈希法
  当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

• 哈希碰撞

元素通过哈希函数被映射到同一个索引下标位置

解决方法：

1. 拉链法

从发生冲突的位置拉出一条链表，发生冲突的元素都被存储在链表中。

2. 线性探测法

要保证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正合适。