O(1) method of getting K using V with a java hashmap?

In Java 8 is there an O(1) method of getting the K by using V for a hashmap? Would I have to use two hashmaps(KV and VK) and if so would that defeat the purpose of having O(1)?

For context, I am trying to find the most efficient way of getting (String userName, Integer userIdentifier) using either value or key.

3 answers

  • answered 2018-11-08 08:19 Mureinik

    As a general note - there's a hidden assumption here that the values are also unique. Otherwise, you won't be able to retrieve a single key by a value, but a list of keys, although even if you take that into consideration it won't change the answer much. Additionally, with your usecase of userName and userId, this may be a moot point altogether.

    As you alluded, a simple HashMap won't be enough - that would mean you'd need to iterate over the entries to find an entry with a specific key, which would be an O(n) operation.

    Using two HashMaps (name to id and id to name) is a good approach. While this would mean you'd have to perform two operations instead of one each time you add/remove/modify a user, it won't affect the order of magnitude (since you're still performing a constant number of constant-time operations), and you'll retain the O(1) insertion time.
    This is in fact a pretty common approach, and if you can introduce third-party libraries to your project, there are pretty solid implementations of this concept out there, like Apache Commons Collections' DualHashBidiMap.

  • answered 2018-11-08 08:22 Siddhesh Rane

    Maps are meant for searching by key, so you won't get O(1) lookup by value, unless you use a second map.

    What serves your use case is a BiMap avaliable from Google Guava

    BiMap<String, Integer> nameidmap = HashBiMap.create();
    Integer id = nameidmap.get("name");
    String name = nameidmap.inverse().get(12345);

    Internally Guava also maintains two hash tables, but it does the heavy lifting of keeping the two maps in sync. You can find full Javadoc for Bimap here.

  • answered 2018-11-08 09:23 Laxmikant

    If you want to use only single hashmap, you can do

    map.put(key, value) and then map.put(value, key)

    Assuming values are unique and also not equal to any key