java - Javaのハッシュ関数とは何ですか?

Question

このウィキペディアのページをチェックアウトしましたが、まだ理解できません。ハッシュ、ハッシュテーブル/ハッシュマップ、およびハッシュ関数の概念を理解するために、誰かが私の頭の悪い心を助けてくれませんか? いくつかの例は本当に役に立ちます。

Answer 1

ウィキペディアの記事には多くの技術情報が含まれていますが、ハッシュの単純化したビューは次のようなものです。

任意のオブジェクトに数値を与えることができる魔法の関数があると想像してください。同じオブジェクトを指定すると、常に同じ数値が返されます。

これで、2 つのオブジェクトが同じかどうかをテストする簡単な方法がわかりました。この関数にそれらの数を尋ねて比較します。それらが異なる場合、それらは同じではありません。

しかし、それらが同じ番号を持っている場合はどうなりますか? 2 つの異なるオブジェクトが同じ番号を持つことはありますか?

はい、これはほとんどのシナリオで可能です。たとえば、この関数が 1 から 10 までの数値のみを与えることができ、100 個の異なるオブジェクトがあるとします。もちろん、いくつかの異なるオブジェクトは同じ番号を持つ必要があります。これがいわゆる「衝突」です。「衝突」があると、簡単な等値テストが役に立たなくなるため、できる限りその発生を最小限に抑えたいと考えています。優れた魔法の機能は、「衝突」の数を最小限に抑えようとする機能です。

では、この数字で他に何ができるでしょうか。これを使用して、配列にインデックスを付けることができます。オブジェクトを指定すると、この魔法の関数の番号で指定されたインデックスに配置できます。この配列は本質的にハッシュテーブルです。この魔法の関数はハッシュ関数です。

Answer 2

ハッシュ関数は、任意の量のデータのコンパクトな表現を作成する方法です。ハッシュコードメソッドを使用するJavaでは、これは、オブジェクトの状態（大きさに関係なく）をint（4バイト）でなんらかの形で記述することを意味します。そして、以下に説明するように、通常はかなり高速になるように書かれています。

ハッシュテーブル/ハッシュマップを単純化するために、ハッシュコードは一種の安価な同等物として機能します。タイプFooの2つのオブジェクトaとbを取り、a.equals（b）が500ミリ秒かかるかどうかを判断しますが、（効率的な）ハッシュコードの計算には10ミリ秒しかかかりません。したがって、最初に直接行うのではなく、a.equals（b）かどうかを知りたい場合は、ハッシュコードを調べて、a.hashCode（）== b.hashCode（）を実行するように依頼します。この例では、これにかかる時間はわずか20msであることに注意してください。

ハッシュコードのAPI定義により、aのハッシュコードがbと等しくない場合、a.equals（b）が真になることはありません。したがって、上記のテストでハッシュコードが等しくないことがわかった場合は、長い.equals（）テストを実行する必要はありません。そのため、常にhashCodeとequalsをオーバーライドする必要があります。

「適切な」または「十分に分散された」ハッシュコードの記述に関するリファレンスも表示される場合があります。これは、ハッシュコードと等号に関する前のステートメントの逆が真ではないという事実と関係があります。より具体的には、a.hashCode（）== b.hashCode（）は必ずしもa.equals（b）を意味するわけではありません。したがって、適切なハッシュコードのアイデアは、a.hashCode（）== b.hashCode（）の可能性を減らすことです。 a.equals（b）はfalseです。これは、ハッシュ関数の衝突と呼ばれることがあります。

ハッシュマップ/テーブルに戻ります。これらは、キーと値のペアに基づいています。したがって、値を追加または取得するときに、キーを指定します。したがって、マップが最初に行う必要があるのは、キーを探すことです。つまり、指定したキーに.equals（）するものを見つけることを意味します。ただし、上記で説明したように、.equals（）は非常に遅くなる可能性があります。つまり、最初にハッシュコードをチェックすることで、比較を大幅に高速化できます。ハッシュコードが適切に分散されている場合、xが確実に！=yである場合をすばやく知る必要があります。

現在、比較に加えて、ハッシュマップ/テーブルは実際にハッシュコードを使用してデータの内部ストレージを整理していますが、これは現時点で理解しようとしている範囲を超えていると思います。

Answer 3

この本 (およびそれをサポートするビデオ講義) は、アルゴリズムとデータ構造の優れた説明を提供します。ハッシュ関数に関する講義がいくつかあります ( 1 , 2 )。私はそれをお勧めします。

_{(ソース: mit.edu )}

また、クラスhashCode()のインスタンスで呼び出された参考までに、Objectメモリ内のこの特定のインスタンスのアドレスを返します。コメントでpolygenelubricantsが指摘しているように、実際にはそうではありません。

Answer 4

ハッシュ テーブルのインデックスへのキーのマッピングは、ハッシュ関数と呼ばれます。ハッシュ関数には 2 つの部分が含まれます

Hash Code Map : キーを任意の範囲の整数に変換します。

圧縮マップ: これらの整数をハッシュテーブルが持つキーの範囲に変換します。

http://coder2design.com/hashing/から取得

Answer 5

ハッシュテーブルは基本的に、配列に何かを格納し、インデックスを介して配列内の何かを検索するのとほぼ同じ速さで取得する方法であり、あまりスペースを浪費することはありません。

ハッシュ関数の仕事は、(このコンテキストでは) オブジェクトの内容に基づいて、オブジェクトが格納される配列インデックスを計算することです。つまり、同じオブジェクトに対して常に同じ結果を返す必要があり、可能な限り異なるオブジェクトに対して異なる結果を返す必要があります。2 つの異なるオブジェクトが同じハッシュを持つ場合、それは「衝突」と呼ばれ、これらのケースを特別に処理する必要があり、全体が遅くなります。