2

I have a data structure that is essentially key-value pairs. However unlike a dictionary I might have duplicate keys, this is legitimate in the system I'm designing. Currently I have a Java class that implements a Pair object (A lot like the example here A Java collection of value pairs? (tuples?)) which has a left and a right (key and value) I then store these in an ArrayList.

What I want is a means of looking up the keys in a fashion quicker that O(N) as the list can grow quite large.

I have thought about potentially creating an inverted index, however wondered whether there is another way?

To handle reduce of a duplicates I really just want to obtain a list of positions in the list based on the key.

Doesn't have to be in Java - thats just what I'll be implementing in.

Cheers

David

Community
  • 1
  • 1
David
  • 139
  • 1
  • 8
  • I forgot to mention that position of the items in the list of pairs is important as this refers to the position of something in another data structure. Does a MultiMap allow for this? – David Aug 13 '12 at 12:26
  • Answered my own question, a ListMultimap looks best. Thanks for the answers – David Aug 13 '12 at 12:27

3 Answers3

8

I would use a MultiMap e.g. Guava's MultiMap or Map<Key, List<Value>> or Map<Key, Set<Value>>

This allows you to have multiple values for the same key and has an O(1) lookup time.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
3

It sounds to me that since you're storing key/values, and those keys can be duplicates, you really need a MultiMap (I've linked to the Guava version, but others exist).

Alternatively you can implement a map of keys to lists of values. That's a little more laborious but will work in a very similar fashion.

Brian Agnew
  • 268,207
  • 37
  • 334
  • 440
1

What are you supposed to get if you ask for the value of a key that exists multiple times? Depending on the answer to that question Apache Commons MultiMap might solve your problem.

Jens Schauder
  • 77,657
  • 34
  • 181
  • 348