本文概述
- 良好哈希函数的特征
- 一些流行的哈希函数是
良好哈希函数的特征
- 哈希值完全由要哈希的数据确定。
- 散列函数使用所有输入数据。
- 哈希函数“均匀地”将数据分布在整个可能的哈希值集中。
- 哈希函数为相似的字符串生成复杂的哈希值。
选择一个小于m中的n个键的数字的m(数字m通常选择为质数或没有小除数的数字, 因为这通常是最少的碰撞次数)。
哈希函数是:
文章图片
例如:如果哈希表的大小为m = 12, 并且密钥为k = 100, 则h(k)=4。由于它仅需要单个除法运算, 因此按除法进行哈希运算非常快。
2.乘法方法:
用于创建哈希函数的乘法方法分两个步骤进行。首先, 我们将密钥k乘以0 < A < 1范围内的常数A, 并提取kA的小数部分。然后, 我们将该值增加m并取下限。
哈希函数是:
文章图片
其中“ k A mod 1”表示k A的分数部分, 即k A-?kA?。
3.中方法:
密钥k平方。然后函数H定义为
H (k) = L
其中L是通过删除k2两端的数字获得的。我们强调必须为所有键使用相同的k2位置。
4.折叠方式:
密钥k分为多个部分k1, k2 … .. kn, 其中每个部分(除了最后一个部分)都具有与所需地址相同的位数。
然后将各部分加在一起, 而忽略最后一个进位。
H (k) = k1+ k2+.....+kn
示例:公司有68名员工, 并且每个员工都分配有唯一的四位数员工编号。假设L由2位地址组成:00、01和02 … . 99。我们将上述哈希函数应用于以下每个员工编号:
3205, 7148, 2345
【常见的散列函数实现方法】(a)除法:选择一个接近99的素数m, 例如m = 97, 然后
H (3205) = 4, H (7148) = 67, H (2345) = 17.
将3205除以17得到的余数为4, 将7148除以97得到的余数为67, 将2345除以97得到的余数为17。
(b)中方法:
k = 320571482345k2= 10272025510939045499025h (k) = 729399
请注意, 从哈希算起, 选择了从右开始计数的第四和第五位。
(c)折叠方法:将密钥k分为2部分, 并相加得出以下哈希地址:
H (3205) = 32 + 50 = 82H (7148) = 71 + 84 = 55H (2345) = 23 + 45 = 68
推荐阅读
- 如何在VMware ESXi上启用SSH(详细操作指南)
- 如何在Hive中创建外部表(如何使用外部表?)
- Fail2Ban安装和设置指南(Ubuntu、CentOS、Fedora 和 Debian)
- 如何在Bash中检查文件或目录是否存在(代码示例)
- 22个用于编程和编码的最佳Linux文本编辑器合集
- 如何在Ubuntu 18.04上安装TensorFlow GPU(分步指南)
- WIN10专业版激活工具图文图文详细教程
- win10变回win7图文图文详细教程
- 最新通用版win10激活密钥分享自制步骤