1

これについては、stackoverflow だけでなく web にもいくつかのトピックがありますが、私はそれらを明確に理解できませんでした。この回答は、ニクラスによるスタックオーバーフローと彼の表現で見つかりました。これにより、トピックに関する有意義な洞察が得られました。

いくつかのアスキー アート

key.hashCode()
     |
     | 32-bit value
     |                          hash table
     V                        +------------+    +----------------------+
HashMap.hash() ----+          | reference  | -> | key1 | value1 | null |
                   |          |------------|    +----------------------+
                   |          | null       |
                   | offset   |------------|    +---------------------+
                   +--------> | reference  | -> | key1 | value1 | ref |
                              |------------|    +---------------------+
                              |    ....    |                       |
                                                  +----------------+
                                                  V
                                                +----------------------+
                                                | key2 | value2 | null |
                                                +----------------------+

JavaはHashtableクラスを実装するためにどのハッシュ関数を使用しますか?

Map aMap = new HashMap();
aMap.put(key,value);
  1. だれか「オフセットとその値とは何か」を説明できますか? オフセット値はどこにマップされますか?
  2. そのハッシュテーブルは何ですか? オブジェクトの配列ですか?、そうであれば、各オブジェクトにはキー、値 1、および参照プロパティがありますか?.

誰かが上の図を段階的に再説明できますか. HashMap の背後にあるハッシュ メカニズムを理解できません。

4

1 に答える 1

6

まず、ハッシュ検索の考え方を説明しましょう。

  1. 検索用のキーを取得できます。たとえば、キーは「hello」などの単なるテキスト文字列です。

  2. この文字列の「チェックサム」を計算してみましょう - 簡単な例として、シンボルの ASCII コードを足し合わせるだけです。(たとえば、実際には数えていませんが) この合計は 1009 です。

  3. たとえば、SZ=10 のように、固定サイズの配列を取得できます。この配列に「hash_table」という名前を付けます。各配列要素には BUCKET が含まれます。これは可能なキーのセットです。

  4. したがって、OFFSET - 配列内のインデックス、つまりハッシュ テーブルを次のように計算できます。

    オフセット = 合計 % SZ = 1009 % 10 = 9;

  5. 次のようにして、"hello" という単語を大道芸人 #9 に登録します。

    hash_table[9].add_to_list("こんにちは");

そこには、セル hash_table[9] に格納されているキー「hello」が 1 つだけあります。

  1. たとえば、「world」などの 2 番目のキーを挿入する必要があるとします。合計を計算すると、37 になります。ここでも、offset = 37 % 10 = 7 を計算します。したがって、このアルゴリズムによって、キー "world" を hashtable[7] に入れます。

  2. 衝突。3 番目の単語キー「衝突」を追加することにしたと想像してください。この単語の合計は 3007 になります。オフセットを計算すると、7 になります。したがって、単語「衝突」は、単語が既に存在するバケットに格納する必要があります。 "世界"。これで結構です。世界の「衝突」を持つ要素をリンクリスト（頭または尾）に追加するだけです。そう：

    hashtable[7] -> "世界" -> "衝突" -> NULL; hashtable[9] -> "こんにちは" ->NULL;

  3. キー「hello」を検索する必要がある場合、チェックサムを再度計算すると、再び 1009 になります。その後、オフセット = 9 を計算し、バケット #9 に直接移動します。そして、linklist を反復すると、「hello」という単語が見つかります。「世界」または「衝突」との類似状況。

表で省略されている単語を検索すると、空のバケット、またはキーが含まれていないバケットに移動します。ということで、検索失敗。

ハッシュ テーブルの幅が広すぎる場合 (たとえば、辞書と同じサイズ)、平均バケット サイズは ~1 要素になります (ハッシュ関数の拡散が良好な場合)。したがって、キーの検索は迅速です。ハッシュサムを計算し、バケットに移動し、バケット内の 1 ～ 2 要素を反復するだけです。

第二 - 私はあなたの質問に答えます:

  1. オフセット - 配列内のインデックスのみ。配列は「ハッシュテーブル」です。各配列要素には、リンクされたリストへのポインターが含まれ、キーが含まれており、同じバケットに格納されています。

  2. バケット スキームのハッシュ テーブル - 単なる配列で、バケットのヘッドへのポインタが含まれます。別のハッシング スキーム (たとえば、複数のハッシングなど) を使用すると、リンクリストなしで、オブジェクト自体を含めることができます。

于 2013-09-24T23:10:15.780 に答える