java - Hashmapはランダムアクセスを使用しますか？

Question

JavaのHashMapでは、ハッシュ値がバケットに格納されることを理解しました。これは、検索の高速化に役立ちます。
取得中に、ハッシュコードをチェックし、それに応じてバケット番号を見つけます。

1から10までのバケット番号があり、ハッシュコードから見つかったバケット番号がバケット番号5である場合
。
コントロールはどのようにバケット番号5に転送されますか？バケット1を通過してバケット4に到達して5に到達しますか、それとも他のメカニズムを使用しますか？

Answer 1

直接配列アクセスです。反復/トラバーサルなし。ただし、バケット内のオブジェクトをトラバースし、 と比較する必要がありますequals。多分それはあなたを混乱させています。

Answer 2

ハッシュ テーブルはバケットの配列として実装されるため、配列のランダム アクセスインデックスを使用して、ハッシュが与えられた適切なバケットに到達します。

Answer 3

ハッシュ関数を使用してバケットを見つけます。

10 個のバケットがある場合、たとえば文字列のセットについて、文字値が追加され、10 個のバケットにハッシュされるとします。

文字列を 10 個のバケットにマップする簡単なハッシュ関数を書きましょう。

 For any non empty String, 

             hash function f = sum of (index of characters) % 10

例: abc = 1+2+3 %10 = 6. したがって、「abc」は 6 番目のバケットになります。xyz = 24+25+25 %10 = 7.5~ 8 . したがって、「xyz」は 8 番目のバケットなどになります。

したがって、「xyz」を検索すると、ハッシュ関数はここでバケットを直接見つけます。

ハッシュ関数は、ハッシュ マップの作業の中心です。

Answer 4

java.util.HashMap コードからの抜粋

         /**
          * Adds a new entry with the specified key, value and hash code to
          * the specified bucket.  It is the responsibility of this
          * method to resize the table if appropriate.
          *
          * Subclass overrides this to alter the behavior of put method.
          */
         void addEntry(int hash, K key, V value, int bucketIndex) {
             Entry<K,V> e = table[bucketIndex];
             table[bucketIndex] = new Entry<>(hash, key, value, e);
             if (size++ >= threshold)
                 resize(2 * table.length);
         }

したがって、配列からランダムにアクセスされます。

Answer 5

There are several strategies while adding and retrieving the values some of them are direct chaning, open addressing etc Based on these the way it stores and fetching values will change.For example, in direct chaining each space of bucket array is pointer to a linked list that contains the key-value pairs that hashed to the same location.So when you search the value, it is scanning the entire list with the give value.