leetcode-代码随想录-哈希表-哈希理论基础

哈希表理论基础

哈希表：或者称为散列表，是根据关键码的值而直接进行访问的数据结构。

哈希法：用于快速判断一个元素是否出现在集合里

哈希函数是⼀种映射关系，根据关键词key，经过⼀定函数关系 f 得到元素的位置。
存储位置 = f (关键字)
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。

把这种对应关系 f 称为散列函数，又称为 哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这种连续的存储空间称为散列表或哈希表。关键字对应的记录存储位置称为散列地址。

散列技术既是一种存储方法，也是一种查找方法。

最适合查找的求解问题是查找与给定值相等的记录 / 用来快速的判断一个元素是否出现在集合里。

直白来讲其实数组就是一张哈希表；
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

哈希函数

例如要查询一个名字是否在这所学校里。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

常见的哈希函数构造方法

1. 直接定址法：

取关键字或关键字的某个线性函数值为散列地址。
fkey) = a * key + b，其中a和b为常数
简单、均匀，不会产生冲突，适合查找表较小且连续的情况。

2. 除留余数法：

取关键字被某个不大于散列表长度m 的数 p 求余，得到的作为散列地址。
f(key) = key % p, p < m 。
通常 p 为小于或等于表长 m 的最小质数或不包含小于20质因子的合数。

3. 叠加法：

将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
用于关键字位数较多，并且关键字中每⼀位上数字分布⼤致均匀。

4. 随机数法：

选择⼀个随机函数，把关键字的随机函数值作为它的哈希值。
f(key) = random(key)。random是随机函数。
通常当关键字的⻓度不等时⽤这种⽅法。
当关键字是整数类型时就可以⽤除留余数法；如果关键字是⼩数类型，选择随机数法会⽐较好

哈希碰撞

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
哈希冲突的解决：

1. 开放地址法（前提是散列表的长度大于等于所要存放的元素）：

发⽣哈希冲突后，按照某⼀次序找到下⼀个空闲的单元，把冲突的元素放⼊。
fi(key) = (f(key) + di) mod m (di是一个随机数列)

2. 平方探查法：

从发生冲突的单元加上1²,2²,3²,…,n²，直到遇到空闲的单元

3. 再散列函数法：

事先准备多个散列函数，当发生冲突时，就换一个散列函数计算，总有一个可以把冲突解决掉。

4. 链地址法：

将哈希值相同的元素构成⼀个链表，head放在散列表中。⼀般链表长度超过了8就转为红⿊树，⻓度少于6个就变为链表。 缺点：指针需要额外的空间

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

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

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。