144

タイプを調べてHashSet<T>いますが、コレクションのどこにあるのかわかりません。

代わりにそれを使用できますList<T>か？のパフォーマンスはHashSet<T>もっと良くなると思いますが、その要素への個々のアクセスを見ることができませんでした。

列挙専用ですか？

4

11 に答える 11

234

重要なことHashSet<T>は、名前のすぐそこにあります。それはsetです。単一のセットでできることは、そのメンバーが何であるかを確立し、アイテムがメンバーであるかどうかを確認することだけです。

単一の要素 (例: ) を取得できるかどうかを尋ねることset[45]は、セットの概念を誤解しています。セットの 45 番目の要素などというものはありません。セット内のアイテムには順序がありません。セット {1, 2, 3} と {2, 3, 1} は、メンバーシップが同じであるため、あらゆる点で同一であり、メンバーシップだけが重要です。

HashSet<T>セット内のアイテムに順序が課されるため、a を反復するのはやや危険です。その順序は実際にはセットのプロパティではありません。それに頼ってはいけません。コレクション内の項目の順序が重要な場合、そのコレクションはセットではありません。

セットは本当に限られており、ユニークなメンバーがいます。一方、彼らは本当に速いです。

于 2009-08-08T18:09:43.250 に答える
113

これが私が使用する実際の例ですHashSet<string>：

UnrealScriptファイルの構文ハイライトの一部は、Doxygenスタイルのコメントを強調表示する新機能です。@または\コマンドが有効かどうかを判断して、灰色（有効）または赤（無効）のどちらで表示するかを判断できるようにする必要があります。私はHashSet<string>すべての有効なコマンドを持っているので@xxx、レクサーでトークンをヒットするたびにvalidCommands.Contains(tokenText)、O（1）の有効性チェックとして使用します。有効なコマンドのセットにコマンドが存在することを除いて、私は本当に何も気にしません。私が直面した選択肢を見てみましょう：

  • Dictionary<string, ?>：値にはどのタイプを使用しますか？を使用するだけなので、値は無意味ですContainsKey。注：.NET 3.0より前は、これがO（1）ルックアップの唯一の選択肢でした-3.0HashSet<T>で追加され、4.0で実装するように拡張されISet<T>ました。
  • List<string>：リストを並べ替えておくと、BinarySearchO（log n）であるを使用できます（上記のこの事実はわかりませんでした）。ただし、有効なコマンドのリストは変更されない固定リストであるため、これは単に...
  • string[]：ここでも、Array.BinarySearchO（log n）のパフォーマンスが得られます。リストが短い場合は、これが最もパフォーマンスの高いオプションである可能性があります。常に、、、またはよりもスペースのオーバーヘッドが少なくHashSetなりDictionaryますList。を使用してもBinarySearch、大きなセットの場合は高速ではありませんが、小さなセットの場合は実験する価値があります。でも私のものは数百点あるので、これを渡しました。
于 2009-08-08T18:32:57.507 に答える
24

AはインターフェースをHashSet<T>実装しICollection<T>ます：

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

List<T>を実装しIList<T>、ICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

HashSetには、ハッシュテーブルを介して内部的に実装されたセマンティクスが設定されています。

セットは、重複する要素を含まず、要素の順序が特定されていないコレクションです。

HashSetがインデックス/位置/リストの動作を失った場合、HashSetは何を獲得しますか？

HashSetからのアイテムの追加と取得は、インデクサーを介さずに常にオブジェクト自体によって行われ、O（1）操作に近いものです（リストはO（1）追加、O（1）インデックスによる取得、O（n）検索/削除する）。

Dictionary<TKey,TValue>HashSetの動作は、キーを値として追加/削除するだけで、ディクショナリ値自体を無視することで、を使用する場合と比較できます。辞書のキーには重複する値がないことが期待されます。これが「設定」部分のポイントです。

于 2009-08-08T18:54:26.357 に答える
15

パフォーマンスは、リストよりもハッシュセットを選択する悪い理由になります。代わりに、あなたの意図をよりよく捉えるものは何ですか？順序が重要な場合は、Set（またはHashSet）が出ています。重複が許可されている場合も同様です。しかし、順序を気にせず、重複したくない状況はたくさんあります。その場合は、セットが必要です。

