c# - 在哈希集中实现 FIFO 行为

Question

我有一个要求，集合中的每个元素都必须是唯一的，为此我使用了哈希集。

但是，我也想根据 First In First Our order 从哈希集中删除元素。但是 .NET 中的默认 Hashset DataStructure 没有这种行为。

有没有办法扩展哈希集来实现这种行为，或者我应该使用其他数据结构。

Answer 1

您可以将哈希集与队列配对。哈希集会给你 O(1) 复杂性来测试元素是否在队列中，队列会给你先进先出的行为，也是 O(1)

如果您要存储引用类型，则使用这两种数据结构的额外空间开销将是最小的（引用数量翻倍）。

如果您使用值类型，则自平衡二叉搜索树将为您提供 O(log n) 中的查找和插入，但允许您仅存储每个元素的一个副本。

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在这里使用不正确。

队列或它的扩展将是你最好的选择。