最高效的Java数据结构

假设我有串的大名单（约10000个）的三倍这样：最高效的Java数据结构

car noun yes 
dog noun no 
effect noun yes 
effect verb no

假设我提出了一个字符串双 - 例如，（效果，动词） - 我需要快速查看列表中的内容，看看这个对是否出现，如果是，它的值是yes还是no。（在这个例子中，double出现，值为“no”）。

什么是Java中用于存储列表和最有效的搜索方式的最佳数据结构？我正在运行数十万次这样的搜索，所以速度是至关重要的。

谢谢！

来源

2011-10-31 Andrew

您可能会考虑使用HashMap<YourDouble, String>。搜索将是O（1）。

您可以创建一个对象，YourDouble包含前两个值，或者将另一个附加到另一个 - 如果值仍然是唯一的 - 并使用HashMap<String, String>。

来源

2011-10-31 13:06:48

你好，你的意思是说，我应该连接前两个字符串，使关键？ – Andrew

我在说这可能是你的选择。如果您可以保证所产生的密钥仍然是唯一的。这真的取决于你的数据。使用String来代替只允许您避免创建YourDouble对象。 –

所有的答案都有帮助，并建议一个HashMap。我将使用HashMap 。 – Andrew

我会为您想要的每种搜索类型创建一个HashMultimap，例如， “全部三个”，“每一对”和“每个单一领域”。在生成列表时，填充所有不同的地图，然后可以从适合您查询的地图中获取。（缺点是你至少需要每个类型的类型，例如对于“单个字段”地图只使用字符串，而对于两场地图使用Pair，对于三维地图使用，野外地图。）

来源

2011-10-31 13:06:48

我只需要在第一对上进行搜索，所以我猜想带Pair的HashMap是最简单的解决方案。 – Andrew

你可以使用一个HashMap其中关键的是前两个字符串，您可以使用它进行查找的那些的串联，并且该值是一个布尔值，代表yes和no字符串。

或者，看起来第二列中的词会更少，因为它们代表类别。你可以有一个HashMap<String, HashMap<String, Boolean>>你第一次索引的地方。 “名词”，“动词”等，然后你通过例如“车”，“狗”，“效果”，以达到你的布尔值。这可能会更节省空间。

来源

2011-10-31 13:09:25 Vlad

为什么不简单地使用HashMap，其中包含两个第一个字符串并重新定义equals和hashCode（即Pair ）的键？这比连接和地图的地图好得多。 –

串联可能是一个糟糕的主意，你是对的。但是，如我所说，地图的地图可能会带来好处_if_，他在第二列中没有多少不同的字符串。 – Vlad

是的，第二列只有5种可能性 – Andrew

10k对我来说似乎并不大。你有没有试过数据库？

需要查找此类信息的地方是Semantic Web。许多项目仅适用于Triple Stores这种类型。在Triple Store页面底部有一个列表。

就Java而言，您的算法几乎肯定会与语言有关，如果您发现在C中实现了一个好的算法，那么它的Java端口也会很快。

另外，你的数据集是什么样的？是否有很多2个匹配，主语和动词经常是相同的？你期望得到多少火柴？ MapReduce可以在10k中找到一个匹配的情况下工作，但如果查询返回8k的10k查询不容易进行分区，那么它将无法正常工作。

还有一个针对这个问题的查询语言：SPARQL。 bigdata blog有一些很好的见解，虽然10k似乎并不大。

来源

2011-10-31 13:17:54

最高效的Java数据结构

回答

相关问题