哈希和哈希桶_(哈希桶)

概念

数据结构中有一类常用于搜索，给定一个元素集合，常见的可用于搜索的算法有
遍历，遍历是十分粗暴简单的手段，对于元素的集合没有特殊要求，时间复杂度是O(N)。效率通常较低。
二分查找，二分查找要求元素集合有序，时间复杂度为O(logN),
二叉搜索树，查找规则简单，但是退化为单支树时间复杂度是O(N),
AVL树和红黑树，时间复杂度都是O(logN).

上面的这些常用的方法无一例外都有一个关键步骤就是元素的比较，通过比较待查找元素和集合中的元素，来确定该元素在集合中的位置。真实的效率取决于比较的次数。

如果有不需要进行元素比较就能查找的方法，就能达到理想的查找。

哈希就是这样一种数据结构，

在存储元素时，通过某些方法，将元素与所存储的位置建立一一对应的关系，则在查找时就可以不需要进行数据的比较。这种方法称为哈希散列方法。元素存储的集合称为哈希表或者散列表，建立映射关系的方法称为哈希函数或者散列函数。通过这个函数来计算元素来计算元素在哈希表中的插入位置。

比如，
元素集合：1 6 7 5 4 9
哈希函数：f(x) = x % capacity

插入元素时，通过哈希函数计算该元素在哈希表中的位置， 1%10 = 1，则1放在1号位置。

查找元素时，通过函数计算该元素在表格中的位置，检测该位置上存储的元素是否是待查找元素。

哈希冲突

如果新增一个元素11，通过哈希函数计算，结果应该插入在1的位置，此时该位置已经有元素了，这就是哈希冲突的产生原因，当不同的元素通过相同哈希函数计算出相同的哈希地址，这种问题成为哈希冲突。

哈希函数的设计

如果哈希函数的设计不合理，则会产生不同元素的哈希地址集中存在与某一段地址范围中，使得哈希冲突产生的概率非常高。因此哈希函数要求
1.函数的定义域必须包含所有要存储的关键码，散列表如果有m个地址，其值域必须在[0,m)之间。
2.哈希函数计算出来的地址要能均匀的分布在哈希表中。
3.哈希函数应尽量简单

常用的方法：
直接定址法，取关键字的某个线性函数作为散列地址， Hash = A*Key+B ，这种函数简单且分布均匀，但是要提前分析关键字的分布情况，适用于元素集合较小且连续的情况。比如查找字符串中只出现一次的字符。就可以采用直接定址法，将字符串中字符的ASCII码值作为数组下标，统计次数。

除留余数法，设散列表中的地址数为m，在不大于m的数中取一个接近或等于m的的素数p，设计
Hash = Key % p这样的方法计算哈希地址。是非常常用的一种方法。

平方取中法，比如关键字为1234，那它的平方就是1522756，取中间3位得到227作为哈希地址，5678的平方Wie23239684，则取中间的3位239或者396作为哈希地址。平方取中法比较适合不知道关键字的分布情况，关键字的位数又不是很大时用。

折叠法，首先将关键字分割成位数相等的几部分，比如关键字12345678，可以分为123,456,78,最后一个可以位数短一点，将分出来的数相加并根据散列表的容量取靠后的位数作为散列表地址。适合用于关键字位数较多的情况。

随机数法，取关键字的随机函数值作为哈希地址，Hash = random(Key),适合用于关键字长度不等的情况。

数学分析法，有n个位数相同的数字，每个位上都有r种不同的符号，出现概率不一定相同，可能在某几位上分布比较平衡，根据散列表的大小，选择符号分布较均匀的几位作为哈希地址，比如手机号码的集合，前三位的分布重复较多都是1几几，不均匀，而后四位分布较均匀。

哈希函数的设计只能尽量降低产生哈希冲突的概率，不论一个哈希函数设计的多么科学，都无法彻底避免哈希冲突的产生。

哈希冲突的解决方式

闭散列

在上面的例子中，如果要继续向哈希表中插入元素54，根据哈希函数算出的地址，应该插入在5的位置，而5的位置上已经有元素了，闭散列的处理方式在5的元素之后开始依次向后查找有没有非空的位置，找到了就将这个元素插入进去，如果找到末尾也没有，则返回表头从表头开始继续找非空的位置。
闭散列中，哈希表中的每个位置都增加了一个标识用来表示状态

