6

私はlinkedHashSetについて次のことを知っています

  • 挿入順序を維持します
  • LinkedList を使用して順序を保持する
  • 私の質問は、ハッシュがどのように現れるかです??

ハッシングを使うとバケット化の概念が出てきます

ただし、JDK のコードを確認すると、LinkedHashSetの実装にはコンストラクターのみが含まれ、実装が含まれていないように見えるため、すべてのロジックが HashSet で発生すると思いますか?

  • それで、hashSetはデフォルトでLinkedListを使用しますか？

私の質問をこのようにさせてください...目的がコレクションを書くことである場合

  1. 独自の価値を維持する
  2. リンクされたリストを使用して挿入順序を保持する THEN ... ハッシングなしで簡単に実行できます ... このコレクションを LinkedSet と呼ぶことができます

HashSet と LinkedHashSet の違いは何かという同様の質問を見ましたが、あまり役に立ちませんでした

私の質問をもっと説明する必要があるかどうか教えてください

4

5 に答える 5

1

間違い。の実装LinkedHashSetは実際にはすべてLinkedHashMap. (そして、 の実装HashSetは本当にすべてですHashMap. Le Gasp!)

HashSetリンクされたリストはまったくありません。

リンクされたリストに裏打ちされたコレクションを作成して、要素を一意に保つことは完全に可能LinkedSetです-それは、そのパフォーマンスがかなりひどいものになるだけです.

于 2013-02-01T04:12:28.583 に答える
1

これは「興味深い」実装です。HashSetLinkedHashSet のコンストラクターは、反復順序を維持するためのデータ構造 (LinkedHashMap) をセットアップするパッケージ プライベート コンストラクターに従います。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

API 設計者は、適切なドキュメントを使用して、このコンストラクターをパブリックとして公開することもできましたが、コードをより「自己文書化」することを望んでいたと思います。

于 2013-02-01T04:14:22.713 に答える
1

よく見ると、通常のコンストラクターではなく、HashSet で保護されたコンストラクターを実際に使用していることがわかります。例えば、

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

したがって、LinkedHashSet をサポートするために使用される keySet は、実際には、通常の HashSet のような通常の HashMap ではなく、LinkedHashMap の実装に由来します。実際には java.util.LinkedList を使用しません。バケットの内容の実装内でリストを形成するポインタを維持するだけです ( Map.Entry<K,V>)

316    private static class Entry<K,V> extends HashMap.Entry<K,V> {
317        // These fields comprise the doubly linked list used for iteration.
318        Entry<K,V> before, after;
319
320        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
321            super(hash, key, value, next);
322        }

ハッシュは、一意性を強制し、ほとんどの操作で一定時間のパフォーマンスを提供するコレクションを作成する簡単な方法であるため、全体像が見えてきます。確かに、リンクされたリストを使用して一意性チェックを追加することもできますが、重複をチェックするためにリスト全体を反復処理する必要があるため、いくつかの操作の時間が O(N) になります。

于 2013-02-01T04:18:21.987 に答える
1

コードサンプル

Set<Registeration> registerationSet = new LinkedHashSet<>();
registerationSet.add(new Registeration());

Line2の説明。

  1. 登録オブジェクトの hashCode を計算します
  2. 登録セットで hashCode を検索して、バケットを見つけます
  3. 候補リストにあるバケット内の等しいオブジェクトをチェックします
    • 3.1. 等しい場合は、新しいオブジェクト参照で置き換えます
    • 3.2. 見つからない場合は、登録オブジェクトの参照をバケットに追加/追加します

それと並行して、

リストは、挿入されたすべての要素のエントリ順序/キューを維持します

  1. 常に、最後に新しい参照を追加します
  2. 置換の場合 (上記の 3.1.)、以前の出現を削除します。
于 2017-09-10T19:13:40.563 に答える
0

あなたの質問に対する具体的な回答について

  • ハッシュはどのように理解されますか? (LinkedHashSet 内)

Java ドキュメントの内容...

  • HashSet と同様に、ハッシュ関数がバケット間で要素を適切に分散すると仮定すると、基本操作 (追加、保持、および削除) に対して一定時間のパフォーマンスが提供されます。
  • このリンクされたリストは、要素がセットに挿入された順序 (挿入順序) である反復順序を定義します。

ハッシュコードによってアクセスされるバケットは、ランダム アクセスを高速化するために使用され、LinkedList の実装は、要素を挿入順に吐き出すイテレータを返すためのものです。

私はあなたの質問に答えたことを願っていますか？

于 2013-02-01T05:13:18.477 に答える