lookup key by key in Java map or set-CodePudding

In most languages, including Java, there is an API something like java.util.Map which is designed to make it easy to loop up a value, given the key that maps to it. But there is not always a convenient way to look up the key, given the key (I'm pretty sure Python makes it hard, C makes it easy (just ask for an iterator), this question is about Java, which I suspect as as bad as Python). At first this may sound dumb: why would you need to look up a key you already have? But consider something like this (example below uses Set instead of Map, but same idea):

TreeSet<String> dictionary = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
dictionary.add("Monday"); // populate dictionary
String word = "MONDAY"; // user input, or something
if(dictionary.contains(word)) System.out.println(word   " already in dictionary");

The above code snippet will print MONDAY already in dictionary. This is of course wrong, because "MONDAY" is not in the dictionary; rather, "Monday" is. How can we make the message more accurate? In this case, we can make a help function that take advantage of the fact that a TreeSet is a NavigableSet (Actually a similar trick works for SortedSet, though it's a bit less convenient.):

String lookup(NavigableSet<String> set, String key) {
    assert set.contains(key) : key   " not in set";
    return set.floor(key);
}

Now we can fix the last line of the previous code snippet:

if(dictionary.contains(word)) System.out.println(lookup(word)   " already in dictionary");

Which will print the correct thing. But now let's try an example with a hash set:

import java.util.HashSet;
/** Maintains a set of strings; useful as a replacement for String.intern() */
class StringInterner {
    private final HashSet<String> set = new HashSet<>();
    /** use this instead of String.intern() */
    String intern(String s) {
         if(!set.contains(s)) {
             s.add(s);
             return s;
         }
         for(String str : set) // linear scan!!
             if(str.equals(s)) return str;
         throw new AssertionError("something went very wrong");
    }
}

The code above resorts to a linear scan to find something that it already knows is there. Note that HashSet could easily give us what we're looking for, because it needs to be able to do this just to implement contains(). But there's no API for it, so we can't even ask the question. (Actually, HashMap has an internal method called getNode which is pretty much what we want, but it is internal.) An easy workaround in this case is to use a map instead of a set: instead of set.add(s) we could instead use map.put(s,s). But what if we're already using a map, because we already have data we want to associate with our key? Then we can either use two maps, and carefully keep them in sync, or else store a tuple of size 2 as the "value" in our map, where the first item in the tuple is simply the map key. Both of these solutions seem needlessly awkward.

Is there a better way?

CodePudding user response：

Is there a better way?

No, there isn't.

For HashMaps, it doesn't matter, because your "two equivalent keys" argument doesn't make sense for HashMap. The two keys will always have to be equals, which as far as Java is concerned, means they should be substitutable in every way.