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<=m), 将关键码转换成哈希地址

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 开散列

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

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