download：海量数据高并发场景 构建Go+ES8企业级搜索微服务内置文档
哈希表查找哈希算法的定义与实现
1哈希表查找定义
哈希技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字对应一个存储位置。
存储位置=f(关键字)
对应关系称为哈希函数，也称为哈希函数。
哈希技术用于将记录存储在一个连续的存储空间中，称为哈希表或哈希表。哈希技术不仅是一种存储方法，也是一种搜索方法。
Hash函数可能将两个或多个不同的关键字映射到同一个地址，称这些情况为冲突，而这些冲突的不同关键字称为同义词。
2哈希函数的构造方法
3.1直接寻址方法
对于关键字age，可以直接用age的数量作为地址，其中f(key)=key。
如果要统计1980年以后出生年份的人口，如下图所示，可以用年份减去1980作为出生年份关键字的地址。此时f(key)=key-1980。
直接关键字去除的线性函数值是哈希地址，哈希函数是:
直接寻址法的哈希函数简单、统一且不会引起冲突，但需要事先知道关键字的分布，所以适用于小而连续的查找表。
3.2除法和余数法
除余数法是构造哈希函数最常用的方法。假设哈希表长度为M，取一个不大于M但最接近或等于M的素数P，哈希函数为:
假设我们有12个记录的关键字来构造哈希表，例如，我们使用新方法，所以它存储在下标5处。
根据经验，如果哈希表长度为M，通常P是小于等于表长度的最小素数(最好接近M)或者是不包含少于20个素数因子的合数。
处理哈希冲突的3种方法
3.1开放地址方法
3.1.1线性检测方法
开放式寻址方法是一旦有冲突就寻找下一个空的散列地址。只要哈希表足够大，总是可以找到空的哈希地址，并且记录将被存储。
在一个简单的例子中，我们的关键字集是，表长度是12。我们使用散列函数。
计算前五个数时，都是哈希地址，没有冲突，直接存储。
计算key=37时，发现与25的位置冲突，于是重新计算，37存储在下标2的位置，如图。
当key=48时，我们计算出和12所在的位置0冲突。继续算，和25的位置冲突，所以一直到都没有空缺，如图。
这种解决冲突的开放式寻址方法称为线性检测方法。
二次检测
那时候叫二次检测法。增加正方形操作的目的是为了防止所有关键词都聚集在某个区域。
伪随机检测
在有冲突的情况下，用随机函数计算位移，称为随机检测法。
3.2链接地址方法
为了避免非同义词的冲突，所有的同义词都存储在一个线性链表中。
对于可能导致许多冲突的散列函数，链方法提供了不会找到地址的保证。
4哈希表的搜索
哈希查找依赖于三个因素:哈希函数、处理冲突的方法和填充因子。
填充因子表中记录的哈希表长度。
哈希表的平均搜索长度取决于哈希表的填充因子，而不是直接取决于或。
越大越满，冲突的可能性越大。
4.1哈希表搜索算法的实现
哈希表的结构定义如下:
#定义成功1
#定义不成功0
#define HASHSIZE 12 /将哈希表长度定义为数组的长度/
#定义NULLKEY -32768
typedef int状态；/* Status是函数的类型，其值是函数结果状态码，如OK等。*/
typedef结构
{
int * elem/数据元素存储基址，动态分配数组/
int计数；/当前数据元素的数量/
}哈希表；
int m = 0；/哈希表长度，全局变量/
哈希表初始化:
/初始化哈希表/
状态InitHashTable(HashTable *H)
{
int I；
m = HASHSIZE
h-> count = m；
h-> elem =(int *)malloc(m * sizeof(int))；
for(I = 0；我
h-> elem[I]= null key；
退货OK；
}
作为哈希函数的余数方法:
/哈希函数/
int Hash(int key)
{
返回键% m；/除法和余数法/
}
哈希表插入算法:
/将关键字插入哈希表/
void InsertHash(HashTable *H，int key)
{
int addr = Hash(key)；/查找哈希地址/
while (H->elem[addr]！= NULLKEY) /如果不为空，则冲突/
{
addr =(addr+1)% m；/开放寻址方法的线性检测/
}
h-> elem[addr]= key；/插入关键字，直到有空格为止/
}
在代码中插入关键字时，首先计算哈希地址。如果当前地址不是空关键字，则表示存在冲突。此时我们使用线性检测的开放寻址方法进行重寻址，这里也可以改为链地址法等其他冲突解决方法。
哈希表查找算法:
复制
/查找关键字的哈希表/
Status SearchHash(哈希表H，int key，int *addr)
{
- addr = Hash(key)；/查找哈希地址/
while(H.elem[*addr]！= key) /如果不为空，则冲突/
{ - addr =(* addr+1)% m；/开放寻址方法的线性检测/
If(h . elem[* addr]= = null key | | * addr = = hash(key))/* If循环返回原点*/
返回不成功；/则该关键字不存在/
}
返回成功；
}