Introduction

HashMap (also known as HashTable) is, a data structure that can map keys to values, used to implement an associative array. A HashMap uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in reality and usually some keys will hash to the same bucket. Instead, most HashMap designs assume that hash collisions — different keys that are assigned by the hash function to the same bucket — will occur and must be accommodated in some way.

In most of the situations, HashMap turns out to be more efficient than search tree or any other table lookup structure. For this reason, HashMap is widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches and sets.

Time Complexity of HashMap

What is Hashing?

The idea of hashing is to distribute the entries (key/value pairs) across an array of buckets or slots. Given a key, the algorithm computes an index that suggests where the entry can be found.

Hashing

Use hash value to group elements into slots, control by hash() method of HashMap.

Single LinkedList

• Each slot is a singly linked list, their key has the same hash value
• The slot index is controlled by indexFor() method of HashMap

In Java 8 or later version the LinkedList will be converted into Tree if the number of elements becomes more than 8 and Tree will be converted back to LinkedList if the number of elements reduces to under 6. You can read improvements in HashMap in Java 8.

More info on Collision resolution can be found at http://en.wikipedia.org/wiki/Hash_table 

Difference between HasMap and HashTable

Both HashMap and Hashtable implements Map interface but there are some significant differences between them and based on these differences we need to decide where to use HashMap or Hashtable in Java

1. HashMap and HashTable classes are equivalent but HashMap is non-synchronized whereas HashTable is synchronized. So HashTable is thread-safe and can be shared among multiple threads but HashMap cannot be shared among multiple threads without synchronization.
2. HashTable is having a thread-safety feature, so it’s much slower than HashMap in single threaded environment and it’s recommended that if there is only one thread is accessing the HashMap then we need to use HashMap because it out-performs HashTable in this scenario.
3. HashMap allows null values for both key and value but HashTable does not allow null values for key and value.
4. Another significant difference between HashMap and Hashtable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the Hashtable is not and throw ConcurrentModificationException if any other Thread modifies the map structurally by adding or removing any element except Iterator’s own remove() method. But this is not a guaranteed behavior and will be done by JVM on best effort.
5. HashMap does not guarantee that over the time the order of the map will remain constant whereas HashTable guarantees.

Working Principle of HashMap

HashMap works on principle of hashing, the HashMap class has put() and get() methods for storing and retrieving object from HashMap.

When you pass both key and value to put() method to store into HashMap, it uses key object hashcode() method to calculate hashcode and then by applying hashing on that hashcode it identifies bucket location for storing value object.

While retrieving it uses key object equals() method to find out correct key value pair and return value object associated with that key.

HashMap uses LinkedList in case of collision and object will be stored in next node of LinkedList.

HashMap stores both key/value pair in every node of linked list. Each node is of type Map.Entry.

HashMap will store values as long as different keys are used so if those different keys result in same hash value they will reside at the same index in the bucket, but in different nodes of the LinkedList.

Let’s look at the default put and get methods of HashMap in Java.

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int bucketIndex = (hash & (table.length-1));
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        return null;
    }
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        int bucketIndex = (hash & (table.length-1));
        for (Entry e = table[bucketIndex]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

Let’s analyze the code:

int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));

hashCode() method could be anything that ensures that hash value will be as unique as possible.

You can also implement your own HashMap with your own hash function.

Note that get() and put() have lot of code in common because before putting any key/value pair it checks if it already exists.

When you invoke get(key) method,  the key is hashed and then index of the bucket is calculated using this hash value.

The LinkedList at this index will be traversed till a ‘key’ with matching hash value and also being ‘equal’ to the input parameter.

Why Immutable Objects are needed for Keys

Immutable objects make best keys because this ensures that hash value will remain same when putting in the value and when retrieving it. String objects make the best keys in HasMap because of this reason; also they implement equals() and hashCode() methods.

That’s all about working principal of HashMap in Java.