通用列表包含（）性能和替代方案
我需要存储大量的键值，其中键不唯一。 键和值都是字符串。 物品数量约为500万。
我的目标是只保留唯一的对。
我试图使用List<KeyValuePair> ，但Contains()非常慢。 LINQ Any()看起来快一点，但仍然太慢。
是否有任何替代方法可以更快地在通用列表上执行搜索？ 或者也许我应该使用另一个存储？
我会使用Dictionary将一个键映射到它的所有值。
这是一个完整的解决方案。 首先，编写几个扩展方法，将一个(key,value)对添加到Dictionary ，另一个用于获取所有(key,value)对。 请注意，我使用任意类型的键和值，您可以用string替换它没有问题。 您甚至可以将这些方法写在其他地方而不是扩展名，或者根本不使用方法，只需在程序中的某处使用此代码即可。
public static class Program { public static void Add( this Dictionary> data, TKey key, TValue value) { HashSet values = null; if (!data.TryGetValue(key, out values)) { // first time using this key? create a new HashSet values = new HashSet (); data.Add(key, values); } values.Add(value); } public static IEnumerable> KeyValuePairs( this Dictionary> data) { return data.SelectMany(k => k.Value, (k, v) => new KeyValuePair(k.Key, v)); } }
现在您可以按如下方式使用它：
public static void Main(string[] args) { Dictionary> data = new Dictionary>(); 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
如果您的密钥映射到List那么您需要自己处理重复项。 HashSet已经为您做到了。
我猜那个Dictionary就可以了。
我会考虑在他们的网站上使用一些像RavenDB （在这种情况下是RavenDB Embedded）的进程内NoSQL数据库：
RavenDB可用于需要存储数百万条记录并具有快速查询时间的应用程序。
使用它不需要大的样板（来自RavenDB网站的例子）：
var myCompany = new Company { Name = "Hibernating Rhinos", Employees = { new Employee { Name = "Ayende Rahien" } }, Country = "Israel" }; // Store the company in our RavenDB server using (var session = documentStore.OpenSession()) { session.Store(myCompany); session.SaveChanges(); } // Create a new session, retrieve an entity, and change it a bit using (var session = documentStore.OpenSession()) { Company entity = session.Query() .Where(x => x.Country == "Israel") .FirstOrDefault(); // We can also load by ID: session.Load (companyId); entity.Name = "Another Company"; session.SaveChanges(); // will send the change to the database }
如果您使用HashSet您很可能会看到改进。
下面的测试在我的机器上完成大约10秒钟。 如果我改变……
var collection = new HashSet>();
…至…
var collection = new List>();
…我厌倦了等待它完成（超过几分钟）。
使用KeyValuePair的优点是，相等性由Key和Value 。 由于字符串是实例化的，而KeyValuePair是一个结构，因此运行时将认为具有相同Key和Value对是相等的。
您可以通过此测试看到相等：
var hs = new HashSet>(); hs.Add(new KeyValuePair("key", "value")); var b = hs.Contains(new KeyValuePair("key", "value")); Console.WriteLine(b);
但是，要记住的一件事是，对的相等性取决于字符串的内容。 如果由于某种原因，你的字符串没有被实现（因为它们来自文件或其他东西），那么相等可能不起作用。
using System; using System.Collections.Generic; using System.Diagnostics; namespace ConsoleApplication1 { internal class Program { static void Main(string[] args) { var key = default(string); var value = default(string); var collection = new HashSet>(); for (var i = 0; i < 5000000; i++) { if (key == null || i % 2 == 0) { key = "k" + i; } value = "v" + i; collection.Add(new KeyValuePair(key, value)); } var found = 0; var sw = new Stopwatch(); sw.Start(); for (var i = 0; i < 5000000; i++) { if (collection.Contains(new KeyValuePair("k" + i, "v" + i))) { found++; } } sw.Stop(); Console.WriteLine("Found " + found); Console.WriteLine(sw.Elapsed); Console.ReadLine(); } } }
你尝试过使用Hashset吗？ 虽然我不知道它是否仍然太慢，但比大数据涉及的列表要快得多。
这个答案有很多信息： HashSet vs. List性能
要创建一个唯一的列表，你要使用.Distinct()生成它，而不是.Contains() 。 但是无论什么类保持你的字符串必须正确实现.GetHashCode()和.Equals()以获得良好的性能，或者你必须传入自定义比较器。
以下是使用自定义比较器的方法
private static void Main(string[] args) { List> giantList = Populate(); var uniqueItems = giantList.Distinct(new MyStringEquater()).ToList(); } class MyStringEquater : IEqualityComparer> { //Choose which comparer you want based on if you want your comparisions to be case sensitive or not private static StringComparer comparer = StringComparer.OrdinalIgnoreCase; public bool Equals(KeyValuePair x, KeyValuePair y) { return comparer.Equals(x.Key, y.Key) && comparer.Equals(x.Value, y.Value); } public int GetHashCode(KeyValuePair obj) { unchecked { int x = 27; x = x*11 + comparer.GetHashCode(obj.Key); x = x*11 + comparer.GetHashCode(obj.Value); return x; } } }
另外，根据您在其他答案中的评论，您还可以在HashSet中使用上述比较器并让它以这种方式存储您的唯一项目。 您只需将比较器传入构造函数即可。
var hashSetWithComparer = new HashSet(new MyStringEquater());