哈希表】哈希表的p怎么取得

2022-04-20 18:51发布

3条回答

这个主要是看你数组的长度是多少, 比如之前写过的一个程序有个数组存的是各个客户端的ip地址:
string clientIp[4]={"XXX", "xxx", "xxx", "xxx"};
这个时候如果想把hash值对应到上面四个地址的话,就应该对4取余,这个时候p就应该为4

摩羯摩羯
3楼 · 2022-04-29 17:08

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

猫的想法不敢猜
4楼 · 2022-05-07 11:43

直接定址法

  直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址,即:H(k)=k  或 H(k)=a×k+b ; (其中a,b为常数)

  例1,有一个人口统计表,记录了从1岁到100岁的人口数目,其中年龄作为关键字,哈希函数取关键字本身,如图(1):

地址

A1

A2

……

A99

A100

年龄

1

2

……

99

100

人数

980

800

……

495

107

可以看到,当需要查找某一年龄的人数时,直接查找相应的项即可。如查找99岁的老人数,则直接读出第99项即可。这种哈希函数简单,并且对于不同的关键字不会产生冲突,但可以看出这是一种较为特殊的哈希函数,实际生活中,关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费,因此这种方法适应性并不强。[2]↑

除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址,即设定哈希函数为  Hash(key)=key mod p (p≤m),其中,除数p称作模。

除留余数法不仅可以对关键字直接取模,也可以在折叠、平方取中等运算后取模。对于除留余数法求哈希地址,关键在于模p的选择。使得数据元素集合中每一个关键字通过该哈希函数映射到内存单元的任意地址上的概率相等,从而尽可能减少发生哈希冲突的可能性。

理论研究表明,除留余数法的模p取不大于表长且最接近表长m素数时效果最好,且p最好取1.1n~1.7n之间的一个素数(n为存在的数据元素个数)。例如:当n=7时,p最好取11、13等素数。 又例图(5):

表长m

8

16

32

64

128

256

512

1000

模p

7

13

31

61

127

251

503

997

由于除留余数法的地址计算方法简单,而且在许多情况下效果较好。[2]↑

例9,公司有236个员工,而员工编号介于1000到9999,除留余数法就是员工编号除以数据个数236后,去余数即为数据的位置。编号5428员工的数据(编号5428除以236取余数得0)放数据中的第一笔,编号3512员工数据(编号3512除以236取余数得8)放数据中的第九笔…依次类推。


相关问题推荐

  • 回答 5

     哈希表的大小 · 关键字的分布情况 · 记录的查找频率 1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。...

  • 回答 6

    哈希表的大小取决于一组质数,原因是在hash函数中,你要用这些质数来做模运算(%)。而分析发现,如果不是用质数来做模运算的话,很多生活中的数据分布,会集中在某些点上。所以这里最后采用了质数做模的除数。 因为用质数做了模的除数,自然存储空间的大小也用质数了...

  • 回答 2

    是啊,哈希函数的设计至关重要,好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间

  • 回答 3

     解码查表优化算法,seo优化

  • 回答 5

    就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。(或者:把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度...

  • 回答 2

    一般情况确实不应该用地址来作为删除的参数,但如果你已经事先搜索到了一个元素但之后不用了不就可以

  • 回答 2

    哈希表是散列的一种。散列是一种用以常数平均时间执行插入、删除和查找的技术。 为了得到更快的执行速度,当查询某个元素多于遍历时可使用。但是数组无法确定准确的位置

  • 回答 3

    跟加载因子设置的大小有关

  • 回答 2

    虽然哈希表和数组在 lua 里都表示为一个 table,但是其底层实现还是有所区别的,理想情况下哈希表的内存占用是数组的两倍,主要区别在于哈希节点比数组节点多了一个 TKey 的内存占用。在数据量大的情况下考虑使用数组可以有效减少内存...

  • 回答 5

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数...

  • 回答 4

    哈希表可以理解为一维数组。因为只是单一的坐标。当然如果考虑到哈希碰撞,理解为二维数组也无不可。至于下标1跟10001,这个问题很好。你观察到了,这样的数组会有大量的空洞。这是一种常见的现象。一维的这种数组叫做稀疏数组,二维的这种数组叫做稀疏矩阵。...

  • 回答 3

    在数据结构哈希表中不成功平均查找长度和成功平均查找长度之间并没有什么直接的关系。他们都是对于特定的哈希表和特定的查找序列,才有意义的。

  • 回答 3

    查找不成功的次数表如下表所示 Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5  所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考...

  • 回答 9

    A--->function()---> B源数据A经过function()的运算得到B.这里的function()就是哈希函数,它是某一种hash算法的实现。得到的数据B就是hashCode,它是源数据A的哈希体现。如果我们将A->B这样的的关系保存下来,存储这个对应关系的我们称为哈希表。补充:还是正...

  • 回答 3

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。哈希表的做法其实很简单,就是...

没有解决我的问题,去提问