• 散列函数设计:除留余数法

    合理选择除数
    服务器君一共花费 57.570 ms 进行了 5 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    除留余数法介绍

    除留余数法此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为:

    f( key ) = key mod p ( p ≤ m )

    mod是取模(求余数)的意思。事实上,这方法不仅可以对关键字直接取模,也可在折叠、平方取中后再取模。

    一个例子

    • 很显然,本方法的关键就在于选择合适的p, p如果选得不好,就可能会容易产生同义词。下面我们来举个例子看看:

    有一个关键字,它有12个记录,现在我们要针对它设计一个散列表。如果采用除留余数法,那么可以先尝试将散列函数设计为f(key) = key mod 12的方法。比如29 mod 12 = 5,所以它存储在下标为5的位置。

    不过这也是存在冲突的可能的,因为12 = 2×6 = 3×4。如果关键字中有像18(3×6)、30(5×6)、42(7×6)等数字,它们的余数都为6,这就和78所对应的下标位置冲突了。

    • 甚至极端一些,对于下图的关键字,如果我们让p为12的话,就可能出现下面的情况,所有的关键字都得到了0这个地址数,这未免也太糟糕了点。

    但是我们如果不选用p=12来做除留余数法,而选用p=ll,则结果如下:

    这个时候就只有12和144有冲突,相对来说,就要好很多了。

    如何合理选取p值

    使用除留余数法的一个经验是,若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。

    • 这句话怎么理解呢?要不这样吧,我再举个例子:某散列表的长度为100,散列函数H(k)=k%P,则P通常情况下最好选择哪个呢?A、91 B、93 C、97 D、99
    • 实践证明,当P取小于哈希表长的最大质数时,产生的哈希函数较好。我选97,因为它是离长度值最近的最大质数
更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [软件工程与项目管理] 呈现器的布局与绘制 11 个条目
  2. [软件工程与项目管理] 浏览器的HTML解析器 8 个条目
  3. [移动开发] ListView 使用相关问题集 1 个条目
  4. [软件工程与项目管理] 呈现树的构建 13 个条目
  5. [数据结构] 图的定义 1 个条目
  6. [数据库技术] 数据库范式篇 5 个条目
  7. [移动开发] 从代码角度去认识 Activity 4 个条目
  8. [软件工程与项目管理] 开始了解Git 5 个条目
  9. [Python程序设计] 从PHP到Python 3 个条目
  10. [移动开发] Activity 初步知识 2 个条目
  11. [PHP程序设计] Nginx基本操作释疑 7 个条目
  12. [Python程序设计] Django架构流程分析 7 个条目
窗口 -- [八点]