数据结构和算法——19. 散列函数设计方法
一、散列(哈希)函数设计方法
1. 折叠法
折叠法设计散列函数的基本步骤:
- 将数据项按照位数分为若干段;
- 将几段数字相加;
- 对散列表大小求余,得到散列值。
例如:对于电话号码62767255,可以两位两位分为4段(62、76、72、55),相加(62 76 72 55=265),散列表包括11个槽,那么就是265=1。所以, h ( 62767255 ) = 1 h(62767255)=1 h(62767255)=1。
有时候折叠法还会包括一个隔数反转的步骤。比如(62、76、72、55)隔数反转为(62、67、72、55),再累加(62 67 72 55=256),对11求余,(256=3),所以 h ′ ( 62767255 ) = 3 h'(62767255)=3 h′(62767255)=3。
虽然隔数反转从理论上看来毫无必要,但这个步骤确实为折叠法得到散列函数提供了一种微调手段。当我们发现折叠法得到的结果不太好时,就可以加入隔数反转,以便更好符合散列特性。
2. 平方取中法
平方取中法的基本步骤:
- 将数据项做平方运算;
- 取平方数的中间两位;
- 对散列表的大小求余,得到散列值。
例如:对44进行散列,首先 4 4 2 = 1936 44^2=1936 442=1936,然后取中间的93,对散列表大小11求余 93 % 11 = 5 93\=5 93%11=5,散列值为5。
折叠法和平方取中法都是完美散列函数,分散度都很好,但平方取中法计算量稍大。
二、散列函数设计:非数项
对非数字的数据项进行散列时,把字符串中的每个字符看作ASCII码即可。
如字符串“cat”,ord('c')
等于99,ord('a')
等于96,ord('t')
等于116。再将这些整数累加,对散列表大小求余。
当然,这样的散列函数对所有的变位词都返回相同的散列值,为了防止这一点,可以将字符串中字符所在的位置(“cat”中,“c”是第一位,“t”是第三位)作为权重因子,乘以ord值。即 99 × 1 97 × 2 116 × 3 = 641 99\times1 97\times2 116\times3=641 99×1 97×2 116×3=641,然后再去求余。
总结
我们还可以设计出更多的散列函数方法,但要坚持的一个基本出发点是,散列函数不能成为存储过程和查找过程的计算负担。否则,在散列身上花费太多计算资源,可能还不如简单地进行顺序查找或者二分查找,失去了散列本身的意义。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhigjcja
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信提示登录环境异常是什么意思原因
PHP中文网 04-09 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
微信人名旁边有个图标有什么用
PHP中文网 03-11