c++——哈希

概念

哈希是一种搜索数据结构，不过哈希搜索不同于顺序搜索和二叉搜索的是：哈希可以不经过任何比较，一次直接从表中得到要搜索的元素。它是通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数就可以直接找到该元素。

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

哈希冲突

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间的大小。

用上面的方法进行元素搜索不必进行多次值的比较，因此搜索的速度比较快 。但是如果再次输入一个21或24等数时，就会发现其函数值所对应的位置已经有数据了。这就被称为哈希冲突。

即不同元素通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

常见的哈希函数

1、 直接定制法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀
缺点：需要事先 知道关键字的分布情况 使用场景：适合查找比较小且连续的情况

2、 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函 数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3.、平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为 4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 。

哈希冲突解决方法

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

找到下一位置的方法：
1、线性探测法
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

例：
对上面的例子插入21和24时

线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

2、二次探测法
二次探测：找下一个空位置的方法为：pos = ( cur+i^2)% m。其中：i = 1,2,3…， cur是通过散列函数Hash(x)对元素的关键码key 进行计算得到的位置，m是表的大小,pos是空位置。

还是上面的例子，插入24时，位置下标变化：4->5->8

注意：当表的长度为质数且表负载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装 满的情况，但在插入时必须确保表的负载因子a不超过0.5，如果超出必须考虑增容。

载荷因子（负载因子）
a=填入表中的元素个数 / 散列表的长度
对于开放定址法，负载因子最好不要超过0.7-0.8.

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

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

对于插入同一位置的元素，可以使用头插，也可以使用尾插。

增容
不同于闭散列的增容是由负载因子决定，开散列的增容是在元素个数刚好等于桶的个数时，可以给哈希表增容。