java - 选择 Trie 还是 HashMap 存储词频列表？

Question

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

很好 345667
坏 456777
...

我需要使用 Java 中的 HashMap 或 Trie 数据结构来存储它。稍后我需要在没有其他操作的情况下从列表中查找单词。我的理解是，HashMap的查找比Trie慢，但是Trie会占用更多的内存，Trie的实现也费力，而HashMap已经可以使用了。对于生产代码，您对哪种数据结构最适合这种情况有什么意见或建议吗？提前致谢。

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

Answer 1

My understanding is that, the look up is slower for HashMap than Trie, but Trie will take up more memory usage

这是不正确的。假设一个好的散列函数，在 HashMap 中的查找将需要对主内存进行少量恒定数量的随机访问，而不管表的大小或其键的长度如何。相比之下，特里树需要为 key 中的每个字母访问主存储器。因此，trie 将导致更多的缓存未命中 - 缓存未命中将主导现代硬件的整体查找成本。

如果键很长并且共享许多公共(public)前缀，则 trie 可以节省内存。

trie 还支持前缀查询。

在你的例子中，键很短，你不需要前缀查询，所以你不会从 trie 中受益。