|
标题：[C++] 哈希布局的哈希冲突 && 办理哈希冲突
@水墨不写bug
目录
一、引言
1.哈希
2.哈希冲突
3.哈希函数
二、办理哈希冲突
1.闭散列
I，线性探测
II，二次探测
2.开散列
正文开始：
一、引言
哈希表是一种非常实用而且好用的关联式容器，如果你刷过不少题，肯定会惊叹哈希竟然能办理如此多的实际问题。
但是哈希表令人头疼的问题是哈希冲突的问题。在具体讲解之前，我们先铺垫引入几个概念：哈希，哈希函数，哈希冲突。
1.哈希
哈希布局最明显的特点是高效。在以往的顺序布局以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比力。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2 N)，搜索的效率取决于搜索过程中元素的比力次数。
最优的搜索方法：不经过任何比力，一次直接从表中得到要搜索的元素。
如果存在一种存储布局，通过某种函数(hashFunc)使元素的存储位置与它的关键码（key）之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当我们向该布局中：
插入元素的时候：根据插入元素的关键码，根据这个关键码来通过某种映射关系来得到哈希表中对应的存储位置，然后将这个元素存入哈希表的对应位置。
搜索元素的时候：对元素的关键码进行同样的盘算，把求得的函数值当做元素的存储位置，在哈希表中按照此位置进行查找，若关键码相等，则搜索乐成。
这种存储布局和方法统称为哈希。
哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的布局称为哈希表(Hash Table)(或者称散列表).
2.哈希冲突
我们可以计划一个简单的哈希表：10个位置，哈希函数也是非常简单的除留取余（插入元素除以表的大小，就通过哈希函数得到了这个值应该在表中存储的位置）：
用该方法进行搜索可以一次找到存储对应值的位置，因此搜索的速率比力快。
但是，如果向上面如许的哈希表中插入14呢？
我们发现14的位置被4占据了，这就是哈希冲突。
即：不同关键字通过相同哈希哈数盘算出相同的哈希地点，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地点的数据元素称为“同义词”.
3.哈希函数
引起哈希冲突的一个缘故原由可能是：哈希函数计划不敷合理。
哈希函数计划原则：
1.哈希函数的界说域必须包括必要存储的全部关键码，同时如果散列表允许有m个地点时，其值域必须在0到m-1之间。
2.哈希函数盘算出来的地点能尽可能的匀称分布在整个空间中。
3.哈希函数应该比力简单。
我们必要了解一下常见的哈希函数的计划方法：
1. 直接定址法
取关键字的某个线性函数为散列地点：Hash（Key）= A*Key + B
优点：简单、匀称、一样平常不会出现哈希冲突
缺点：必要事先知道关键字的分布环境
使用场景：适合查找比力小且一连的环境
2. 除留余数法.
设散列表中允许的地点数为m，取一个不大于m，但最靠近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地点.
优点：实用环境广泛
缺点：会出现哈希冲突，必要办理哈希冲突的问题
二、办理哈希冲突
哈希冲突的办理方法常用的有两种：闭散列与开散列。
1.闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中肯定还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
寻找下一个“空位置”也有多种方法，这里先容常见的两种：线性探测，二次探测。
I，线性探测
在上面的例子中，我们想要插入14，原来14经过哈希函数盘算得到的位置是4，但是4这个位置已经被占据了。
线性探测就是：从发生冲突的位置开始，一个一个向后探测，直到寻找到下一个空位置为止。
a.插入
起首通过哈希函数获取待插入元素在哈希表中的位置。 如果该位置中没有元素则直接插入新元素；如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素：
b.删除
采用闭散列处置处罚哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。
比如：删除元素4，如果直接删除掉，14查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
我们可以通过一个标记状态的变量来表现哈希表内的数据的状态：存在，删除，空（EXIST,DELETE,EMPTY）:
- enum STATE
- {
- EXIST,
- DELETE,
- EMPTY
- }
如果存在元素，状态为EXIST；
如果原来存在元素，但是之后删除了，状态为DELETE；
不同的状态对于将来查找（find）的处置处罚会有影响。
II，二次探测
通过了解上面的线性探测，你自然也会发现线性探测的困难：
产生冲突的数据堆积在一块，这与其一个一个向下找空位置有关系，找空位置的方式就是挨着今后逐个去找.
二次探测的找下一个空位置的方法就大不相同了：二次探测向下找的方式是依次加上位置差的平方：
H_i = (H_0 + i^2 )% m 或者H_i = (H_0 - i^2 )% m
此中：i = 1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key 进行盘算得到的位置，m是表的大小。
对于上面的例子，如果使用二次探测，插入的过程：
插入 44 的过程：
1.44 的初始哈希值是 14 % 10 = 4 ，但是位置 4 已经被占用了。
2.触发二次探测，从 i = 1 开始。对于 i = 1 ，探测位置是：(4 + 1^2) % 10 = 5 但位置 5 也被占用了。
3.继承探测， i = 2 时，探测位置是：(4 + 2^2) % 10 = 8
位置 8 是空的，以是 14 被插入到位置 8。
对于闭散列而言，哈希表是必要扩容的，由于我们每次插入的时候都必要包管哈希表有空余的位置，以是我们必要一个判定哈希表内数据 装满水平的标记因子：载荷因子
载荷因子记为a，a越大，表明填入表中的数据越多，产生哈希冲突的可能就越大。反之则相反。
对于开放定址法，载荷因子必要严格控制在0.7-0.8以下。当载荷因子靠近这个值时，就必要扩容。
2.开散列
开散列法又叫链地点法(开链法)，起首对关键码集适用散列函数盘算散列地点，具有相同地点的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中:
当插入14时，对4这个位置的链表头插即可：
以上是哈希布局办理哈希冲突的方法。
完~
未经作者同意克制转载
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 | 