于 2009-08-07T23:33:56.470 に答える
12

HashSetは、ハッシュによって実装されるセットです。セットは、重複する要素を含まない値のコレクションです。セット内の値も通常、順序付けされていません。したがって、セットを使用してリストを置き換えることはできません（最初にセットを使用する必要がない限り）。

セットが何に適しているのか疑問に思っている場合：明らかに、重複を取り除きたい場所ならどこでも。少し不自然な例として、ソフトウェアプロジェクトの10.000のリビジョンのリストがあり、そのプロジェクトに貢献した人の数を調べたいとします。を使用してSet<string>リビジョンのリストを繰り返し処理し、各リビジョンの作成者をセットに追加できます。反復が完了すると、セットのサイズが探していた答えになります。

于 2009-08-07T23:30:42.997 に答える
11

HashSet は、IEnumerable コレクション内の重複する要素を削除するために使用されます。例えば、

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

これらのコードが実行された後、uniqueStrings は {"abc"、"ghjr"、"yre"、"obm"、"qwrt"、"vyeu"} を保持します。

于 2013-04-25T21:15:06.973 に答える
6

おそらく、ハッシュセットの最も一般的な用途は、特定の要素が含まれているかどうかを確認することです。これは、包含のチェックが O( n) (およびそれが O(log n) であるソート済みセット)。そのため、アイテムが何らかのリストに含まれているかどうか、多くのチェックを行う場合、ハッシュセットはパフォーマンスの向上につながる可能性があります。それらのみを反復する場合、大きな違いはありません (セット全体の反復は O(n) であり、リストとハッシュセットの場合と同じで、アイテムを追加するときに多少のオーバーヘッドがあります)。

いいえ、セットにインデックスを付けることはできません。セットは順序付けられていないため、とにかく意味がありません。いくつかのアイテムを追加すると、セットはどれが最初でどれが2番目かなどを覚えていません.

于 2009-08-07T23:39:38.487 に答える
5

HashSet<T>数学的集合をオブジェクトとして表すことができる .NET フレームワークのデータ構造です。この場合、ハッシュ コード (GetHashCode各項目の結果) を使用して、セット要素の等価性を比較します。

セットは、その中に含まれる同じ要素の出現を 1 回だけ許可するという点で、リストとは異なります。2 番目の同一の要素を追加しようとすると、HashSet<T>単に返されます。実際、内部データ構造は単なるハッシュテーブルであるため、false要素の検索は非常に高速です (時間)。O(1)

どちらを使用するか迷っている場合は、適切なList<T>場所を使用するHashSet<T>ことは最大の間違いではありませんが、コレクションに望ましくない重複アイテムがある場合に問題が発生する可能性があることに注意してください。さらに、ルックアップ (アイテムの取得) は非常に効率的です。理想的にはO(1)(完全なバケット化のために)O(n)時間ではなく、多くのシナリオで非常に重要です。

于 2009-08-07T23:36:54.327 に答える
4

List<T>順序付けられた情報のセットを格納するために使用されます。リストの要素の相対的な順序がわかっている場合は、それらに一定の時間でアクセスできます。ただし、要素がリスト内のどこにあるかを判断したり、リスト内に存在するかどうかを確認したりする場合、ルックアップ時間は線形です。一方、HashedSet<T>格納されたデータの順序は保証されないため、その要素への一定のアクセス時間が提供されます。

名前が示すように、セット セマンティクスHashedSet<T>を実装するデータ構造です。データ構造は、従来の List 実装では効率的に実行できないセット操作 (つまり、Union、Difference、Intersect) を実装するように最適化されています。

したがって、使用するデータ型の選択は、アプリケーションで何をしようとしているのかによって異なります。コレクション内で要素がどのように並べられているかを気にせず、列挙または存在の確認のみを行いたい場合は、 を使用しますHashSet<T>。List<T>それ以外の場合は、または別の適切なデータ構造の使用を検討してください。

于 2009-08-07T23:37:46.260 に答える
1

要するに、ディクショナリ (または S が T のプロパティであるディクショナリ) を使用したくなるときはいつでも、HashSet (または HashSet + S と同等の T に IEquatable を実装する) を検討する必要があります。

于 2009-08-08T01:22:19.527 に答える