Does Java have a HashMap with reverse lookup?

views:

1499

answers:

+10 Q:

Does Java have a HashMap with reverse lookup?

I have data that is organized in kind of a "key-key" format, rather than "key-value". It's like a HashMap, but I will need O(1) lookup in both directions. Is there a name for this type of data structure, and is anything like this included in Java's standard libraries? (or maybe Apache Commons?)

I could write my own class that basically uses two mirrored Maps, but I'd rather not reinvent the wheel (if this already exists but I'm just not searching for the right term).

+17 A:

There is no such class in the Java API. The Apache Commons class you want is going to be one of the implementations of BidiMap.

As a mathematician, I would call this kind of structure a bijection.

uckelman 2009-11-03 20:47:38

thanks, exactly what i was looking for!

Kip 2009-11-03 21:09:23

+20 A:

In addition to Apache Commons, Google Collections also has a BiMap.

ColinD 2009-11-03 20:54:54

thanks for the info! i'm sticking with apache for the time being though (unless there are some good reasons not to?)

Kip 2009-11-03 21:10:38

I can't offer a good comparison to apache collections, but google collections does have a lot of nice stuff that I think would make it worth looking in to.

ColinD 2009-11-03 21:25:06

One advantage of Google Collections is that it has generics whereas Commons Collections does not.

Mark 2009-11-03 21:38:12

@Mark: thanks, I didn't notice that. That is pretty significant...

Kip 2009-11-04 01:15:47

For comparison of the two libs, see the quotes in this answer: http://stackoverflow.com/questions/787446/is-there-a-java-1-5-equivalent-to-the-predicatet-methods-in-net/787459#787459 (and the original interview). That's biased towards Google, for obvious reasons, but even so I think it's safe to say you're better off with Google Collections nowadays.

Jonik 2009-11-05 18:21:59

+2 A:

If no collisions occur, you can always add both directions to the same HashMap :-)

rsp 2009-11-03 21:11:46

if it weren't for the smilie, i'd downvote you for that.... :)

Kip 2009-11-03 21:12:39

@Kip: Why? In some contexts this is a perfectly legitimate solution. So would be having two hash maps.

Software Monkey 2009-11-03 23:38:04

no, it's an ugly, fragile hack. it requires maintenance of the bi-directional property on every get() and put(), and it could be passed to other methods that modify the map without even knowing about the bi-directional property. maybe it'd be okay as a local variable inside a method that isn't passed anywhere, or if it was made unmodifiable immediately after creation. but even then, it's fragile (someone comes along and tweaks that function and breaks bidirectionality in a way that will not always immediately show itself to be a problem)

Kip 2009-11-04 01:22:44

@Kip, I agree that such a usage should be kept internal to the class using that map, but your last remark only holds true if the corresponding JUnit tests are sloppy :-)

rsp 2009-11-04 09:32:14

ansaurus

tags:

views:

answers:

Does Java have a HashMap with reverse lookup?

related questions