3

異なる hashCode を持つ要素が HashSet に追加されると、新しい要素が追加されますよね? この新しいバケットはどのデータ構造に追加されますか? 新しい要素が追加されるたびに、ある種の配列とサイズ変更に再び頼るので、HashSet O(n) への追加と削除が複雑になりますか?

いくつかの投稿を読んだ後、JDK の一部の実装では HashMap を HashSet のバックアップ コレクションとして使用していることを知りましたが、その HashMap はこれに何を使用しているのでしょうか?

4

3 に答える 3

5

ソースコードはいつでも見ることができます。

そして、HashMap にバケットの配列があることがわかります。

transient Entry[] table;

すべてのバケットは基本的にリンクされたリストです。

static class Entry<K,V> implements Map.Entry<K,V> {
         final K key;
         V value;
         Entry<K,V> next;
         final int hash;

配列は、指定されたハッシュ コードのバケットへの一定時間のアクセスを提供し、そのリストをループする必要があります (1 つまたは 2 つ以上のエントリが含まれていないことを願っています)。

final Entry<K,V> getEntry(Object key) {
         int hash = (key == null) ? 0 : hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];
              e != null;
              e = e.next) {
             Object k;
             if (e.hash == hash &&
                 ((k = e.key) == key || (key != null && key.equals(k))))
                 return e;
         }
         return null;
}

異なる hashCode を持つ要素が HashSet に追加されると、新しい要素が追加されますよね?

既存のものと同じ hashCode を持つ要素が追加されると、同じバケット (リンクされたリストの最後) に入ります。

新しい hashCode を持つ要素が追加されると、別のバケットに移動する場合と移動しない場合があります (バケットよりもはるかに多くの hashCode があるため)。

すべてのバケットは、マップのサイズが決定されるときに事前に作成されます。容量制限に達すると、バケットのサイズが変更され、すべてが新しいバケットに入れられます。

この新しいバケットはどのデータ構造に追加されますか?

バケットは追加されません。バケットの固定配列があります。より多くの容量が必要な場合は、構造全体がより大きな配列で再構築されます。

新しい要素が追加されるたびに、ある種の配列とサイズ変更に再び頼るので、HashSet O(n) への追加と削除が複雑になりますか?

毎回ではありません。理想的には決して。容量の計算を誤って、さらに容量が必要になった場合のみ。次に、すべてが新しい配列にコピーされるため、コストがかかります。このプロセスは基本的に ArrayList と同じです。

于 2013-03-08T04:28:13.563 に答える
0

HashMapの配列を使用しますMap.Entry：配列内の要素はペアkey,valueです。

要素が挿入されると、バケットの位置はハッシュコードから計算されます。挿入されたキーが、バケットにすでに格納されているキーと異なる場合（ハッシュコードの衝突）、次の空のバケットが選択されます。このアルゴリズムの結果、配列が「ほぼ満杯」のハッシュマップでの操作はかなりコストがかかります。実際、空きバケットが1つしかない場合は、O（n）になります。

この問題を回避するためHashMapに、現在のカウントが内部アレイ容量の一定の割合（「負荷率」、デフォルトでは75％）を超えると、自動的にサイズが変更されます。これは、75要素HashMapが100要素の配列によってベイク処理されることを意味します。負荷率を下げると、メモリオーバーヘッドが増加しますが、平均実行順序がほぼ一定にバイアスされます。

すべての要素が同じhashCodeを持っている場合、最悪の場合の挿入は依然としてO（n）である可能性があることに注意してください。

于 2013-03-08T04:39:17.653 に答える
0

HashSetおよびHashMapの Javadoc を読むだけでも、多くの情報を収集できます。HashSet は HashMap によって支えられています。

HashMap Javadoc によると、初期容量と負荷係数によって定義されています。バッキング ハッシュ テーブルは、負荷係数を超えるまでサイズ変更されないため、質問の 1 つに答えると、いいえ、マップからの新しい追加/削除のたびにサイズ変更が行われるわけではありません。

于 2013-03-08T04:31:40.797 に答える