数据结构哈希算法

发布网友发布时间：2022-04-19 20:22

共1个回答

热心网友时间：2023-01-20 16:42

1，直接定址法：
函数公式：f(key)=a*key+b (a,b为常数)
这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。
2，数字分析法：
比如我们的11位手机号码“136XXXX7887”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意通，136是移动神州行，153是电信等。中间四们是HLR识别号，表示用户归属地。最后四们才是真正的用户号。
若我们现在要存储某家公司员工登记表，如果用手机号码作为关键字，那么极有可能前7位都是相同的，所以我们选择后面的四们作为哈希地址就是不错的选择。
3，平方取中法：
故名思义，比如关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为哈希地址。
4，折叠法：
折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
比如我们的关键字是9876543210，哈希表表长三位，我们将它分为四组，987|654|321|0 ，然后将它们叠加求和987+654+321+0=1962，再求后3位即得到哈希地址为962，哈哈，是不是很有意思。
5，除留余数法：
函数公式：f(key)=key mod p (p<=m)m为哈希表表长。
这种方法是最常用的哈希函数构造方法。
6，随机数法：
函数公式：f(key)= random(key)。
这里random是随机函数，当关键字的长度不等是，采用这种方法比较合适。
两种哈希函数冲突解决方法：
我们设计得最好的哈希函数也不可能完全避免冲突，当我们在使用哈希函数后发现两个关键字key1!=key2，但是却有f(key1)=f(key2)，即发生冲突。

首页

文章

数据结构哈希算法