2

我有一个本质上是键值对的数据结构。然而，与字典不同，我可能有重复的键，这在我正在设计的系统中是合法的。目前我有一个 Java 类，它实现了一个 Pair 对象（很像这里的例子A Java collection of value pairs? (tuples?)），它有一个左和一个右（键和值），然后我将它们存储在一个 ArrayList 中。

我想要的是一种以比 O(N) 更快的方式查找键的方法，因为列表可以变得非常大。

我曾考虑过可能创建一个倒排索引，但想知道是否还有其他方法？

为了处理重复项的减少，我真的只想根据键获取列表中的位置列表。

不必使用 Java - 这正是我将要实现的。

干杯

大卫

4

3 回答 3

8

我会使用 MultiMap 例如Guava 的Map<Key, List<Value>>MultiMap或Map<Key, Set<Value>>

这允许您对同一个键有多个值并且具有 O(1) 查找时间。

于 2012-08-13T10:59:00.583 回答
3

在我看来，由于您正在存储键/值，并且这些键可以是重复的，因此您确实需要一个MultiMap（我已链接到 Guava 版本，但存在其他版本）。

或者，您可以实现键映射到值列表。这有点费力，但将以非常相似的方式工作。

于 2012-08-13T10:59:37.643 回答
1

如果您询问多次存在的键的值，您应该得到什么？根据该问题的答案，Apache Commons MultiMap可能会解决您的问题。

于 2012-08-13T11:00:48.957 回答