Most efficient key object type in a hash map?

Question

When using a HashMap, how much does the object type matter for element retrieval when it comes to speed? Say I use a loop to iterate through possible keys of a large hash map. What would be the most efficient key type I could use?

As of now I am using a String for the key object type due to simplicity for my sake. While coding, this question popped up in my head and struck my curiosity. I attempted searching this question online, but couldn't quite find the answer I was looking for. Thanks!

Answer 1

1. Key hashCode() and equals() should be fast

2. hashCode() should be well-distributed to minimize hash collisions

Answer 2

The hash map would ask your key for a hashCode(). If the time taken to generate a hash code is unreasonable, then insertion and retrieval times for such objects would be high. Take java.net.URL for example. It's hashcode method performs a DNS lookup. Such objects would not make good keys for a hash map.

There is no universal answer to which is the best key, since there is no best key. The best key for use in your hash map is one that you need for retrieval. Just make sure the key's hashCode() is quick and uses the int space appropriately.

Answer 3

What matters is the implementation of the equals and hashCode methods. See the following: What issues should be considered when overriding equals and hashCode in Java?

As these functions are utilized in hash operations, their efficiency comes into play when you operate on your collection.

As a sidenote, keep in mind the point made in the reference link:

Make sure that the hashCode() of the key objects that you put into the collection never changes while the object is in the collection. The bulletproof way to ensure this is to make your keys immutable, which has also other benefits.