哈希函数构造 哈希冲突解决 一致性hash

简介哈希函数的构造方法 https://blog.csdn.net/u011037053/article/details/82080023 (1)直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即H(key)=key 或 H(key)=a*key+b   (a,b为常数)。 (2)数字分析法 若关键字是以r为基的数(如:以10为基的十进制数),并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。 (3

哈希函数的构造方法 https://blog.csdn.net/u011037053/article/details/82080023


(1)直接定址法
取关键字或关键字的某个线性函数值为哈希地址。即H(key)=key 或 H(key)=a*key+b   (a,b为常数)。

(2)数字分析法
若关键字是以r为基的数(如:以10为基的十进制数),并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
(3)平方取中法
取关键字平方后的中间几位为哈希地址。(较常用的一种)
(4)折叠法
将关键字分割成位数相同的几部分(最后一部分的位数可不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。适用于关键字位数比较多,且关键字中每一位上数字分布大致均匀时。
(5)除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址(p为素数)
H(key)=key  MOD  p,p<=m   (最简单,最常用)p的选取很重要
一般情况,p可以选取为质数或者不包含小于20的质因数的合数(合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数)。
(6)随机数法
选择一个随机函数,取关键字的随机函数值为它的哈希地址。即H(key)=random(key),其中random为随机函数。适用于关键字长度不等时。
总结:实际工作中根据情况不同选用的哈希函数不同,通常,考虑因素如下:
(1)计算哈希函数所需时间(包括硬件指令的因素)
(2)关键字的长度
(3)哈希表的大小
(4)关键字的分布情况
(5)记录的查找频率


新加评论 评论标题:

文章评论