c# - C# HashSet 快速获取随机元素

Question

我需要存储一组元素。我需要的是功能

1. 删除(单个)元素和
2. 添加(组)元素和
3. 每个对象只能在集合中出现一次
4. 从集合中随机取一个元素

我选择了 HashSet (C#)，因为它采用快速方法来删除元素 (hashSet.remove(element))、添加集合 (hashSet.UnionWith) (anotherHashSet)) 并且 HashSet 的性质保证没有重复项，因此满足要求 1 到 3。

我发现获得随机元素的唯一方法是

Object object = hashSet.ElementAt(rnd.Next(hashSet.Count));

但这非常慢，因为我为 map 的每个像素调用一次(从多个起点创建随机洪水填充；目前 map 大小为 500x500，但我想更大)并且哈希集相当许多项目。 (快速测试显示它在再次收缩之前最多增加了 5752 个条目。)

分析(CPU 采样)告诉我，我的 ElementAt 调用占用了 50% 以上。

我意识到在一个大哈希集上进行 500x500 操作并不是一件容易的事，但其他操作(Remove 和 UnionWith)的调用频率与 ElementAt 一样，因此主要问题似乎是操作而不是调用次数。

我模糊地理解为什么从 HashSet 中获取某个元素非常昂贵(与从列表或其他有序数据结构中获取它相比，但我只是想要随机选择。真的这么难吗？有没有办法解决它？是否有更好的数据结构来满足我的目的？

将所有内容更改为列表无济于事，因为现在其他方法成为瓶颈并且需要更长的时间。

将 HashSet 转换为数组并从中选择我的随机元素预计不会有帮助，因为虽然从数组中选择随机元素很快，但首先将 hashset 转换为数组比运行 hashSet.ElementAt 花费的时间更长自己。

如果您想更好地理解我正在尝试做的事情:A link to my question and the answer.

Answer 1

我认为 OrderedDictionary 可能适合您的目的:

var dict = new OrderedDictionary();

dict.Add("My String Key", "My String");
dict.Add(12345, 54321);

Console.WriteLine(dict[0]); // Prints "My String"
Console.WriteLine(dict[1]); // Prints 54321

Console.WriteLine(dict["My String Key"]); // Prints "My String"
Console.WriteLine(dict[(object)12345]);   // Prints 54321 (note the need to cast!)

这具有快速添加和删除，以及 O(1) 索引。它只适用于 object不过键和值 - 没有通用版本。

[编辑] 许多年后:我们现在有了强类型泛型 SortedDictionary<TKey, TValue> 哪个可能更好。