【20230206-0209】哈希表小结

哈希表

一般哈希表都是用来快速判断一个元素是否出现在集合里。

哈希函数

哈希碰撞--解决方法：拉链法和线性探测法。

拉链法：冲突的元素都被存储在链表中

线性探测法：一定要保证tableSize大于dataSize，利用哈希表中的空位解决碰撞问题。

三种哈希结构

数组、set（集合）、map（映射）

set与map的共同点：

set、map都是C++的关联容器，只是通过它提供的接口对里面的元素进行访问，底层都是采用红黑树实现。

set与map的不同点：

set：用来判断一个元素是否在一个组里。

map：映射，相当于字典，把一个值映射成另一个值，可以创建字典。

set

map

小结

当要用集合来解决哈希问题时，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合有序，就用set，要有重复数据，就用multiset。

---

1.为什么要成倍的扩容，而不是一次增加一个固定大小的容量？

保证常数的时间复杂度。

2.为什么以两倍方式扩容？

考虑可能产生的堆空间浪费，所以增长倍数不能太大。

3.为什么insert后，以前保存的iterator不会失效？

因为map和set储存的是节点，不需要内存拷贝和内存移动。但是vector在插入数据时如果内存不够，会重新开辟一块内存。map和set的iterator指向的是节点的指针，vector指向的是内存的某个位置。

4.为什么map和set的插入删除效率比其他序列容器高？

因为map和set底层实现为红黑树，插入和删除的时间复杂度为O(logn)。

---

例题：

1. 有效的字母异位词（小写字母，用数组！）

2. 赎金信（与有效的字母异位词类似）

3. 两个数组的交集(输出结果是去重的，无序的，用unordered_set)

4. 两个数组的交集II（哈希映射，有重复元素）

5. 字母异位词分组（字符串排序的效果、通过设计哈希表中的键值进行归类）

6. 快乐数（各个位上数的提取、判断是否有重复的数字出现，是否出现了死循环或者出现了1）

7. 两数之和（经典，利用哈希查询效率高）

8. 四数相加II(四个数组，两两分组)

//9、10使用双指针

9. 三数之和(双指针法，对三个元素的去重)

10. 四数之和（与三数之和类似，在一级剪枝时，判断条件要注意，nums[i]>0且target>0，对各个元素进行去重）