快速从 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));

但这非常慢，因为我对地图的每个像素都调用一次它（从多个起始点创建随机泛洪;目前的地图大小为500x500，但我想扩大规模），并且哈希集保留了相当多的项。（快速测试表明，在缩小之前，它会增加到5752个条目。）

剖析（CPU采样）告诉我，我的ElementAt调用占据了50%以上。

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

我模糊地了解为什么从HashSet获取某个元素非常昂贵（与从列表或其他有序数据结构中获取相比，但我只想要随机选择。 它真的可以如此困难，并且没有其他方式吗？ 是否有更好的数据结构适合我的目的？

将所有内容更改为List也无济于事，因为现在其他方法成为瓶颈，所需时间更长。

将HashSet转换为数组并从中选择我的随机元素预期不会有所帮助，因为虽然从数组中选择随机元素很快，但是首先将哈希集转换为数组比单独运行hashSet.ElementAt更慢。

如果您想更好地了解我的尝试，请访问： 我的问题和答案的链接。

- Christian Geese

---

你要移除什么？只是随机找到的元素，还是任意的？ - spender

为什么不使用 HashSet 进行所有添加和删除操作，然后在需要随机获取像素之前，只需将其转换为 List<T> 即可？使用该 List<T>，然后在使用后丢弃即可。除非您需要同时添加、删除和获取随机元素... - Baldrick

@spender 我只删除了随机找到的元素。 - Christian Geese

@Baldrick 我恐怕是后者。循环基本上是这样的：选择一个随机单元格（哈希集包含所有可能的单元格，其中随机泛洪可以扩展到“边缘”）-> 填充它-> 查找相邻的空单元格并将它们添加到哈希集中-> 从哈希集中删除填充的单元格-> 再次循环直到哈希集为空。 - Christian Geese

我觉得一个二维链表在这里会对你有帮助。 - Enigmativity

相关：从HashSet中选择“任何”项非常缓慢 - 如何快速完成此操作？ - Theodor Zoulias

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>，可能更好。

- Matthew Watson

Answer 2

基本问题是索引。

在数组或列表中，数据由其坐标进行索引 - 通常只是简单的整数索引。在HashSet中，您自己选择索引 - 键。副作用是，没有“坐标” - “索引3处的元素”这个问题并不真实存在。它实际实现的方式是枚举整个HashSet，一项接一项地，然后返回第n项。这意味着要获取第1000个项目，您必须枚举之前的999个项目。这会影响效率。

解决这个问题最好的方法是基于HashSet的实际键来随机选择。当然，只有在可以合理地随机选择关键字时才有效。

如果无法以令人满意的方式随机选择关键字，则可能需要保留两个单独的列表 - 每当向HashSet添加新项目时，请将其键添加到List ; 然后，您可以轻松地从List中选择一个随机键，并跟踪它。根据您的要求，重复项可能并不是大问题。

当然，如果您只进行枚举一次 - 例如，在搜索HashSet之前，您可以将其转换为List，这可以节省ElementAt枚举的时间。通常，只有在一次选择多个随机索引时才有意义（例如，如果您一次选择5个随机索引，则平均可以节省约1/5的时间） - 如果您总是选择一个，然后修改HashSet并选择另一个，那么这不会有帮助。

根据您的实际用例，查看SortedSet也可能非常有价值。它的工作方式类似于HashSet，但它维护键的顺序。有用的部分是您可以使用GetViewBetween方法获取整个键范围 - 如果您的键是稀疏的，但在任意范围之间很好平衡，则可以有效地使用此功能。您只需首先随机选取一个范围，然后使用GetViewBetween获取范围内的项目，并从中随机选择一个。实际上，这将允许您对搜索结果进行分区，并应该节省相当多的时间。

- Luaan

---

是的，我在考虑使用列表和哈希集来进行索引。 - spender

@spender 如果你不关心清除垃圾，那么这可能会非常有效。但如果你关心的话，成本就会相当高。 - Luaan

我想随机选择的对象是网格中的单元格，因此很容易为它们提供唯一的ID（将x坐标转换为字符串+将y坐标转换为字符串？）。如果我想要“根据HashSet的实际键选择随机值”，那么我是否需要在Cell类中重写GetHashCode方法？ - Christian Geese

@ChristianGeese 你现在使用的是什么键？整个单元格吗？那是什么类型？ - Luaan

是的，整个单元格。不确定 "type" 意味着什么。它只是一个自定义类，保存了一些信息，没有继承。 - Christian Geese