怎么样的才算是好的哈希函数？
- 计算简单，哈希函数的计算时间（指的是产生地址的时间），不应该超过其他查找技术与关键字比较的时间。
- 地址分布均匀，尽量让哈希地址均匀分布在存储空间中，这样可以使空间有效的利用。
1.直接定址法
哈希地址：f(key) = a*key+b (a,b为常数)
这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道 key 的分布情况，适合查找表较小并且连续的情况。
2、数字分析法
比如我们的11位手机号码“136xxxx5889”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意 通，136是移动神州行等等。中间四位表示归属地。最后四位才是用户号。
若我们现在要存储某家公司员工登记表，如果用手机号码作为 key，那么极有可能前7位都是相同的，所以我们选择最后 四位作为 f(key) 就是不错的选择。
3、平方取中法
故名思义，比如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。
4、折叠法
折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按 哈希表的表长，取后几位作为 f(key) 。
比如：我们的 key 是 9876543210，哈希表的表长为3位，我们将 key 分为4组，987|654|321|0 ，然后将它们叠加求和 987+654+321+0=1962，再取后3位即得到 f(key) = 962 。
5、除留余数法
哈希地址：f(key) = key % p (p<=m) m为哈希表表长。
这种方法是最常用的哈希函数构造方法。
事实上，如果p选得不好，就很容易出现同义冲突的情况：
例子
如上图所示，选择p=11，就会出现key=12、144的冲突。
若哈希表表长为m，通常p为小于或者等于表长的最小质数或不包含小于20质因子的合数。
6、随机数法
哈希地址：f(key) = random(key)
这里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。
网友评论