Created Sunday 08 September 2013
A hash map is a datastructure that maps keys to values. The HashMap class is roughly equivalent to the HashTable class except that it is unsynchronized and permits nulls.
In Java, a hash map:
- is unsynchronized
- permits null keys and values
- does not guarantee the order of the map will remain constant over time.
What are the differences between Map, HashTable, HashMap, TreeMap, ConcurrentHashMap, LinkedHashMap?
- Map is an interface for a key-value map
- HashMap is a Map that uses a hash table for its implementation
- HashTable is a synchronized version of HashMap - it is very slow
- TreeMap uses a tree to implement a map
- ConcurrentHashMap allows for multiple threads to access it at the same time safely
- LinkedHashMap preserves the iteration order that things were inserted in (others don’t provide a fixed iteration order)
Keys
To use a class as a key, you must (correctly) implement #equals and #hashCode.
HashMap works by calling the key's #hashCode method. A HashCode need not always be unique. Keys with the same HashCode map to the same bucket. HashMap then uses the key's #equals method to find a match in the bucket. Obviously, if #equals doesn't work as expected, then HashMap may enter the same object twice in the hash map or get the wrong object.
See the HashMap source code.
Implementing #hashCode incorrectly degrades a HashMaps performance. HashMap ANDs a hash code with the hash map capacity to get the bucket to store the key/value pair. Obviously, if your #hashCode function always returns the same lower bits, then you will basically reduce the HashMap into a LinkedList --- #get then runs in linear time.