C++笔记20•数据结构:哈希(Hash)•

哈希

1.无序的关联式容器（unordered_map&unordered_set） 

unordered_map与unordered_set几乎与map与set是一样的，只是性能unordered_map与unordered_set比map与set更优一些。还有就是unordered_map与unordered_set是无序的，map与set是有序的（会将数据进行排序）。

unordered_map：官方实现

unordered_set：官方实现

unordered_map、unordered_set与map、set对比与联系：

• 都可以可以实现key和key/value的搜索场景，并且功能和使用基本一样。
• map/set的底层是使用红黑树实现的，遍历出来是有序的，增删查改的时间复杂度是0(logN)
• unordered_map/unordered_set的底层是使用哈希表实现的，遍历出来是无序的，增删查改的时间复杂度是O(1)(不是1次，是常数次)，说明性能比map/set更优一些
• map和set是双向迭代器，unordered_map和unorded_set是单向迭代器。
• unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.哈希表

2.1哈希概念：

     顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过关键码的多次比较
。
顺序查找时间复杂度为
O(N)
，平衡树中为树的高度，即
O(log N)，搜索的效率取决于搜索过程中元素的比较次数。

     
※理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

    如果构造一种存储结构，通过某种函数
(hashFunc)
使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素
。

解释说明插入和搜索：

当向该结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置

取元素比较，
若关键码相等，则搜索成功

       该方式即为哈希
(
散列
)
方法，
哈希方法中使用的转换函数称为哈希
(
散列
)
函数，构造出来的结构称
为
哈希表
(Hash Table)(
或者称
散列表
)。

举例：

数据集合
{1
，
7
，
6
，
4
，
5
，
9}
；

哈希函数设置为：
hash(key) = key % capacity
;

key为待插入的值（1
，
7
，
6
，
4
，
5
，
9）

capacity为存储元素底层空间总的大小（申请的存储空间的容量）。

但是：这种插入看似合理，但是也有很大的弊端，
如果插入11呢?

hash(11)=11%10=1,1映射过去，1的位置已经被占了。这个问题就是
哈希冲突？

2.2哈希冲突

     对于两个数据元素的关键字key_i和 key_j(i != j)，有key_i != key_j，但有：Hash(key_i) == Hash(key_j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突
或哈希碰撞
。

       引起哈希冲突的一个原因可能是：
哈希函数设计不够合理
。

       哈希函数设计原则
：

•  哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

2.3常用的哈希函数：

2.3.1
. 直接定址法
–(
常用
)

取关键字的某个线性函数为散列地址：
Hash
（
Key
）
= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

2.3.2. 除留余数法–(常用)

设散列表中允许的
地址数为
m
，取一个不大于
m
，但最接近或者等于
m
的质数
p
作为除数，

按照哈希函数：
Hash(key) = key% p(p
将关键码转换成哈希地址

2.3.3
. 平方取中法
–(
不常用
)

假设关键字为
1234
，对它平方就是
1522756
，抽取中间的
3
位
227
作为哈希地址；

再比如关键字为
4321
，对它平方就是
18671041
，抽取中间的
3
位
671(
或
710)
作为哈希地址

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

2.3.4
. 折叠法
–(不常用
)

折叠法是将关键字从左到右分割成位数相等的几部分
(
最后一部分位数可以短些
)
，然后将这

几部分叠加求和，并按散列表表长，取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4哈希冲突解决方法：解决哈希冲突两种常见的方法是：闭散列和开散列

2.4.1
闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把
key
存放到冲突位置中的
“
下一个
”
空位置中去。

• 线性探测 ：  从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，一次只前进一个

           

• 二次探测 ：  从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。一次前进i^2个

2.4.2 开散列

     开散列法又叫链地址法
(
开链法
)
，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。所以这个哈希表也就是一个存储节点指针的指针数组。

开散列中每个桶中放的都是发生哈希冲突的元素
。