如果我只需要快速查找键而值无关紧要，我应该使用 C# 字典吗？

Question

我需要一种能够插入条目然后能够快速确定是否已插入条目的数据类型。 Dictionary 似乎适合这种需要（参见示例）。但是，我对字典的values没有用。我还应该使用字典还是有其他更适合的数据类型？

public class Foo
{
    private Dictionary<string, bool> Entities;

    ...

    public void AddEntity(string bar)
    {
        if (!Entities.ContainsKey(bar))
        {
            // bool value true here has no use and is just a placeholder
            Entities.Add(bar, true);
        }
    }

    public string[] GetEntities()
    {
        return Entities.Keys.ToArray();
    }

}

Answer 1

您可以使用 HashSet<T>。

The HashSet<T> class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

Answer 2

is excellent, but for multi-threaded environments if you use a HashSet<T> then by consequence you have to use locks to protect access to it. I find myself more prone to creating deadlocks with lock statements. Also, locks yield a worse speedup per Amdahl's law 因为添加 lock 语句会降低实际并行代码的百分比。

出于这些原因，ConcurrentDictionary<T,object> fits the bill in multi-threaded environments. If you end up using one, then wrap it like you did in your question. Just new up objects to toss in as values as needed, since the values won't be important. ~~You can verify that there are no lock statements in its source code~~.

如果您不需要集合的可变性，那么这就没有实际意义了。但是你的问题暗示你确实需要它，因为你有一个 AddEntity 方法。

附加信息 2017-05-19 - 实际上，ConcurrentDictionary 在内部使用锁，虽然不是 lock 语句本身 ——它使用 Monitor.Enter（查看 TryAddInternal 方法）。但是，它似乎锁定了字典中的各个存储桶，这意味着与将整个内容放在 lock 语句中相比，争用更少。

总而言之，ConcurrentDictionary 通常更适合多线程环境。

仅使用 Interlocked 方法来创建并发哈希集实际上非常困难（不可能？）。我自己尝试并一直运行解决需要同时更改两件事的问题——通常只有锁定才能做到这一点。我发现的一种解决方法是对哈希桶使用单链表，并在一个线程需要在不受其他线程干扰的情况下对节点进行操作时有意在列表中创建循环；这会导致其他线程在同一位置旋转，直到该线程完成其节点并取消循环。当然，它在技术上没有使用锁，但它的扩展性不好。

如果我只需要快速查找键而值无关紧要，我应该使用 C# 字典吗？

Should I use a C# Dictionary if I only need fast lookup of keys, and values are irrelevant?

c#

lookup

dictionary