Java言語で使用されるハッシュ関数

Question

Javaには、HashMapsまたはHashTablesの美しいinbuiltサポートがあることは知っています。

Java言語では、どのような種類のハッシュ関数や技術が採用されているのか、誰かが知っていますか？

パフォーマンスを向上させ、アクセス時間を短縮するために、アプリケーションをより具体的にするためにこれらの機能を調整することは可能ですか？

読んでいただきありがとうございます！

Answer 1

Javaは、あなたのクラスだけでなく、アプリケーションに、しかし、あなたの個々のタイプに適していますハッシュアルゴリズムを使用するためのhashCode()メソッドをオーバーライドすることができます：

public class Employee { 

    private int id; 
    // Default implementation might want to use "name" for as part of hashCode 
    private String name; 

    @Override 
    public int hashCode() { 
    // We know that ID is always unique, so don't use name in calculating 
    // the hash code. 
    return id; 
    } 
} 

Answer 2

Goナッツ。

http://www.docjar.com/html/api/java/util/HashMap.java.html

さらに、あなたは常にあなたがマップがほぼいっぱいになったときプット時間を短縮するであろう、することが必要になりますようの大きさにリサイズしきい値と初期メモリ使用量を設定することができます。マップがスレッド化されている場合は、ConcurrentHashmapを使用することでパフォーマンスが大幅に向上します。

Answer 3

ハッシュコードが格納されたオブジェクトごとに計算され、コレクションにこれは標準的なアルゴリズムを使用して計算されます（Effective Javaによる）。詳細については、それを参照してください。

実際にオブジェクト単位でhashcodeメソッドをオーバーライドできます。 hashCodeメソッドを実装するための最良の方法は、HashcodeBuilder（whcih経由でコモンズラングフレームワークの一部である、ここを参照してください：

http://www.ibm.com/developerworks/java/library/j-jtp05273.html

：ハッシュコードの

http://commons.apache.org/lang/

フォアの詳細血みどろの詳細はこちらの記事を参照してください助け

希望。

Answer 4

私はJavaがハッシュマップやハッシュテーブルのための美しい作り付けのサポートを持っていることを知っている。

は

完全ハッシュマップリテラルの構文を欠いている、私は本当にそれを言わないだろう...

とにかく、他の人が指摘したように、それがどのような彼らのhashCodeを指定するには、個々のクラスに任されて（）すべきbe（デフォルトはメモリアドレスのハッシュです）。自分で実装する場合は、hashCode（）メソッドの規約に従っていることを確認してください（特にequals（）と矛盾しないようにする必要があります）。そうでなければ、クラスはHashMapのキーに対して機能しません。

j ava.util.HashMapのソースコードを直接見て、それらの実装方法を確認することもできます。たとえば、HashMapはバケットの配列を使用し、バケットはリンクされたリストを使用してオーバーフローする可能性があります。

さらに読むには、同時に多くのスレッドから安全にアクセスできるConcurrentHashMapと、順序付け可能なキーのマップを構築するTreeMap（および必ずしもハッシュされる必要はない）。

Answer 5

一般に、標準のJDKクラスのハッシュ関数についてあまり心配する価値はありません。 Stringをオーバーライドすることはできますが、実際には、ハッシュ関数は実際には常に「十分に良い」ものです。多少の例外があります。 BigIntegerやコレクションなどの特定のクラスは、その中に含まれるすべての要素を循環するたびにハッシュコードを計算しますが、これはかなり疑わしい場合もあります。

自分のクラスのハッシュコードを設計する場合、しようとしていることは、整数の範囲にランダムに拡散することです。これを行うには、一般的にオブジェクト内の連続するフィールドのビットを「ミックス」したいと考えています（how the String hash code mixes bitsをグラフィカルに示す私のWebサイトの記事に興味があるかもしれません）。現在のハッシュに奇数（一般に素数）を掛け、次の要素のハッシュを加えることは、一般に、最初の試みとして十分にうまく機能する。 （ただし、結合される数値/ハッシュコードの下位ビットが0になる傾向があるなどの理由で、このメソッドで問題が発生する可能性があります。実際にはすべての場合にうまく機能することが絶対的に保証されていません）。

次に、ハッシュコードのテストを検討することができます。一連のランダムなオブジェクトを生成したり、実際のものを使用したりして、ハッシュコードを計算します。そして、例えば16ビットのハッシュコードを取り出し、衝突の数を確認します。取得した衝突の数がhash collisions you'd expect to get by chanceにほぼ一致することを確認します。たとえば、ハッシュコード（& 0xffff）の下位16ビットをANDで除いて、1000個のランダムオブジェクトの後に約8個の衝突があるとします。 2000年以降、約30回の衝突が予想されます。

性能に関しては、ハッシュ計算速度のハッシュ品質を犠牲にするよりも、よく分散されたハッシュコードを取得するほうが、今日では一般的により有益になると私は考えています。

Answer 6

速いハッシュが必要な場合は、別の実装を使用することをお勧めします。高速util（http://fastutil.dsi.unimi.it/）またはtrove（http://trove4j.sourceforge.net/）を試してください。彼らは明らかに速いですが、タイプに特化しています。

Answer 7

同様に、hashCodeをオーバーライドする場合は、equalsをオーバーライドする必要があります。

Answer 8

equals（）メソッドに基づいてお互いに等しいオブジェクトが同じhashCode（）値を提供しなければならないということに従うべきである「hashCode/equals contract」があります。 ただし、同じhashCodeを持つすべてのオブジェクトも同じである必要はありません。あなたは詳細を教えるhttp://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode()を見てください。

最初に関与した対称性の周りを頭で囲むのはちょっと難しいかもしれませんが、あなたがアプリをHashMapや友人に入れたときにあなたのアプリで奇妙な振る舞いをしたくないのであれば、その契約に従わない。

Effective Javaのコピーを入手し、hashCode/equalsの章を読んで完全に理解することをお勧めします。