平均的なプログラマーにとって「十分に良い」ハッシュ関数はありますか？

Question

クラスに対してhashCode（）を実装する必要があると言われていますが、私のような人には、これをどうやって行うのか、あるいは「間違っている」場合はどうなるのかについての考えはありません。たとえば、ツリー内のノードをインデックスするためのハッシュ関数が必要です（Finding the most frequent subtrees in a collection of (parse) trees）。この場合、順序付き子ノードに基づいてハッシュコードを再帰的に生成する必要があります。ハッシュコードの回答のrecent discussionで

hashCode = function(child1.hashCode, child2.hashCode, ...) 

（長期プライムおよび31に基づいて）文字列のハッシュを含めてもbitshifting。文字列のハッシュは：

// adapted from String.hashCode() 
public static long hash(String string) { 
    long h = 1125899906842597L; // prime 
    int len = string.length(); 

    for (int i = 0; i < len; i++) { 
    h = 31*h + string.charAt(i); 
    } 
    return h; 
} 

私はセキュリティに興味がなく、衝突を気にしません。害よりも優れた（そしてそれを全く呼び出すよりも良い）順序づけられたオブジェクトのハッシュコードを組み合わせるための「普遍的な機能」はありますか？

また、一般的なケースを検索できるサイトはありますか？文字列、リストなど）

普遍的なアプローチが期待されていたので、私は言語を指定しませんでした。しかし、言語に深刻な問題がある場合は、その言語とそれが普遍的でない理由を明記してください。

UPDATE IDEのhashCodeジェネレータを使用することをお勧めします。それは優れたデフォルト設定です。ここではNetbeansのです：

public int hashCode() { 
    int hash = 5; 
// objects 
    hash = 97 * hash + (this.rootElement != null ? this.rootElement.hashCode() : 0); 
    hash = 97 * hash + (this.tableElement != null ? this.tableElement.hashCode() : 0); 
// a string 
    hash = 97 * hash + (this.tag != null ? this.tag.hashCode() : 0); 
    return hash; 
} 

Answer 1

Joshua BlochのEffective Javaには優れたhashCode（）があります。サンプル第3章「すべてのオブジェクトに共通のメソッド」は、でした（これは、Sunの古いサイトにページがあったときに戻っていましたが、あなたが検索しても、その章のPDF版が見つかる可能性がありますどこか）。

Apache Commons LangでHashCodeBuilderのソースを見ることもできますが、引用することなくクラスのためにコピーしないでください。それは実際にこれについて学ぶために費やされた時間です - それはあなたをより良い人にします。

Answer 2

は、Windowsを使っているのであれば、あなたはHashData()を使用することができます。

Answer 3

タグがありませんが、私はあなたがJavaについて話していると仮定します。

「怠惰な」ソリューションはEclipse 3.5でパッケージ化されています。これはボタンを押すだけでハッシュコードを生成します。 toString（）とequals（）も同様です。非常に素晴らしい！あなたはIDEAとNetBeansで同様の機能を見つけることができると思います。

これ以外にも、同じ入力に対して同じ値を一貫して生成する任意のハッシュ関数が行います。これは（おそらく）ハッシュマップのようなものの効率にのみ影響します。

Answer 4

カスタムクラスのハッシュコードの定義に関して言えば、すべてのフィールドのハッシュコード関数の何らかの数学的連結を定義するのが最善の方法です。

ハッシュコードを定義する際には、通常は衝突を最小限に抑えるため、このようなことを行うと通常は明確になります。

hashcode=(field1.hashcode()*7)+(field2.hashcode()*3)+(field3.hashcode()*51)... 

Answer 5

任意の管理対象環境では、オブジェクトハッシュ関数の生の実装はメモリアドレス自体です。ハッシュ関数のプロパティを気にしない場合は、同じ値を表す別々のインスタンス間にある種の等価関係が存在する限り、任意の値が行います。

リレーショナルデータベースの設計に精通している場合は、オブジェクトの主キーについて考えてください。主キーはどのような値を構成しますか？

は、それがうまく、その後のhashCodeの実装は次のようになり、a, b and cだと言うこの

return a.hashCode()^b.hashCode()^c.hashCode(); 

^でXOR（排他的OR）ビット単位の演算、一緒にあなたがチェーンにすることができ、このような値の任意の数ハッシュ値を形成し、それでもまともな普及を維持する。

Answer 6

何が問題になる可能性があるのあなたの質問に答えるには：あなたのクラスのインスタンスの場所を見つけるためにあなたの関数によって生成されたハッシュコードは、ハッシュテーブル（辞書/マップ）に置く場合に使用されます。あなたのhashfunctionがあまりにも多くの衝突を生成する場合、あなたのハッシュテーブルのパフォーマンスはO（n）と同じくらい悪い可能性があります。

Answer 7

これは、私は（C＃で）を使用する機能を組み合わせたハッシュコードである：

public static int CombineHashCodes(params int[] hashCodes) 
{ 
    unchecked 
    { 
     var result = 0; 
     foreach (var hash in hashCodes) 
      result = (result * 397)^hash; 
     return result; 
    } 
} 

直感的推論を組み合わせ態様は、XOR演算子であるということです。これは、.NET 4がタプルに対して行う方法です。

public static int CombineHashCodes(int h1, int h2) 
{ 
    return ((h1 << 5) + h1)^h2; 
}