Searching for *the* key in a Java (Concurrent)HashMap

Question

Can I get a reference to the actual key in a (Concurrent)HashMap (or HashSet), by searching for a key which equals() it? How?

I'm looking for something like getEntry(K key).getKey() that will give me the same reference every time I access the key after the first insert, so I can use this reference instead of the freshly generated key to save memory.

(Clearly one can dedicate a special HashMap<K,K> just for this purpose, but I actually already have a map and was wondering if I can use its keys for this purpose)

Answer 1

You cannot retrieve the original key from a HashMap, without just doing a brute-force sequential search like this:

K keyToLookup = ...;

K originalKey = map.keySet().stream().filter(keyToLookup::equals).findAny().orElse(null);

---

Option 1: Embed key in value

Workaround for a HashMap is of course to have the key object as part of the value:

• By actually having the key object as part of the value object, which is often inherent, e.g. a map of user name to user object. May require modifying the value object, and may require removing and re-adding the map entry when it is updated to refer to a different value object.

• In a separate Map<K, K>. Less efficient, since you have to look up twice.

• By changing the value to a key/value pair, e.g. Map<K, Entry<K, V>>. This is likely the best solution, but does require care to ensure that the Entry's key object is always the original key.

---

Option 2: Use NavigableMap

If the Map can be changed from a HashMap to be a NavigableMap, e.g. a TreeMap, it supports retrieving the original key object from the map, e.g. using the ceilingEntry(K key)​ method.

The key object must implement Comparable or the TreeMap can use a custom Comparator. In either case, the implementation must be consistent with equals.

Not all key types can define a relative ordering, so it may not be possible to use NavigableMap.

K keyToLookup = ...;

Entry<K,​V> entry = map.ceilingEntry​(keyToLookup);
if (entry != null && entry.getKey().equals(keyToLookup)) {
    K originalKey = entry.getKey();
    V value = entry.getValue();
    // code here
} else {
    // key not found
}

Answer 2

It is rather strange to want to obtain the "original" of the key ...usually, polling with newly created keys is "cheap" and they can be garbage collected later. I guess you have a fairly exotic use case.

That said, you can't achieve what you want with a HashMap out of the box. The closest you could do is extend it to expose the getNode(...) method, allowing you to get access to the key.

Answer 3

You seem to be saying that you want a reference to the object held as a key in a map, to be found using another object that happens to be equal per the Object::equals contract.

While I’ve not yet tried this code, I think you can do this by getting a Set of the map’s keys. Then convert to a List. Find your desired object in that list, retrieving a reference from the list’s element.

Map< Car , Integer > map = … ;
Car car = new Car( … ) ;
map.put( car , 42 ) ;

Set< Car > carSet = map.keySet() ;
List< Car > carList = List.copyOf( carSet ) ;
Car similarCar = … ;
int index = carList.indexOf( similarCar ) ;
Car originalCar = carList.get( index ) ;  

boolean same = ( car == originalCar ) ;

You could also make a stream from the set of keys, searching for a match while having the stream halt on first match.