我需要在数据结构中存储几百个字符串。每个字符串都有两个与之关联的字段，比如说单词含义及其来源。我可以以任何方式存储单词，比如排序、反向排序或任何你喜欢的方式。
我只需要尽快在字典中搜索一个字符串并获取两个相关字段。如果可能的话，我希望我的搜索比二分搜索更好。
我正在使用 Java。我应该使用哪个data structure或Collection Class应该使用？
注意：我不想在此使用数据库。
问问题
1812 次
4 回答
6
您可以使用 a HashMap<String,MyDataObject>- 这将是最快和最简单的使用。
平均寻道时间是O(|S|)，其中|S|是字符串的长度。
您也可以尝试使用trie或radix tree，但请确保HashMap在开始研究解决方案之前通过分析解决方案来为它留出时间。
于 2012-09-24T08:07:46.577 回答
2
显而易见的答案是“使用 a HashMap”，但并非没有警告。您搜索的每个字符串都需要计算其哈希码。如果您每次都使用一个新对象，则每次都需要支付 O( s )（在这种情况下s是字符串长度），再加上另一个 O( s ) 进行equals检查。
解决此问题的一种方法是使用intern所有用于搜索的字符串。equals这将确保一次计算的哈希码被重用，并且还将使随后的检查短路。
另一种选择是使用trie。它的优点是你最多支付 O( s )，但通常更少——它是基于前缀的搜索，所以只要你遍历到你的前缀唯一的点，你就会得到结果。
总之，如果您可以安排interned字符串的重用，基于哈希码的解决方案是最佳的；如果不是，则trie是更好的选择。
其他常见的选项是跳过列表（在 Lucene 中使用）和 B-tree（在数据库索引中很常见）。
于 2012-09-24T08:10:33.877 回答
1
使用HashTable或HashMap
你的结构应该是这样的HashMap<String,Bookcontent>
whereBookContent是具有属性词含义和来源的类
于 2012-09-24T08:08:43.780 回答
1
我建议你使用Trie数据结构。我已经完成了与此类似的任务。此链接可帮助您实施 Trie DS。
于 2012-09-24T08:11:25.263 回答