Get key object out of a HashMap in Java

Question

I would like to retrieve the original object of a key in a HashMap in Java, what is the best way to do it?

For example

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
Integer keyObj = new Integer(10);
Integer valueObj = new Integer(100);
// And add maybe 1 million other key value pairs here
//... later in the code, if I want to retrieve the valueObj, given the value of a key to be 10
Integer retrievedValueObj = map.get(10);
//is there a way to retrieve the original keyObj object with value 10 from map?

Basically, the user can query any value of key here just for the key object, 10 is just an example. Some comment say, "you already have the x object, why do you want to get it?" Well, this is the same as saying "you already have the value object, why do you want to get it?" That is the purpose for the HashMap data structure, store and retrieval.

Retrieving a value object is easy but it seems no many people know how to retrieve the key object. It seems like many people don't get why I want to achieve the object of 10 and ask why? why not just value 10. This is just a greatly simplified model.

Well, let me give a little bit context. The keyObj is data in another data structure and I need the exact reference of this original key object. Say, there is a linked list of all the key values, and if I want to remove a particular node in the linked list.

I am not only interested in the value "10", but also the memory location, i.e. the reference in Java of that "10" object. There could be many "10"'s in memory. But that exact object is what I want to retrieve.

The iterator approach answer below give an O(n) approach. But what I am looking for is an O(1) retrieval of the key OBJECT given the key value.

One way I can think of is to store the key object in value as well, like

class KeyAndValue {
 public Integer key;
 public Integer value;
 public KeyAndValue(Integer key, Integer value) {
 this.key = key;
 this.value = value;
 }
}
map<Integer, keyAndValueL> map = new map<Integer, keyAndValueL>();
Integer x = new Integer(10);
map.add(x, new KeyAndValue(x, 100));
//then I can retrieve the reference of x, given value of key 10
Integer newKeyObj = map.get(10).key;

but this approach uses more memory and looks like a hack to me. I am wondering if there is a more elegant way in Java.

• Rahul: It really doesn't make any sense. Why would you want to get the key from the map, when you already know it?!
• musical_coder: Do you mean get all keys for a given value? Check out stackoverflow.com/questions/1383797/…
• Trying: may be you need map.keySet()
• Alfred Zhong: @musical_coder No, keys are unique in a HashMap. I try to just use standard Java library rather than 3rd party libraries...
• Cinnam: This is a perfectly valid question. You might have a key that is equal to the one used by the map, but it's not identical. Unfortunately the Map interface provides no way of obtaining the key reference in O(1). Unless you implement your own map or modify e.g. HashMap (subclassing won't help, since the method you need is package-private), I think the simplest way would be to store the key reference in the value, as you said.

Answer 1

A similar aproach but more generic is to store the "key + value" as an Entry instead of encapsule in another class. Example:

 Map<Integer, Entry<Integer, Integer>> map = new HashMap<Integer, Entry<Integer, Integer>>();
 Integer x = new Integer(10);
 map.put(x, new AbstractMap.SimpleEntry<Integer, Integer>(x, 100));
 //then I can retrieve the reference of x, given value of key 10
 Entry<Integer, Integer> keyObj = map.get(10);

Answer 2

try this

 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 Integer keyObj = new Integer(10);
 Integer valueObj = new Integer(100);
 map.put(keyObj, valueObj);
 Set<Integer> keys = map.keySet();
 Iterator<Integer> iterator = keys.iterator();
 while(iterator.hasNext()){
 Integer x = iterator.next();
 if(map.get(x) == 100)
 System.out.println("key is "+ x);
 }

• Alfred Zhong: This is O(n) algorithm, is there a O(1) approach?

Answer 3

You could store a key + value object "as the value" as you mention in your question.

Answer 4

What you are implementing is a variant of the flyweight pattern.

This is easiest implemented using a Map of every managed object to itself:

Map<T, T> cache = new HashMap<>();

And for every object you encounter:

T obj; // comes from somewhere
obj = cache.computeIfAbsent(obj, v -> obj); // reuse, or add to cache if not found

This has O(1) time complexity and uses only one extra object reference for each object so managed.