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

Question

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

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

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

我更喜欢C#中的答案,但Java,Javascript和C++也是可以接受的.

我的问题类似于这个问题,但我没有必要查找或删除最大值或最小值(或实际上任何特定类型的值),所以我希望在这方面会有所改进.但是,如果该问题中的任何结构适用于此,请告诉我.

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

Answer 1

内置怎么样HashSet<T>？

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

Answer 2

正如Meta-Knight所说,HashSet是最快的数据结构.查找和删除需要持续O(1)时间(除非极少数情况下您的哈希很糟糕,然后您需要多次重新哈希或使用桶哈希集).对散列集的所有操作都需要O(1)时间,唯一的缺点是它需要更多内存,因为散列用作数组(或其他已分配的内存块)的索引.因此,除非你对内存非常严格,否则请使用HashSet.我只是解释你应该采用这种方法的原因,你应该接受Meta-Knights的答案,因为他是第一个.

使用散列是可以的,因为通常会覆盖HashCode()和Equals()函数.HashSet在内部执行的操作是生成哈希,然后如果它相等则检查相等性(仅在哈希冲突的情况下).如果它们不是,它必须调用一个方法来执行一个叫做rehashing的东西,它会产生一个新的哈希值,它通常与原始哈希值有一个奇数的素数偏移量(不确定.NET是否这样做,但其他语言是这样做的)并在必要时重复该过程.