选择Trie树还是HashMap来存储单词频率列表？

Question

我有一个包含100万个英文单词及其频率的txt文件，格式如下：

good 345667
bad 456777
...

我需要使用Java中的HashMap或Trie数据结构来存储它。稍后我需要从列表中查找单词而不进行其他操作。我的理解是，对于HashMap，查找速度比Trie慢，但Trie将占用更多的内存使用量，并且实现Trie也需要付出努力，而HashMap已经可以直接使用。对于生产代码，您是否有任何建议或建议适合这种情况的数据结构？提前致谢。

此外，HashMap允许“常数时间”进行查找。对于英语单词，它真的比Trie慢吗？

- user697911

---

我的理解是，HashMap 的查找速度比 Trie 慢。你是从哪里得到这个结论的？ - Anirban Nag 'tintinmj'

参见维基百科，“在Trie中查找数据在最坏情况下更快”，“Trie也可以用来替换哈希表…” - user697911

@user697911，最坏情况不是常数哈希函数吗？这会导致查找的线性时间，因此最坏情况下查找肯定会更慢。 - William Morrison

我觉得这很有趣：https://github.com/jpountz/tries/wiki/Benchmark ... 就我所知，该项目包含了所有提到的实现，因此您可能希望使用您特定的数据进行基准测试（速度、内存）。 - qqilihq

很棒的基准数据。看起来 Trie 更节省空间，而 HashMap 最快。好好知道。谢谢。 - user697911

@user697911："但Trie会占用更多的内存使用量"，这真的取决于您的数据。如果您的许多字符串共享相同的前缀，则Trie将具有高效利用空间的优势。如果您的数据没有共享相同的前缀，则需要问一下它们在Trie中的作用是什么：） - TacticalCoder

Answer 1

我认为 HashMap 的查找速度比 Trie 慢，但 Trie 占用的内存更多，这种想法是错误的。如果假设哈希函数良好，HashMap 的查找将只需要少量恒定数量的随机访问主存，无论表的大小或其键的长度如何。相反，Trie 将需要对键中的每个字母进行一次主存访问。因此，Trie 将导致更多缓存未命中，而未命中将在现代硬件上支配整个查找成本。如果键长且共享许多公共前缀，则 Trie 可以节省内存。此外，Trie 还支持前缀查询。根据您的情况，由于键短且不需要前缀查询，因此您不会从 Trie 中获益。

- meriton

Answer 2

假设有一个好的哈希函数（String类肯定有这个），HashMap的查找时间将比Trie快。

从维基百科上可以看到：

在最坏的情况下，使用Trie查找数据速度更快，时间复杂度为O(m)（其中m是搜索字符串的长度），与不完美的哈希表相比。不完美的哈希表可能会发生键碰撞。键碰撞是哈希函数将不同的键映射到哈希表中相同位置的现象。在不完美的哈希表中，最坏情况下的查找速度是O(N)时间，但通常是O(1)，需要O(m)的时间来计算哈希值。

因此，如果哈希函数较差，HashMap中有许多碰撞，则速度会比Trie慢。然而，只有当您的键具有较差的哈希函数时才会出现这种情况。如果您使用String对象作为键，则不会出现这个问题。

Trie将节省您的内存。节省的内存量取决于您的数据组成方式。如果数据相似，则节省的内存将更大。如果数据不同，则节省的内存将较少。这是因为具有共同前缀的字符串共享前缀。

因此，如果内存足够，并且您有一个好的哈希函数，请使用HashMap。

否则，请使用Trie。

- William Morrison

---

由于词条数量较大（一百万），使用Trie树可能会节省一些空间，因为前缀是共享的。不过我并不确定哪一种更节省空间。 - user697911

需要注意的是，哈希表在理论上只有O（1）的时间复杂度。但是，在处理大型数据时，它开始出现问题。 - Hot Licks

Answer 3

如今，在服务器、台式机或笔记本电脑上，内存数据结构中存储100万条数据并不是一个很大的数字。但在手机或平板电脑上，这可能会变得困难。

实现一个高效的字典树并不是一件简单的事情，而且可能会导致性能和内存使用方面的问题。想象一下：在每个节点上，你都需要一个跳转表来分支到潜在的每个字符到子节点。你的潜在字符集是什么：所有Unicode字符、欧洲字符、ASCII字符、小写和大写字母，还是只有小写字母？你的答案越靠左，跳转表就会变得越大。即使只有a-z的小写字母，你也需要在每个节点中的跳转表中预留26个条目。速度要求在每个节点中保留26*4个字节。空间效率则倾向于以某种方式稀疏地存储表。在字典树的顶部，可能需要所有插槽，并且稀疏数组将浪费空间和时间。接近叶子节点时，越来越少的插槽需要指向子节点并保持为空，因此完整且快速的表将浪费空间。

Java的HashMap有相当长的历史，可能是可用的哈希映射的经过最好的测试、评论、批评和改进之一。对于你的要求，我会明确地从它开始，可能会对负载因子进行一些实验，只有当你因HashMap遇到严重的问题时，才会花时间投资于字典树。

- Harald

---

关于负载因子，由于已知条目数量为100万，因此最好将负载因子设置为1，容量=100万？ - user697911

loadFactor 关乎碰撞问题。当 HashMap 的容量为 2，loadFactor 为 1，HashMap 中只有一个元素时，你存储的第二个元素有 50% 的机会造成碰撞。 如果将 loadFactor 设置为 1/2-epsilon，则在存储第一个元素后，容量将增加到 4，并且存储第二个元素时发生碰撞的概率仅为 25%。 - Harald

我不确定你对碰撞的思考方式是否正确。默认的loadFactor = 0.75。这是否意味着在大多数HashMap使用中，会有很多碰撞？碰撞确实会发生，但是如果使用良好的哈希函数，这种情况是罕见的。理论上，足够好的哈希函数可以确保在loadFactor = 1的情况下不会发生任何碰撞。 - user697911

你的意思是当loadFactor=0.75且表已经填充了75%时，任何新键发生冲突的概率为75%吗？ - user697911

如果您使用二进制基数树，则“跳转表”始终只有2个条目，并且对于一般情况，任何节点中的跳转表只需要是该节点的“跨度”大小。但是Java不是实现Trie的最佳语言选择，因为节点的位操作很有用。 - Hot Licks

Answer 4

我想这里的关键词是“million”。对于这么多条目，哈希将开始遇到性能问题，而Trie保持其log(N)特性，即使机器开始频繁分页。Trie更适合基于磁盘的表格（具有缓存）。

但是实现高效（且可靠）的Trie相当困难。这不是胆小者可以解决的问题。

- Hot Licks