代码随想录笔记——哈希表
定义
也叫散列表，哈希表是一种“通过 key 快速找到 value 的数据结构思想”，并不是一种新的数据结构。
用key访问对应的value
特点
- 可以O(1)的时间复杂度进行元素查询、添加、删除
- 牺牲空间换取时间：哈希表中有一部分空间是浪费的。
什么时候用
当遇到要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
基本操作
初始化、查询操作、添加键值对和删除键值对等，在python中用字典实现：
hmap:dict={}hmap['a']=1hmap['b']=2#查询n=hmap['a']#删除hmap.pop('a')#三种遍历#遍历键值对forkey,valueinhmap.items():#遍历keyforkeyinhmap.keys():#遍历valueforvalueinhmap.values():哈希函数
将key转换为更规范的数组索引（相当于对key归一化）
- 输入key, 输出index
- 常见哈希函数：对数组长度取余（对应用数组实现哈希表的情况，比如数组（list）的长度是20，现在有20个键值对，我们想让数组的元素就是键值对的值，为了让key直接索引到对应的value，需要把key归一化为数组的索引：0到19）
- 哈希函数的特点：输入空间大于输出空间。以数组型哈希表为例，输出的是数组索引，0-len(nums)-1,但是key的范围是无限的。这也引出的了哈希函数的关键问题——哈希冲突
哈希冲突
当哈希函数的多个输入对应一个输出时（多对一），存在索引冲突。
简单粗暴的解决方式是直接扩容输出空间的范围，比如用，但效率低。
相关概念：负载因子
定义为哈希表中元素数量除以桶数量，反映了哈希冲突的严重程度，常用作触发哈希表扩容的条件
哈希表的结构改良方法主要包括链式地址和开放寻址
链式地址
本来一个位置只能存一个键值对（元素），当多个元素指向一个索引时，可用链表将他们连起来，设置其中一个为头结点，将所有发生冲突的键值对都存储在同一链表中。
操作
- 查询：key先根据哈希函数找到这个索引——找到链表的头结点，然后进入链表，当key与链表中某一个pair.key相等时，就找了对应的value
- 删减：遵循链表的删减规则
缺点
- 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
- 查询效率降低：因为需要线性遍历链表来查找对应元素。
开放寻址
1. 线性检测
- 当插入键值对时发现index的对应位置已有了其他键值对，便从当前索引开始，继续向后依次寻找位置，直到发现某个index位置是空的，把pari插入进去。
- 如何查询：当发现key由哈希函数映射的index对应的pair.key不是当前的key,从这个位置开始，逐个对比pair.key,直到找到自己。
缺点：
- 有聚集效应
- 无法删除起冲突的键值对（所有开放选址的共性问题），比如由两个index内的pair的key是相同的，如果删除index = hash_function(key)那个位置的，那么它的位置就是None，之后如果需要查找另一个pair，当发现了第一个index的位置的none,就不会再继续遍历了，会认为这个哈希表里没有需要的pair。
- 解决方法是需要删除时，把None替换成TOMBSTONE，当被检测到这个字符时，还可以继续查询。
- 同时为了避免一个哈希表前面的TOMBSTONE过多，发现一个就把它和目标pair的位置互换一下，提高查找效率。
2. 平方检测
- 减缓聚集效应
线性检测是从冲突的位置之后逐一检测空位情况，index+1,index+2,index+3…
平方检测是从冲突位置开始，跳过“探测次数的平方”的步数，index+1,index+4,index+9…
3. 多次哈希
使用不止一个哈希函数，当一个映射冲突时，就换另一个
不同的语言解决哈希冲突的方式不同，Python 的 Dict 采用开放寻址
说明
上述解决哈希冲突的思路（链式地址，开放选址）是“出现哈希冲突时仍能正常工作”。但是这些解决方式会提高哈希表查询的复杂度，如果冲突严重，查询的复杂度可能从O(1)变为O(n)
哈希算法
哈希算法指的就是哈希函数，解决哈希冲突的另一个想法。哈希算法的思路是通过设计哈希函数，使其尽可能避免冲突（多对一的映射），通过哈希函数让键值对在哈希表中的分布更均匀。
常见哈希算法：一般使用一些标准哈希算法，如 MD5、SHA-1、SHA-2 和 SHA-3 等
不同的编程语言有其内置哈希算法，python可以调用
hash()函数来计算各种数据类型的哈希值