Java Hashmap In Action

Basics

Hashmap is a

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.)

Initial Capacity

This is a performance critical field for hashmap.

Load Factor

This is a performance critical field for hashmap.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

Performance

• Time complexity of Basic Operations i.e. GET and PUT is O(1).
• Time complexity of Iterations over hashmap is O("capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings)).

it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

Design Diagram

There is a note on fail fast behaviour of iterators, lets try to understand this.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

When hashmap dynamically grows and sink, what happens ?

Rehashing.

Reminders

• Avoid initializing hashmap with defaults, always define with right initial capacity.
• If your use case is concurrent access and multithreading then this implementation is not thread safe.
• There are no ordering gurantees in this implementation, Look for other implementations like TreeMap.
• Using many keys with the same hashCode() is a sure way to slow down performance of any hash table.
• The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.