c# - 具有独特元素和快速添加和删除的数据结构

Question

我需要一个具有以下属性的数据结构:

• 结构中的每个元素都必须是唯一的。
• 添加:向数据结构添加一个元素，除非该元素已经存在存在。
• Pop:从数据结构中移除一个元素并返回该元素删除。删除哪个元素并不重要。

此结构不需要其他操作。带有列表的简单实现几乎需要 O(1) 时间用于 Pop 和 O(N) 时间用于 Add(因为必须检查整个列表以确保唯一性)。我目前正在使用红黑树来满足这种数据结构的需求，但我想知道我是否可以使用更简单的东西来实现几乎相同的性能。

我更喜欢用 C# 回答，但 Java、Javascript 和 C++ 也可以接受。

我的问题类似于this question ，但是我不需要查找或删除最大值或最小值(或者实际上任何特定类型的值)，所以我希望在这方面会有改进。但是，如果该问题中的任何结构适合此处，请告诉我。

那么，什么数据结构只允许唯一元素，支持快速添加和删除，并且比红黑树更简单？

Answer 1

内置的 HashSet<T> 怎么样？ ？

它只包含独特的元素。 Remove (pop) 是 O(1) 和 Add是 O(1) 除非必须调整内部数组的大小。