我需要存储一组元素。我需要的是功能
- 删除（单个）元素和
- 添加（组）元素和
- 每个对象应该只在集合中一次
- 从集合中获取随机元素
我选择了HashSet（C＃），因为它运动 快速 去除元素的方法（hashSet.remove（元件）），添加套装（hashSet.UnionWith（anotherHashSet）并且HashSet的性质保证不存在重复，因此需要处理要求1到3。
我发现获得随机元素的唯一方法是
Object object = hashSet.ElementAt(rnd.Next(hashSet.Count));
但这很慢，因为我为地图的每个像素调用一次（从多个起点创建随机洪水填充;此刻mapize 500x500但我想要更大）并且hashset包含相当多的项目。 （一项快速测试显示，在再次缩小之前，它会爆发5752个条目。）
分析（CPU采样）告诉我，我的ElementAt调用占用了50％以上。
我意识到在一个大的hashset上运行500x500并不是一件容易的事，但是其他操作（Remove和UnionWith）和ElementAt一样被调用，所以主要的问题似乎是操作而不是调用次数。
我模糊地理解为什么从HashSet中获取某个元素非常昂贵（与从列表或其他有序数据结构中获取它相比，但我只想要一个随机选择。 真的可以这么难，周围没有办法吗？ 是否有更好的数据结构用于我的目的？
将所有内容更改为列表并没有帮助，因为现在其他方法成为瓶颈而且需要更长时间。
将HashSet转换为数组并从那里选择我的随机元素预计无济于事，因为从数组中选择一个随机元素很快，首先将hashset转换为数组需要比运行hashSet.ElementAt更长的时间。
如果你想更好地理解我想要做的事情： 我的问题和答案的链接。
基本问题是索引。
在数组或列表中，数据由其coördinate索引 - 通常只是一个简单的int索引。在一个 HashSet，你自己选择索引 - 关键。然而，副作用是没有“coördinate” - 问题“索引3处的元素”真的没有意义。它实际实现的方式就是整体 HashSet 枚举，逐项后，并返回第n项。这意味着要获得第1000个项目，您必须在此之前枚举所有999个项目。这很伤人。
解决这个问题的最好方法是根据实际的密钥选择随机数 HashSet。当然，这只有在选择随机密钥时才有效。
如果您无法以令人满意的方式随机选择密钥，您可能希望保留两个单独的列表 - 每当您向a添加新项目时 HashSet，将其键添加到 List<TKey>;然后，您可以轻松地从中选择一个随机密钥 List，并遵循它。根据您的要求，重复可能不是什么大问题。
当然，你可以节省 ElementAt 枚举，如果你只进行一次枚举 - 例如，在搜索之前 HashSet，你可以把它转换成 List。这只有在您一次选择多个随机索引时才有意义（例如，如果您一次随机选择5个索引，您将节省 关于 平均1/5的时间） - 如果你总是选择一个，然后修改 HashSet 选择另一个，它不会有所帮助。
根据您的具体用例，可能值得一看 SortedSet。它的工作方式与此类似 HashSet，但它维持键中的顺序。有用的部分是你可以使用 GetViewBetween 获得一系列键的方法 - 如果键很稀疏，但在任意范围之间很好地平衡，你可以非常有效地使用它。你只需要随机选择一个范围，然后获取范围内的项目 GetViewBetween，并从中随机选择一个。实际上，这将允许您对搜索结果进行分区，并且应该节省相当多的时间。
我觉得 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 键和值虽然 - 没有通用版本。