Den*_* S. 15 java algorithm lookup dictionary data-structures
我遇到了几个问题和文章,说java中的字典实现最好用try.但就我所见,他们中的大多数都没有解决重要问题.那么,接下来是一个现实世界的任务:
让我们假设我需要使用java来实现一个字典(让我们说像Lingvo,但更简单).对于我的特定任务,需要存储单词定义并执行快速字典查找.
请解决下一个问题:
PS:代码示例受到高度赞赏.:)
提前感谢您的回答.
更新:如果我们在谈论Java中的标准DS实现,那么HashTable对于这个特定任务来说是最好的吗？为什么不使用HashMap,TreeMap或LinkedHashMap？
Kon*_*lph 16
我想在你的问题中只谈一点:
甲线索是不通用的字典的数据结构.原因是trie是(子)字符串搜索的专用搜索树.通常,您会对一般搜索树更感兴趣,例如二叉搜索树或B树.
所有这些实现都依赖于字典元素的排序,并且它们都具有对数平均情况和最差情况运行时的常见操作.
甲哈希表,相比之下,不要求中的元素的相对顺序.相反,它需要的元素是可哈希和平等相媲美.公共哈希表特征的最坏情况特征比树更差,即元素数量的线性.
但是,有点小心,哈希表操作的平均情况可以保持不变(即独立于容器大小).更重要的是,可以证明较慢的操作非常罕见.
在实践中,这意味着除了非常专业的用例外,哈希表击败了基于树的词典.
这样做的缺点是哈希表对其元素施加了任意看似的顺序.如果您有兴趣按排序顺序从字典中获取项目,则哈希表不适合您.
(还有其他有趣的字典实现,例如跳过列表,可以与搜索树和Bloom过滤器等概率实现相媲美.)
只有在处理字符串值字典时才能使用基于trie的实现,在这种情况下,它实际上通常是一个不错的选择,特别是如果字典中的许多字符串共享公共前缀并且相当短.