1

问题：在计算文本文件中的n 个最常用词时，哪种数据结构更有效。哈希表或优先队列？

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

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

我的哈希表想法：因为在这里决定哈希表的大小有点不确定，所以我决定选择对我更有意义的方法：26。由于字母表中的字母数量。此外，使用良好的散列函数将是有效的。然而，在我看来，对链表（使用单独的链表进行勾结）和将其整数值增加 1 进行一次又一次的访问是没有效率的。

抱歉，这篇文章很长，但作为程序员，你会推荐哪一个。如果优先级队列你能简单地给我一些想法来将它与我的问题联系起来，如果哈希表可以做任何事情来提高它的效率吗？

4

2 回答 2

1

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

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

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

于 2012-04-21T00:44:59.083 回答
0

为什么不使用通用/通用字符串散列函数？毕竟你不想计算第一个字母，你想计算所有可能的单词。我会保持桶数动态。如果不是，您将需要进行大量的链表遍历。

于 2012-04-21T00:29:02.523 回答