download：受用毕生的产品思维无密分享内置文档

哈希表查找哈希算法的定义与实现
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循环返回原点/
    返回不胜利；/则该关键字不存在/
    }
    返回胜利；
    }