快速搜索字典

我需要在数据结构中存储几百个字符串。每个字符串都有两个与它相关的字段，就像说出字的含义和它的起源一样。我可以以任何方式存储字，比如排序，反向排序或任何你喜欢的字。快速搜索字典

我只需要尽快搜索字典中的字符串并获取两个相关字段。如果可能的话，我希望我的搜索比二进制搜索更好。

我正在使用Java。我应该使用哪个data structure或Collection Class？

注意：我不想在此使用数据库。

来源

2012-09-24 OneMoreError

您寻找完全匹配或寻找类似于'foo'的东西也会返回'foobar'的条目吗？ – Stephan

嗯，我正在寻找完全相同的东西。但是，如果后者可以完成，我希望它.. – OneMoreError

您可以使用HashMap<String,MyDataObject> - 这将是最快和最简单的使用。

平均寻道时间是O(|S|)，其中|S|是字符串的长度。

您也可以尝试和使用trie或radix tree，但在开始使用该解决方案之前，请确保您想通过分析HashMap解决方案来给它时间。

来源

2012-09-24 08:07:46 amit

你是什么意思，他应该使用'HashSet '？它有一个'contains'方法，但不是'get'。他说他需要存储键值对。 – maba

@maba：你是对的，我想他也想检查一个Set是否适合存在。从第二次阅读 - 这肯定不是问题。编辑工作。 – amit

你应该实现接口 – ramsinb

使用HashTable或HashMap

您的结构应该是这个样子HashMap<String,Bookcontent>

其中BookContent是属性词的含义和由来类

来源

2012-09-24 08:08:43 premprakash

答案显然是“使用HashMap”，但这不是没有警告。您搜索的每个字符串都需要计算其哈希码。如果您每次使用新对象，则每次支付O（s是此例中的字符串长度），再加上另一个O（s）以检查equals。

解决这个问题的一个方法是用intern所有用于搜索的字符串。这将确保一次计算的哈希码被重复使用，并且还会使后续的检查短路。

另一种选择是使用trie。它的优点是您最多支付O（s），但通常较少—这是一个基于前缀的搜索，因此只要您遍历到前缀唯一的位置，就会得到结果。总之，如果您可以安排重复使用interned字符串，那么基于哈希码的解决方案是最佳选择;如果您可以安排重复使用interned字符串，如果不是的话，一个trie是一个很好的选择。

其他常见的选项将是一个跳过列表（在Lucene中使用）和B-tree（在数据库索引中通用）。

来源

2012-09-24 08:10:33

纠正我，如果我错了，但发现哈希匹配后应该仍然应用“equals（）”方法 - 除非存储的String和查找的String是*完全相同的对象*无论如何它都是'O（| S |）'。 – amit

@amit如果密钥被实施，那就会发生 - 将使用完全相同的对象。 –

我建议你使用Trie数据结构。我已经完成了一项类似于此的任务。此link可帮助您实施Trie DS。

来源

2012-09-24 08:11:25 Amarnath

快速搜索字典

回答

相关问题