17

一意のハッシュを生成したい（GetHashCode（）をオーバーライドした）オブジェクトがありますが、オーバーフローや予測できない何かを避けたいです。

コードは、文字列の小さなコレクションのハッシュコードを組み合わせた結果である必要があります。

ハッシュコードはキャッシュキーの生成の一部になるため、理想的には一意である必要がありますが、ハッシュされる可能性のある値の数が少ないため、ここでは確率が有利だと思います。

このようなもので十分であり、これを行うためのより良い方法はありますか？

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

編集：これまでの回答をありがとう。@Jon Skeet：いいえ、順序は重要ではありません

これはほとんど別の質問だと思いますが、結果を使用してキャッシュキー（文字列）を生成しているので、MD5のような暗号化ハッシュ関数を使用するか、このintの文字列表現を使用するのが理にかなっていますか？

4

4 に答える 4

24

ハッシュは一意であるという意味ではなく、ほとんどの状況で適切に分散されるように意図されています。それらは一貫性を保つことを目的としています。オーバーフローは問題にならないことに注意してください。

単に追加することは一般的に良い考えではなく、分割することは確かにそうではありません。私が通常使用するアプローチは次のとおりです。

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

それ以外の場合はチェックされたコンテキストにいる場合は、意図的にチェックを外したい場合があります。

これは、順序が重要であること、つまり{"a"、"b"}が{"b"、"a"}とは異なることを前提としていることに注意してください。そうでない場合はお知らせください。

于 2009-07-03T12:46:05.057 に答える
24

Marc と Jon が指摘したファンダメンタルズは悪くありませんが、結果の分布の均一性という点では最適とはほど遠いものです。悲しいことに、Knuth から非常に多くの人々によってコピーされた「素数による乗算」アプローチは、多くの場合、最良の選択ではありません。多くの場合、より安価に関数を計算することでより良い分散を実現できます (ただし、これは最新のハードウェアでは非常にわずかです)。実際、ハッシュの多くの側面に素数を投入することは万能薬ではありません。

このデータがかなりのサイズのハッシュ テーブルに使用される場合は、 Bret Mulvey の優れた研究と、C# で簡単に実行できるさまざまな最新の (そしてそれほど最新ではない) ハッシュ手法の説明を読むことをお勧めします。

さまざまなハッシュ関数の文字列の動作は、文字列が短い (大まかに言えば、ビットがオーバーフローし始める前にハッシュされる文字数) か長いかに大きく偏っていることに注意してください。

Jenkins One at a time ハッシュは、実装が最もシンプルで簡単なものの 1 つであり、最高のものの 1 つでもあります。

private static unsafe void Hash(byte* d, int len, ref uint h)
{
    for (int i = 0; i < len; i++)
    {
        h += d[i];
        h += (h << 10);
        h ^= (h >> 6);
    }
}

public unsafe static void Hash(ref uint h, string s)
{
    fixed (char* c = s)            
    {
        byte* b = (byte*)(void*)c;
        Hash(b, s.Length * 2, ref h);
    }
}

public unsafe static int Avalanche(uint h)
{
    h += (h<< 3);   
    h ^= (h>> 11);  
    h += (h<< 15);  
    return *((int*)(void*)&h);
}

これを次のように使用できます。

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

次のように、複数の異なるタイプをマージできます。

public unsafe static void Hash(ref uint h, int data)
{ 
    byte* d = (byte*)(void*)&data;
    AddToHash(d, sizeof(int), ref h);
}

public unsafe static void Hash(ref uint h, long data)
{ 
    byte* d= (byte*)(void*)&data;
    Hash(d, sizeof(long), ref h);
}

内部の知識がなく、オブジェクトとしてフィールドにしかアクセスできない場合は、単純にそれぞれに対して GetHashCode() を呼び出して、その値を次のように組み合わせることができます。

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

残念ながら、 sizeof(T) を実行できないため、各構造体を個別に実行する必要があります。

リフレクションを使用したい場合は、すべてのフィールドで構造的同一性とハッシュを行う関数を型ごとに構築できます。

安全でないコードを回避したい場合は、ビット マスキング手法を使用して、それほど手間をかけずに int (および文字列を処理する場合は char) から個々のビットを引き出すことができます。

于 2009-07-03T13:43:28.430 に答える
1

結合するハッシュコードのメンバーがハッシュコードの規則に従っている限り、このアプローチに問題はありません。要するに ...

  1. プライベートメンバーのハッシュコードは、オブジェクトの存続期間中は変更しないでください
  2. コンテナは、プライベートメンバーが指すオブジェクトを変更してはならず、コンテナのハッシュコードを変更しないようにする必要があります。
于 2009-07-03T12:45:55.477 に答える
1

アイテムの順序が重要でない場合（つまり、{"a"、 "b"}が{"b"、 "a"}と同じである場合）、排他的論理和を使用するか、ハッシュコードを組み合わせることができます。

hash ^= item.GetHashCode();

[編集：マークが別の回答へのコメントで指摘したように、これには{"a"}や{"a"、 "b"、"b"}のようなコレクションにも同じハッシュコードを与えるという欠点があります。]

順序が重要な場合は、代わりに素数を掛けて次を追加できます。

hash *= 11;
hash += item.GetHashCode();

（乗算すると、無視されるオーバーフローが発生することがありますが、素数で乗算すると、最小限の情報が失われます。代わりに16のような数値を乗算すると、毎回4ビットの情報が失われるため、最初のアイテムのハッシュコードが完全になくなったのは8つのアイテムです。）

于 2009-07-03T12:58:16.743 に答える