rust - 如何快速查看HashSet中的任意值？

Question

当前，当我想从Hashset中获取任何值时，我可以通过以下方式进行操作:

my_set.iter().next().unwrap();

与first中的last或BTreeSet方法相比，它花费了很长时间，并且我的程序因此遭受了很大的痛苦。另外，出于性能原因，我不能使用BTreeSet，因为它会大大降低我的程序速度。

有什么方法可以比我正在使用的更快地从我的集合中获得的值吗？

Answer 1

最好的可能方法是保持哈希表的低加载因子，但代价是哈希冲突的风险较高。
另外，如果您了解哪些条目更可能具有某些值(value)，
维护这些条目的较小索引。
否则，这是不可能改善的。

以下内容描述了无法做到这一点的直观证明。

首先，让我们回顾一下HashSet的结构。 HashSet基于以哈希值为键的哈希表。下面以从维基百科获取的哈希表为例:

假设存在一种从哈希表中获取任意条目的有效算法。

考虑在示例中插入三个条目的情况，
然后调用remove("John Smith")和remove("Lisa Smith")。
现在，我们运行此假想算法并获得521-9655。这是怎么做的？
由于假设哈希值是均匀分布的，
尝试探测条目00、01，...的性能应与其他任何算法一样有效
假设没有其他信息是已知的。
然后我们看到最坏的情况，我们需要探测O(n)项(在此示例中为15个探测)以找到任意项。
请注意，此n是哈希表条目的数量，
通过哈希表加载因子与HashSet的大小线性相关
(或有史以来的最大大小，具体取决于删除太多项目时实现如何缩小和重建哈希表)。

因此，为了获得更快的算法，我们必须维护有关哈希表的其他信息
而不是原始的实现。
考虑一下我们索引可能插入条目的f(n)指针的情况。
该指数如何维护？
也许我们对insert()或remove()执行一些操作。
插入条目时更新索引可能很简单，
但是如果连续删除f(n)(我们的索引为空，
并且除非将窥视操作的成本转移到remove()操作上，否则我们将无法在索引中填充更多内容。
因此，如果我们从这些指针开始搜索，我们的虚构算法可以达到O(n/f(n))性能。
但是f(n)是什么？如果f(n)= O(n)，则除了HashSet之外，我们基本上还在维护一个新的集合，
这几乎抵消了使用HashSet的意义(在这种情况下，为什么不只使用BTreeSet呢？)，
因为我们基本上将搜索任意条目的成本转移到了插入/删除操作上。
如果f(n)= O(1)，则O(n/f(n))= O(n)，这意味着算法基本上没有改进。类似的论点适用于f(n)的其他变体。

总而言之，假设我们不知道什么更可能插入/删除
和哈希键是均匀分布的，
窥视任意值的性能必须为O(n)
否则会在一定程度上影响insert()/remove()的性能。

(该结论可能有用。一个简单的建议是，假设与搜索任意值相比，调用remove()的频率明显较低，以延迟计算结果)