0

GrepCode.com で HashMap のソース コードをチェックインしたところ、オブジェクト ハッシュコードが配列に格納されていることがわかりました。

transient Entry[] table;

  public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
         int hash = hash(key.hashCode());
         int i = indexFor(hash, table.length);
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }

         modCount++;
         addEntry(hash, key, value, i);
         return null;
     }

 void addEntry(int hash, K key, V value, int bucketIndex) {
         Entry<K,V> e = table[bucketIndex];
         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
         if (size++ >= threshold)
             resize(2 * table.length);
}

提案してください。

4

7 に答える 7

4

これは内部実装の詳細です。HashMapのコントラクトは順序付けを保証しないため、位置アクセスを許可すると、本質的に、実装が微調整されるたびに壊れるコードを記述できるようになります。

于 2013-10-07T05:09:05.513 に答える
2

HashSet または HashMap が位置ベースのアクセスをサポートしないのはなぜですか?

  • ハッシュ テーブルの配列内のエントリの「位置」は安定していません。

    • 新しいエントリが追加された場合、位置は予測できない形で変化する可能性があります。

    • ハッシュ テーブルをコピーすると、要素の位置が予測できない形で変化する可能性があります。

    • 正確な動作は実装固有です。

  • 配列はエントリではなく実際のエントリチェーンであるため、配列内のエントリの「位置」は完全な位置ではありません。エントリの完全な位置は、実際には 2 つの整数です。ハッシュ配列のインデックスと、ハッシュ チェーンの開始点からの距離です。

  • エントリの「位置」は、エントリ自体や、エントリが追加された順序と意味のある関係を持ちません。

これらのことが組み合わさって、「位置」が実質的に役に立たなくなります...そしておそらく使用するのは危険です. したがって、これをサポートするのは悪い考えです。

実際、私は少し単純化しすぎました。すべてのハッシュ コードが何であるか、およびハッシュ テーブルを現在の状態にするために使用された変更操作の正確なシーケンスがわかっている場合、ハッシュ チェーンと、各エントリのハッシュ チェーン内の位置を把握することができます。 . ただし、これを行うには、一連の操作全体を効果的に再生する必要があります。さらに、これを行ったとしても、その情報を有用な目的に悪用することはできません。

于 2013-10-07T05:24:51.973 に答える
2

確かに「オブジェクトのハッシュコードを配列に格納」しますが、マップ内のすべてのオブジェクトを配列に格納するわけではありません。もう一度見てください。Entry アイテムを配列に格納しますが、各 Entry アイテムはリンクされたリストの先頭です。ハッシュ テーブルのすべての値が配列へのインデックスを持っているわけではありません。したがって、インデックス付きアクセスは無意味です。

于 2013-10-07T05:19:16.490 に答える
1

位置インデックスを使用する明確な方法はありません。バケットのインデックスはありますが、バケットに複数のエントリを持つことができます。これは、一部のポジションにはエントリがないことを意味しますが、一部のポジションには複数のエントリがあります。どのような戦略を使用しても、単純な方法でインデックスをインクリメントする方法はありません。

エントリを追加すると、すべての位置が再配置される可能性があるため、エントリを追加する前後の位置が役に立たなくなります。また、エントリのインデックスがどうあるべきかを表現する自然な方法もありません。

あなたが持っている最も近いオプションは、エントリを繰り返し処理し、インデックスをそれぞれに関連付けることです。問題は、マップの更新間での保存が効率的ではないか、保証されていないことです。

于 2013-10-07T05:59:48.587 に答える
1

Sets とsの概念にMapは順序付けが含まれていないため、「位置ベース」のアクセスは意味がありません。aSetに要素があるかどうか、および aMapはキーで値を検索します。要素を位置で選択できるように何らかの順序を設定したい場合は、SortedMapまたはSortedSetのようなより具体的なデータ構造を使用します。これにより、要素が並べ替えられた順序で保持され、部分範囲を分割および選択するための要素が含まれます。

于 2013-10-07T05:12:53.187 に答える
1

はい、内部的に HashMap/HashSet が配列を使用することは事実です。しかし、これらの配列への保存も検索もシーケンシャルではありません。理由は簡単です。これらのコレクションはhashing、オブジェクトを格納および取得するバケットを決定するために使用されます。エントリごとに計算されるハッシュは連番ではありません。また、各要素のハッシュは、これらのコレクションからエントリを格納および取得するために使用されます。

于 2013-10-07T05:13:09.950 に答える
0

HashMapは、順序を保証しません。

このクラスは、マップの順序を保証しません。特に、順序が長期的に一定であることを保証するものではありません。

ただし、必要に応じて、LinkedHashMapクラスを通過できます。これは、キーがマップに挿入された順序 (insertion-order)です。

于 2013-10-07T05:12:37.140 に答える