[部分内容由gpt自动生成]
第一节 哈希（散列）查找
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f、使每个关键字key对应一个存储位置
address = f(key)
查找时,根据这个确定的对应关系找给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。
这里我们把这种对应关系f称为散列函数,又称为哈希（Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。
哈希查找，也被称为散列查找，是一种非常高效的查找方式，它利用哈希表（又被称为散列表）来查找目标元素。这种方法在理想情况下，即无冲突的情况下，时间复杂度可以达到O(1)。这是因为哈希查找算法不需要对关键字进行比较，而是通过哈希函数直接得到其地址，从而大大提高了查找效率。
然而，实际应用中，哈希表可能存在哈希冲突的问题，即不同的输入可能会被映射到同一个输出值。对于这种情况，有多种解决方法，如线性探测法和链地址法等。
第二节 哈希函数的构造方法
3.1 把任意类型的key转为整数
现有的技术中，可以通过MD5或者SHA之类的算法，把任意类型的key转为多字节的整数。
下面是一个简单例子。我们把任意类型的key看做是一个字节数组：[b0,b1,b2,b3,…]，再把各个字节进行某种叠加，从而计算出一个整数。
/* 把n个字节的key转为Int32 */ int hash(char *key, int n) { int i, h=0; for(i=0; i<n; i , key ) { h = h<<4 h *key; /* h = h*17 *key; */ } return h; } |
3.2 根据哈希表的大小，映射到有效地址空间上
常用的办法是除留余数法。
addr = hash(key, n) mod p
其中，p为小于哈希表大小的一个最大素数。如果p与哈希表大小差值较大，也可以选一个接近哈希表大小、质因子较少的数。最坏的情况下，也别选偶数。
第三节 哈希冲突的处理办法
冲突是指关键字不一样，但哈希值相同：
key1 != key2
hash(key1) == hash(key2)
无论如何精心设计哈希函数，冲突几乎是无可避免的。key1和key2称为同义词。
冲突的处理可以采用如下技术：开放地址法、链地址法、再哈希法、公共溢出区等。
3.1 开放定址法
理论上，哈希表中的某个地址，只存放映射到该地址值的关键字。但是为了解决关键字冲突，开放定址法允许该地址对所有关键字开放，即，可以存储任意关键字。
当发现关键字对应哈希地址上已经存有元素后，可以采用给若干种办法来确定下一个存储地址。
Hi(key)=(H(key) di) MOD m，i=1, 2, …, k(k<=m-1)
其中：
H(key)：哈希函数；
m：散列表长度；
di：第i次探测时的增量序列；
Hi(key) ：经第i次探测后得到的散列地址。
探测序列的方法可以分为：
（1）线性探测法
当发生冲突时，从初次发生冲突的位置依次向后探测其他的地址。
增量序列为：di=1, 2, 3, …, m-1
【例】设散列表长为7，记录关键字组为：15, 14, 28, 26, 56, 23，散列函数：H(key)=key MOD 7，冲突处理采用线性探测法。
解：
H(15)=15 MOD 7=1
H(14)=14 MOD 7=0
H(28)=28 MOD 7=0
H(26)=26 MOD 7=5
H(56)=56 MOD 7=0
H(23)=23 MOD 7=2
散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
关键字 | 14 | 15 | 28 | 56 | 23 | 26 | |
冲突次数 | 0 | 0 | 2 | 3 | 2 | 0 |
平均查找长度为：(6 2 3 2)/7 = 13/7
（2）二次探测法
（3）伪随机探测法
3.2 链地址法
3.3 再哈希法
3.4 公共溢出区
