什么是哈希函数的使用倍增法的缺点 [英] What are the disadvantages of hashing function using multiplication method

问题描述

有被引用pretty的两种基本方法实现的哈希函数每得多课本和CS课程：

There are two basic methods for implementing a hash function that are cited in pretty much every text book and CS courses:

1. 司法在这里我们简单地做 K模m 基本采摘米首相不要太接近2的力量。
2. 倍增法在这里我们乘K的一些精心挑选的无理数（克努特建议使用基于黄金比例数）0〜1，取本品的小数部分，并使用所需数量最显著位来自它。

1. Division method where we simply do k mod m essentially picking m as prime not too close to power of 2.
2. Multiplication method where we multiply k with some well-chosen irrational number (Knuth suggests using number based on Golden ratio) between 0 to 1, take the fractional part of the product and use desired number of most significant bits from it.

大多数教科书和课程举出几个缺点的方法1，包括事实，即它是昂贵的，事情取决于微米。但是我从来没有看过任何一本教科书或课程提唯一的缺点的方法2。

Most text books and courses cite several disadvantages for method 1 including the fact that it's expensive and things depends on m. However I've never yet seen any textbook or courses mention single disadvantage for method 2.

这使得方法2更可取。加方法2可以制成非常有效的对现代计算机消除浮点算术都在一起。因此，它看起来像那个方法2是倒手赢家，没有任何机构应该谈论的方法1，但是，这显然不是这样。事实上，我从来没有见过方法2在任何实际的实现中得到。所以它也有一些缺点。

This makes method 2 more desirable. Plus the method 2 can be made very efficient on modern computers eliminating floating point arithmetic all together. So it would look like that method 2 is hands down winner and no body should be talking about method 1. But that's obviously not the case. In fact, I've never seen method 2 getting used in any practical implementations. So it does have some disadvantages.

问题是它们是什么，为什么方法1被应用较多，尽管它的缺点是什么？

Question is what are they and why method 1 gets used more often despite of its disadvantages?

推荐答案

划分方法可与需要黄金表大小的哈希表算法相结合 - 例如，开放式解决双散列或的 QHash ，当你反正需要划分的关键，还是它的哈希，通过表的大小来获取索引。

Division method is used in conjunction with hash table algorithms which require prime table size - for example, open addressing with double hashing or QHash, when you anyway need to divide the key, or it's hash, by table size to get the index.

乘法方法适于当表大小是二的幂，然后让从哈希索引可以实现为按位与运算，由密钥计算表索引因此整个路径，以乘法散列，则很快。您可以探索一些实际实现由寻找魔法不断2654435769 Github上。

Multiplication method is suitable when the table size is a power of two, then getting the index from the hash could be implemented as bitwise AND operation, therefore the whole path of computing the table index by the key, with multiplication hashing, is very fast. You can explore some actual implementations by searching for magic constant 2654435769 on Github.

有使用，而不是倍增法MurmurHash3雪崩过程的一个新趋势：

There is a recent trend of using MurmurHash3 avalanche procedure instead of multiplication method:

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

由于这只是一个有点慢，但更加稳健坏密钥分发。这就是为什么你可能会得到错误的（或右？）IM pression乘法方法用于不公平的很少。

Because it is just a bit slower, but considered more robust to bad key distribution. That is why you might get wrong (or right?) impression that multiplication method is used unfairly rarely.

这篇关于什么是哈希函数的使用倍增法的缺点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！