9

これは、Knuth乗法ハッシュの正しい実装ですか。

int hash(int v)
{
    v *= 2654435761;
    return v >> 32;
}

乗算のオーバーフローはアルゴリズムに影響しますか？

このメソッドのパフォーマンスを向上させる方法は？

4

4 に答える 4

22

{0, 1, 2, ..., 2^p - 1}Knuth乗法ハッシュは、整数kからのハッシュ値を計算するために使用されます。

それpが0から32の間にあるとすると、アルゴリズムは次のようになります。

  • 2 ^ 32（-1 + sqrt（5））/2に最も近い整数としてalphaを計算します。alpha=2 654435769を取得します。

  • k * alphaを計算し、2^32を法として結果を減らします。

    k * alpha = n0 * 2 ^ 32 + n1 with 0 <= n1 <2 ^ 32

  • n1の最上位pビットを保持します。

    n1 = m1 * 2 ^（32-p）+ m2、0 <= m2 <2 ^（32-p）

したがって、C++でのKnuth乗法アルゴリズムの正しい実装は次のとおりです。

std::uint32_t knuth(int x, int p) {
    assert(p >= 0 && p <= 32);

    const std::uint32_t knuth = 2654435769;
    const std::uint32_t y = x;
    return (y * knuth) >> (32 - p);
}

結果を（32 --p）だけシフトするのを忘れることは、大きな間違いです。ハッシュのすべての優れたプロパティを失うことになります。偶数のシーケンスを偶数のシーケンスに変換しますが、すべての奇数のスロットが占有されないままになるため、非常に悪い結果になります。それは、良いワインを取り、それをコークスと混ぜるようなものです。ちなみに、ウェブはクヌースを誤って引用し、上位ビットを取得せずに2 654435761による乗算を使用する人々でいっぱいです。私はクヌースを開いたばかりですが、彼はそのようなことを言ったことはありません。「賢い」と判断した人が、2 654435769に近い素数を取ることにしたようです。

ほとんどのハッシュテーブルの実装では、この種の署名は許可されているだけなので、インターフェイスでは許可されていないことに注意してください。

uint32_t hash(int x);

hash(x)xのハッシュ値を計算するためにモジュロ2^pを減らします。これらのハッシュテーブルは、Knuth乗法ハッシュを受け入れることができません。これは、非常に多くの人々がより高いpビットを取ることを忘れてアルゴリズムを完全に台無しにした理由かもしれません。std::unordered_mapしたがって、またはでKnuth乗法ハッシュを使用することはできませんstd::unordered_set。しかし、これらのハッシュテーブルはサイズとして素数を使用していると思うので、この場合、クヌースの乗法ハッシュは役に立ちません。これらのテーブルには、を使用hash(x) = xするのが適しています。

出典：「アルゴリズム入門、第3版」、Cormen et al。、13.3.2 p：263

出典：「TheArt of Computer Programming、Volume 3、Sorting and Searching」、DE Knuth、6.4 p：516

于 2017-01-08T21:17:10.970 に答える
15

わかりました。TAOCPボリューム3（第2版）、セクション6.4、ページ516で調べました。

コメントで述べたように、この実装は正しくありませんが、とにかく正しい結果が得られる可能性があります。

正しい方法（TAOCPの関連する章を読んで、これを確認してください）は次のようなものです:(重要：はい、結果を右にシフトして、ビット単位のANDを使用しないでください。ただし、そうではありません。この関数の責任-範囲の縮小は、ハッシュ自体の一部ではありません）

uint32_t hash(uint32_t v)
{
    return v * UINT32_C(2654435761);
    // do not comment about the lack of right shift. I'm not ignoring it. read on.
}

uint32_t's（' sではなく）に注意してくださいint-ワードサイズとして32を選択した場合に行われるはずのように、乗算が2^32を法としてオーバーフローすることを確認します。kまた、基本的なハッシュ関数に範囲縮小の責任を負わせる理由がなく、完全な結果を取得する方が実際にはより便利であるため、ここでは右シフトもありません。定数2654435761は質問からのものであり、実際に推奨される定数は2654435769ですが、これは小さな違いであり、私が知る限り、ハッシュの品質には影響しません。

他の有効な実装は、必要なハッシュのビット数に応じて、結果をある程度右にシフトします（ただし、完全なワードサイズではありませんが、それは意味がなく、C ++はそれを好みません）。または、他の定数（特定の条件に従う）または他のワードサイズを使用する場合があります。何かを法としてハッシュを減らすことは有効な実装ではありませんが、よくある間違いです。おそらく、ハッシュの範囲を減らすためのデファクトスタンダードの方法です。乗法ハッシュの最下位ビットは最悪の品質のビットです（入力に依存するビットが少ない）。実際にもっと多くのビットが必要な場合にのみ使用します。ハッシュをモジュロで2の累乗にすると、最悪のビットのみが返されます。ビット。実際、これはほとんどの入力ビットを破棄することと同じです。2の累乗以外のモジュロを減らすと、上位ビットが混在するため、それほど悪くはありませんが、乗法ハッシュが定義された方法ではありません。

明確にするために、はい、右シフトがありますが、それはハッシュではなく範囲の縮小であり、内部サイズに依存するため、ハッシュテーブルの責任のみになります。

タイプは符号なしである必要があります。そうでない場合、オーバーフローは指定されておらず（したがって、2の補数以外のアーキテクチャだけでなく、過度に巧妙なコンパイラでも間違っている可能性があります）、オプションの右シフトは符号付きシフトになります（間違っています）。

冒頭で述べたページには、次の式があります。

knuth式

ここでは、A = 2654435761（または2654435769）、w = 2 32、M = 232です。AK / wを計算すると、Q32.32形式の固定小数点結果が得られます。mod1ステップは32小数ビットのみを使用します。しかし、これは、モジュラー乗算を実行して、結果が小数ビットであると言うのと同じことです。もちろん、Mを掛けると、Mの選択方法により、すべての小数ビットが整数ビットになります。したがって、単純に古いモジュラー乗算になります。Mが2の低い累乗である場合、前述のように、結果はちょうど右シフトします。

于 2012-08-08T20:19:50.603 に答える
2

遅れるかもしれませんが、ここにクヌースのメソッドのJava実装があります：

サイズNのハッシュテーブルの場合： 

public long hash(int key) {
    long l = 2654435769L;
    return (key * l >> 32) % N ;
}
于 2019-01-12T13:00:02.220 に答える
0

入力引数がポインタの場合、これを使用します

#include <inttypes.h>

uint32_t knuth_mul_hash(void* k) {
  ptrdiff_t v = (ptrdiff_t)k * UINT32_C(2654435761);
  v >>= ((sizeof(ptrdiff_t) - sizeof(uint32_t)) * 8); // Right-shift v by the size difference between a pointer and a 32-bit integer (0 for x86, 32 for x64)
  return (uint32_t)(v & UINT32_MAX);
}

私は通常、これをハッシュマップの実装、辞書、セットなどのデフォルトのフォールバックハッシュ関数として使用します...

于 2016-05-30T12:06:38.093 に答える