C# 中最快、最高效的集合类型

Question

我正在构建一个应用程序，需要一个集合来容纳大约 10k 的字符串。

集合将用作队列。

因此，我们正在查看 C# 中的不同集合类型，但无法确定哪一种在队列中执行 Put 和 Get 操作的速度方面具有最佳性能。还应该能够不允许队列/集合中出现重复项。

根据评论进行编辑。

任何现有的收藏都会有所帮助。或者一个可以胜过任何现有集合的自定义集合也会很棒。

谢谢

Answer 1

如果您正在寻找高性能看跌期权和在检查唯一性（重复检查）时获取，但顺序并不重要（不是队列），然后使用HashSet

如果队列功能更重要，则使用 Queue

我认为没有任何东西可以同时提供这两者。

Answer 2

有 OrderedDictionary 类，它保留插入顺序，但允许您通过键查找值。

Answer 3

你介意花费 O(2n) 内存吗？您可以使用 Queue<>与字典<,>结合使用。队列将处理队列和出列操作，字典将确保唯一的条目。一个简单的包装类可以将这两者结合起来，它会给你 O(log n) 的队列和出队时间。

示例：

public class SetQueue<T>
{
    private readonly Dictionary<T, bool> duplicates = new Dictionary<T, bool>();
    private readonly Queue<T> queue = new Queue<T>();

    public bool Enqueue(T item)
    {
        if (!duplicates.ContainsKey(item))
        {
            duplicates[item] = true;

            queue.Enqueue(item);

            return true;
        }

        return false;
    }

    public T Dequeue()
    {
        if (queue.Count >0)
        {
            var item = queue.Dequeue();
            if (!duplicates.ContainsKey(item))
                throw new InvalidOperationException("The dictionary should have contained an item");
            else
                duplicates.Remove(item);

            return item;
        }

        throw new InvalidOperationException("Can't dequeue on an empty queue.");
    }
}

对此自定义数据结构的插入检查字典是否已包含该项目。此操作使用 ContainsKey 方法，该方法是一个 O(log n) 操作。如果该项目已包含在数据结构中，则该方法退出。如果不包含该项目，则该项目将被插入到队列中，这是一个常数 O(1) 操作。它也将被添加到词典中。当字典的数量小于容量时，这将接近一个常数，插入时间也为 O(1)。因此，总队列时间将为 O(log n)。

出队方法也是如此。

该解决方案与内置数据结构 OrderedDictionary 基本相同，但是，由于该解决方案使用泛型，因此其操作中的装箱/拆箱没有开销，从而使其速度更快。