哈希函数的三个特性
哈希函数的三个特性是任何对象作为哈希函数的输入都可以得到一个相应的哈希值；两个相同的对象作为哈希函数的输入，它们总会得到一样的哈希值；两个不同的对象作为哈希函数的输入，它们不一定会得到不同的哈希值。
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。哈希表中元素是由哈希函数确定的。
将数据元素的关键字K作为自变量，通过一定的函数关系，计算出的值，即为该元素的存储地址。在哈希表中，不同的关键字值对应到同一个存储位置的现象。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。
哈希函数冲突的处理及解决方法：
冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）=H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。
解决冲突的方法：
1、链接法（拉链法）。将具有同一散列地址的记录存储在一条线性链表中。例，除留余数法中，设关键字为（18,14,01,68,27,55,79），除数为13。散列地址为（5,1,1,3,1,3,1）。
2、开放定址法。如果h(k）已经被占用，按如下序列探查：(h(k)+p⑴）%TSize,(h(k)+p⑵）%TSize，…，h(k)+p(i))%TSize。
其中，h(k)为哈希函数，TSize为哈希表长，p(i）为探查函数。在h(k)+p(i-1)）%TSize的基础上，若发现冲突，则使用增量p(i)进行新的探测，直至无冲突出现为止。其中，根据探查函数p(i）的不同，开放定址法又分为线性探查法（p(i)=i:1,2,3，…）。
ZESTRON
2024-09-04 广告
