当前位置: 首页 > 面试题库 >

使用乘法的哈希函数有什么缺点

容磊
2023-03-14
问题内容

几乎每本教科书和CS课程都引用了两种实现哈希函数的基本方法:

  1. 除法 ,我们只需要简单地k mod m选择m作为素数就不太接近2的幂。
  2. 乘法方法 是将k与0到1之间的某些非理性选择数(Knuth建议使用基于黄金比率的数)相乘,取乘积的小数部分,并从中使用所需数目的最高有效位。

大多数教科书和课程都列举了方法1的几个缺点,包括方法昂贵且取决于m的事实。但是,我从未见过任何教科书或课程提到方法2的单一缺点。

这使得方法2更可取。另外,方法2在现代计算机上可以非常有效地消除浮点运算。因此,看起来方法2是不言而喻的胜利者,没有人应该谈论方法1。但是显然不是这样。实际上,我从未见过方法2在任何实际的实现中得到使用。因此它确实有一些缺点。

问题是,它们是什么?为什么方法1尽管有其缺点,却仍被更频繁地使用?


问题答案:

除法与需要主要表大小的哈希表算法结合使用-
例如,当您无论如何都需要通过表大小来划分键或哈希(即哈希)以获取索引时,使用双哈希或QHash进行开放式寻址。

当表的大小为2的幂时,乘法方法是合适的,然后可以通过按位AND运算来从哈希中获取索引,因此,通过键进行乘法哈希计算,使用键计算表html" target="_blank">索引的整个路径非常快。您可以通过在Github上搜索魔术常数2654435769来探索一些实际的实现。

最近有使用MurmurHash3雪崩过程而不是乘法方法的趋势:

int hash = key;
hash ^= (hash >> 16);
hash *= 0x85ebca6b;
hash ^= (hash >> 13);
hash *= 0xc2b2ae35;
hash ^= (hash >> 16);
// see this code and the version for 64 bits here:
// https://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp

因为它速度稍慢,但被认为对不良的密钥分发更可靠。这就是为什么您可能会错误(或正确?)的印象,即很少使用不公平的乘法方法。



 类似资料:
  • 从原理到应用分析什么是哈希? 一、什么是哈希? 哈希(hash):将任意长度的输入(关键字),通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法,而原始数据映射后的二进制串就是哈希值,通常哈希值代表了关键字的存储位置。 但是为什么要这样做呢?或者说,哈希是怎样来的呢? 哈希的出现解决了两个问题:存储和搜索。 1. 存储(数据结构):如果在容器中保存对象及其关联的键,并且不用键

  • 问题内容: Spark MLLIb具有HashingTF()函数,该函数根据每个术语的哈希值计算文档术语频率。 1)它使用什么函数进行哈希处理? 2)如何从Python获得相同的哈希值? 3)如果我想为给定的单个输入计算散列输出,而不计算术语“频率”,我该怎么做? 问题答案: 如果您有疑问,通常检查来源。给定项的存储区确定如下: 如您所见,这只是存储桶的一个普通的旧模块数。 最终哈希只是每个存储区

  • 问题内容: 我需要一个可逆的哈希函数(显然,输入的大小将比输出小得多),该函数将输入以随机的方式映射到输出。基本上,我想要一种将“ 123”之类的数字转换为“ 9874362483910978”之类的较大数字的方法,但不是要保留比较的方法,因此,如果x1> x2,f(x1 )> f(x2)(但也不能始终为假)。 这种情况的用例是,我需要找到一种方法将小数字转换成看起来更大的随机数字。它们实际上并不

  • 在查看了用于生成 Java MD5 和 SHA* 哈希的多个在线参考后,我注意到纯文本(文件字符串)之前经历了某些准备 PS:我想答案与Java和Digest对象如何处理它们的业务有关,我问这个问题的动机是为了理解这种行为,并可能获得一些深入解释这一点的文档/文献的参考资料。 丹科!

  • 我正在尝试编写一个C程序,使用哈希表来存储不同的单词,我需要一些帮助。 首先,我创建一个哈希表,其大小为最接近我必须存储的单词数的素数,然后我使用一个哈希函数为每个单词找到一个地址。我从最简单的函数开始,把字母加在一起,结果有88%的碰撞。然后我开始实验这个函数,发现无论我把它改成什么,碰撞都不会低于35%。现在我在用 这只是我想出来的一个随机函数,但它给了我最好的结果--大约35%的碰撞。 在过

  • 也许我没有看到什么或者我忘记了在计算运行时考虑的事情,所以请告诉我。