java – 选择Trie或HashMap来存储单词频率列表？
发布时间：2020-12-15 04:42:30 所属栏目：Java 来源：网络整理
导读：我有一个包含100万英文单词的txt文件,其频率格式如下： 好345667 坏456777 … 我需要使用Java中的HashMap或Trie数据结构来存储它.稍后我需要从列表中查找单词而不需要其他操作.我的理解是,HashMap的查找速度比Trie慢,但是Trie将占用更多的内存,而Trie的实现
|
我有一个包含100万英文单词的txt文件,其频率格式如下：
好345667 我需要使用Java中的HashMap或Trie数据结构来存储它.稍后我需要从列表中查找单词而不需要其他操作.我的理解是,HashMap的查找速度比Trie慢,但是Trie将占用更多的内存,而Trie的实现也需要付出努力,而HashMap已经可以使用了.对于生产代码,您对哪种数据结构最适合这种情况有什么建议或建议吗？提前致谢. 此外,HashMap允许查找“恒定时间”.它真的比英语单词的Trie慢吗？ 解决方法
这是不正确的.假设一个好的散列函数,HashMap中的查找将需要对主存储器的少量常量随机访问,而不管表的大小或其密钥的长度.相反,trie需要访问密钥中每个字母的主存储器.因此,trie将导致更多的缓存未命中 – 并且在缓存未命中将主导现代硬件上的整体查找成本. 如果密钥很长并且共享许多公共前缀,则trie可以节省内存. trie还支持前缀查询. 在您的情况下,密钥很短,并且您不需要前缀查询,因此您不会受益于trie. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |