通用列表包含（）性能和替代品

Question

我需要存储大量键值对，其中键值不唯一。这两个键和值都是字符串。项目数约为 500 万。

我的目标是只持有唯一的对。

我尝试使用List<KeyValuePair<string, string>>，但Contains()速度非常慢。LINQAny()看起来有点快，但仍然太慢。

是否有任何替代方法可以在通用列表上更快地执行搜索？或者我应该使用另一个存储？

Answer 1

我会使用Dictionary<string, HashSet<string>>一个键映射到它的所有值。

这是一个完整的解决方案。首先，编写几个扩展方法以将一(key,value)对添加到您的Dictionary和另一个以获取所有(key,value)对。请注意，我使用任意类型的键和值，您可以string毫无问题地替换它。您甚至可以在其他地方编写这些方法而不是作为扩展，或者根本不使用方法而只在程序中的某处使用此代码。

public static class Program
{
  public static void Add<TKey, TValue>(
    this Dictionary<TKey, HashSet<TValue>> data, TKey key, TValue value)
  {
    HashSet<TValue> values = null;
    if (!data.TryGetValue(key, out values)) {
      // first time using this key? create a new HashSet 
      values = new HashSet<TValue>();
      data.Add(key, values);
    }
    values.Add(value);
  }
  public static IEnumerable<KeyValuePair<TKey, TValue>> KeyValuePairs<TKey, TValue>(
    this Dictionary<TKey, HashSet<TValue>> data)
  {
    return data.SelectMany(k => k.Value,
                           (k, v) => new KeyValuePair<TKey, TValue>(k.Key, v));
  }
}

现在您可以按如下方式使用它：

public static void Main(string[] args)
{
  Dictionary<string, HashSet<string>> data = new Dictionary<string, HashSet<string>>();
  data.Add("k1", "v1.1");
  data.Add("k1", "v1.2");
  data.Add("k1", "v1.1"); // already in, so nothing happens here
  data.Add("k2", "v2.1");

  foreach (var kv in data.KeyValuePairs())
     Console.WriteLine(kv.Key + " : " + kv.Value);
}

这将打印：

k1 : v1.1
k1 : v1.2
k2 : v2.1

如果您的键映射到 aList<string>那么您需要自己处理重复项。HashSet<string>已经为你做到了。