EMPTY，表示该位置为空，EXIST，表示该位置上有有效元素，DELETE表示该位置元素被删除了。在插入时，通过哈希函数计算出地址后，先检测该位置有没有发生哈希冲突，如果没有发生就直接插入并将该位置状态修改为EXIST，删除时，先通过哈希函数计算表中的位置，发现该位置有元素，与待删除元素进行比较，如果是则直接删除，但是该位置的状态不能修改成EMPTY，应改为DELETE，因为如果该位置为空，则表明该元素不存在。
1

这种依次查找空位的方式称为线性探测，线性探测插入和删除的规则比较简单，但是存在一定缺陷，发生哈希冲突时，容易产生数据的堆积，导致堆积的元素占用大量空余的位置，增加查找时的时间消耗影响效率。

另一种方式称为二次探测，不再通过挨个去找空位的方式，下一个位置是通过H(i) = (H0 + i²) 或者H(i) = H0 - i²的方式去计算。与线性探测相比，能解决数据堆积的问题，但是线性探测最差情况下，走完一圈哈希表就能找到，而二次探测不能确定。当表中空位置比较少时，可能需要找很多次。

总的来说，当哈希表中的元素存了非常多的时候，表中的剩余位置越来越少，发生冲突的概率就越来越高，而且会影响探测的效率，哈希是追求高效查找的数据结构，而当哈希表中有效元素很多时，会大大影响效率。解决这个问题就需要哈希表中存储的元素不能太多，达到一定程序就要扩容，所以哈希表一定是不会存满的。具体什么情况下扩容，提到负载因子的概念，负载因子是有效元素/空间总数的值，有研究表明，线性探测负载因子达到70%左右就应该进行扩容，而二次探测负载因子达到50%就应该进行扩容。因此哈希也是一种空间利用率较低的数据结构。

开散列

开散列又称链地址法，相比于闭散列在开发中应用更多，开散列实际上是数据与链表的集合，数组中的每个元素都是单链表，链表上挂载发生哈希冲突的元素。

首先通过哈希函数计算出哈希地址，然后，具有相同哈希地址的元素归为一个集合中，称为一个桶，桶中的元素通过单链表组织起来。哈希表中存放链表的头，这种结构称为哈希桶。

根据哈希桶的规则，插入元素的理想状态，

而实际上，当插入的元素比较特殊时，依然会导致大部分元素集中在一个链表中，导致某些链表特别长，这样一来，在哈希桶中查找元素实际上变成了在链表中查找元素，链表的查询时间复杂度是O(N),因此插入元素也应该避免这种问题的出现。闭散列当中是通过根据负载因子来进行扩容的方式解决问题的。哈希桶也是如此，哈希桶的规则中，当哈希桶中元素的个数与桶的个数相等时，就要考虑扩容，哈希桶的容量改变后，哈希函数计算的地址也改变了，所以要将旧哈希桶中的元素搬移到新的哈希桶中。
有时候会有些更极端的情况，虽然没达到扩容的条件，但是某些链表中挂载的节点已经非常多了，哈希表的性能因此会下降，此时的处理方法是当链表中的节点达到一定的阈值还没有得到扩容时，将链表转换成红黑树。一般设计是当链表中节点的个数等于8的时候，就将链表转换为红黑树，删除时，当红黑树中的节点个数小于6的时候，再将红黑树转换位链表。

除留取余法的设计，除留取余法要取一个不大于表的容量但最接近于它的素数，在SGI-STL3.0版本中，hash_map底层给出了一个和除留取余法有关的确定素数的方法。将常用的28个素数枚举出来。
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
泛型设计：理想的哈希表应该能存储任意元素，但是有些元素不能直接取模运算，比如常见的字符串类型。atoi只能将数字类型的字符串转换为字符串格式，因此要借助一些其他的算法来实现取模的运算，有住专门设计的字符串哈希算法等。

实现一个简单的哈希桶

#pragma once

#include<iostream>
#include"Common.h"
#include<vector>

using namespace std;

template<class T>

struct HashBucketNode {
   
	HashBucketNode<T>* next;
	T data;

	HashBucketNode(
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15