c++ - 高效频率计算的数据结构决策

Question

问题:在计算文本文件中 n 个最频繁出现的单词时，哪种数据结构更有效。 哈希表还是优先级队列？

我之前问过一个与这个主题相关的问题，但是在创造性的回答之后我感到困惑，我决定选择两种我实际上很容易实现的数据类型； 哈希表与优先级队列

优先级队列的困惑:老实说，我听过youtube上关于优先级队列的讲座，了解它的每一个组成部分，但是当谈到它的适用性时，我感到困惑。使用 二进制堆 我可以轻松实现优先级队列，但我的挑战是将其组件使用与频率问题相匹配。

我的哈希表想法:因为在这里决定哈希表的大小有点不确定，所以我决定采用对我来说更有意义的方法:26 .由于字母表中字母的数量。此外，具有良好的哈希函数将是高效的。然而，在我看来，为链接列表(使用单独链接进行串通)并再次将其整数值递增 1 并不是高效的。

抱歉发了这么长的帖子，但是作为程序员同行，您会推荐哪一个。如果是优先队列，你能简单地给我一些想法，将它与我的问题联系起来吗？

Answer 1

除了更有意义之外，哈希表是所提供的两种选择中速度更快的一种。而不是选择大小 26，如果你估计了唯一单词的总数(并且大多数人的专业术语之外的词汇量不会比 10,000 大很多 - 20,000 确实很大，而 30,000收集单词的爱好)，使尺寸足够大，以至于您不希望填满它，因此发生碰撞的可能性很低 - 不超过 25%。如果您想更保守一些，可以实现一个函数，将表的内容重新散列为原始大小两倍的表(并使大小为质数，因此大约只有原始大小的两倍)。

既然这是标记为 C++，您可能会问自己为什么不直接使用标准模板库中的多重集。它会记录您输入的每个单词的数量。

在任何一种情况下，您都需要进行单独的传递以找出哪些单词是最频繁出现的 n 个，因为您只有频率，而不是频率的排序。