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.
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
HashMapwon'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.
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.
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
BiMapavaliable 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.
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