c# - ハッシュセットでの FIFO 動作の実装

Question

コレクション内の各要素は一意でなければならないという要件があり、その目的のためにハッシュセットを使用しました。

ただし、First In First Our の順序に基づいてハッシュセットから要素を削除することも必要です。ただし、.NET のデフォルトの Hashset DataStructure には、この動作はありません。

この動作を実装するためにハッシュセットを拡張する方法はありますか、それとも他のデータ構造にする必要がありますか?

Answer 1

ハッシュ セットとキューを組み合わせることができます。ハッシュセットは、要素がキューにあるかどうかをテストするための O(1) の複雑さを提供し、キューは先入れ先出しの動作を O(1) で提供します。

参照型を格納している場合、2 つのデータ構造を使用することによる余分なスペースのオーバーヘッドは最小限になります (参照の数が 2 倍になります)。

値型を使用している場合、自己均衡二分探索木は O(log n) への検索と挿入を提供しますが、各要素のコピーを 1 つだけ保存できます。

Answer 2

HS の拡張は不可能です。OrderedDictionaryで試すことができます。値を入力してnull、Key. 広告掲載順と広告掲載順の両方でアクセスできますKey。悲しいことに、それは強く型付けされていません (.NET 1.1 時代のものです... 技術的には .NET 2.0 のものですが、ジェネリックが作成される前に設計されたことは明らかです)。

OrderedDictionary myOrderedDictionary = new OrderedDictionary();
myOrderedDictionary.Add("testKey1", null);
myOrderedDictionary.Add("testKey2", null);
myOrderedDictionary.Add("keyToDelete", null);
myOrderedDictionary.Add("testKey3", null);

// Remove first
myOrderedDictionary.RemoveAt(0);

// Check for existance
if (myOrderedDictionary.Contains("something")) {
}

Answer 3

HashSetここで使用するのは適切ではありません。

キューまたはその拡張が最善の策です。