aspose file tools*
The moose likes Java in General and the fly likes HashMap/Tree map question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "HashMap/Tree map question" Watch "HashMap/Tree map question" New topic
Author

HashMap/Tree map question

Misha Chitharanjan
Greenhorn

Joined: Aug 25, 2002
Posts: 2
I was wondering if there was a way to find out the key in a HashMap or TreeMap, given the value.
Basically, I need something that does the exact opposite of HashMap.get(). get() gets the value in the key-value pair, using the key as a parameter. I know the value, and need to find its key. Having looked at the API, I cannot see a way to do this.
If it's not possible, is there another class that could do this?
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
It can't be done with either of those data structures, and a data structure that did support it wouldn't be a dictionary/map anymore (what happens if you want two items with different keys to have the same value?).
That said, you could manually do a reverse lookup. Here's how it could be done:

This still doesn't address the problem of duplicate values though.
Another possibility would be to maintain two Maps. Everytime you add/change/delete the entry a->b in the first map, you then add/change/delete the entry b->a in the second map. Thus you get a reverse lookup by changing maps. Twice the memory, but probably better performance.
This one doesn't quite solve the duplicate value problem without some tweaking though -- before changing the value of a pre-existing entry, you have to delete its reverse mapping. Otherwise you could have keys pointing to values that are no longer pointing back at them. I have a feeling I don't sound coherent anymore.
(grrr. unwanted smilies. they're gone now)
[ August 25, 2002: Message edited by: David Weitzman ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
a data structure that did support it wouldn't be a dictionary/map anymore (what happens if you want two items with different keys to have the same value?).
I disagree. The duplicates problem can be solved by rejecting any map entry which adds a value which is already contained in the map. Nothing in the Map API disallows this; it's still a Map, with additional methods to get by value rather than key. This type of Map is generally called a double map - an example may be found here in the Jakarta Commons library. I assume it works; haven't tried it. You can modify the source code if you don't like their implementation.
If you need to allow duplicates, that's another matter, with a more complex solution, and I agree the solution would not be a Map as defined by its API. A get() would probably need to return a Collection of the matching entries. There are probably implementations out there already, but I'm not sure where offhand. For now I'll assume this isn't necessary.


"I'm not back." - Bill Harding, Twister
Misha Chitharanjan
Greenhorn

Joined: Aug 25, 2002
Posts: 2
Thanks!
The map doesn't have any duplicates, so that isn't an issue.
�gain, thanks for all your help.
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
I've never looked into Red-Black trees (as the jakarta implementation uses), but it looks like they might be interesting.... Wait a minute -- I still haven't bought an algorithms book. Shame on me. I'll do that as soon as I'm done posting.
I haven't studied the Collections API docs closely enough to notice, but IllegalArgumentException is indeed legal. Certainly I would find it offensive it a Map suddenly threw one without my permission. You would have to be careful about passing such a Map to code that wasn't aware of the contraints.
It looks like the Jakarta implementation doesn't let you put() with either a duplicate key or value. You would have to explicitly remove() first. Anyway, problem solved. Thanks for catching me Jim.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
You would have to be careful about passing such a Map to code that wasn't aware of the contraints.
True. This is true of the Map interface in general though, as well as many of the other collection interfaces. Most methods capable of modifying a Map or Collection are specified as throwing UnsupportedUpoerationExceptions, indicating that some implementations may not allow the given operation. This is intentional - it allows us to create immutable views of collections (e.g. with Collections.unmodifiableMap()) which still follow the base API. What it means though is that a method which accepts a Map parameter should either (a) allow for the possibility that some methods will throw an exception, or (b) document the fact that the method will work only for modifiable Maps, and programmers must be careful to use the method accordingly. Usually this is not a big problem, as I find that the methods where I want to modify a Map are often closely linked with the code that created the Map in the first place, so I know what kind of Map I'lve created. Other methods use only the read-type Map operations, and don't require any assumptions about the type of Map used. But in general you should be aware that certain methods may throw exceptions like this if you're not careful.
 
wood burning stoves
 
subject: HashMap/Tree map question