Internal Working of HashMap

Last Updated on December 28, 2023 by Ankit Kochar

HashMap is a fundamental data structure in Java and many other programming languages, widely used for storing and retrieving key-value pairs efficiently. It provides rapid access to elements based on their keys and is a part of the java.util package. Understanding the internal workings of HashMap is crucial for developers to leverage its functionalities effectively and optimize their code for performance. This article delves into the intricacies of HashMap’s internal mechanisms, shedding light on its underlying principles and operations.

What is HashMap?

A HashMap provides a way to store and retrieve key-value pairs in a way that is efficient and fast. An internal HashMap is also known as an open addressing or closed hashing. HashMap is a specific implementation of a HashMap that stores the key-value pairs directly within an array. In an internal HashMap, the key-value pairs are stored in an array called a hash table. The array is indexed using a hash function that converts each key into an index in the array. When a new key-value pair is added to the HashMap, the key is hashed to determine its index in the array. If there is already a key stored at that index, HashMap uses a collision resolution strategy to find an empty index to store the new key-value pair.

Collision Resolution Strategy

Collision resolution is the process of handling situations where two or more data items are mapped to the same hash value. A common collision resolution strategy is to use one of the following methods:

• Chaining: A collision resolution strategy in which each bucket in the hash table is a linked list, and collisions are resolved by adding the new item to the end of the list.
• Open addressing: A collision resolution strategy in which the hash table is treated as a linear array, and collisions are resolved by finding an empty slot in the array using one of several techniques, such as linear probing or quadratic probing.
• Robin Hood hashing: A variation of open addressing that tries to minimize the variance of the number of probes required to find an empty slot, by inserting the new item into the slot with the smallest distance from its original position.
• Cuckoo hashing: A collision resolution strategy that uses two or more hash functions to map each item to multiple locations in the hash table, and resolves collisions by moving the item to the next location according to the hash function until an empty slot is found, or by rehashing the table with new hash functions if all locations are occupied.

HashMap Internal Working

Here is a step-by-step explanation of how a hashmap works internally:

• When a key-value pair is inserted into the hashmap, the hashmap computes a hash code for the key using the hash function.
• The hash code is used to determine the index in the array where the key-value pair should be stored. The hash code is typically used to compute the remainder of the hash code divided by the size of the array, which ensures that the index is within the bounds of the array.
• If the index is already occupied by another key-value pair, a collision has occurred. There are different ways to handle collisions, but a common approach is to use a linked list or a similar data structure to store multiple key-value pairs at the same index.
• When retrieving a value based on a key, the hashmap computes the hash code for the key and uses it to find the index in the array where the value is stored.
• If the index contains a linked list or a similar data structure, the hashmap searches through the list to find the key-value pair with the matching key.
• If the key is not found, the hashmap returns null or throws an exception, depending on the implementation.
• To ensure efficient performance, the hashmap typically uses a load factor to determine when to resize the array. When the number of key-value pairs exceeds the product of the load factor and the size of the array, the hashmap creates a new, larger array and rehashes all the key-value pairs into the new array.

HashMap Internal Working Operations

The HashMap internal working of a can be described in the following:

• Hash Function: A hash function is a mathematical function that takes in an input and generates a fixed-size, unique hash value. The output is usually a string of characters that represents the input in a compressed and encrypted form. The purpose of a hash function is to provide a secure and efficient way to store and transmit data.

  Syntax of hash function:

  hash = hashfunc(key)
  index = hash % array_size

• Bucket: A bucket is a container used to store data in cloud storage services. In the context of a hashmap, a bucket is a collection of entries that share the same hash code.

  

  Syntax of bucket:

  import java.util.HashMap;
  HashMap map = new HashMap();

• Put operation: A put operation adds data to a data structure or an entry to a bucket in a hashmap.

  Syntax of put operation:

  String key = "my-key";
  String value = "my-value";
  map.put(key, value);

• Get operation:A get operation retrieves data from a data structure or an entry from a bucket in a hashmap.

Syntax of get operation:

    String key = "my-key";
    String value = map.get(key);

HashMap Internal Implementation

In this implementation, the HashMap class stores an array of Entry objects, where each Entry object represents a key-value pair. If two or more keys map to the same index in the array, a linked list of Entry objects is created at that index to handle collisions. The size field keeps track of the number of entries in the HashMap. The put method inserts a new key-value pair into the HashMap.

Example for Internal HashMap Implementation

import java.util.HashMap;
public class Example {
    public static void main(String[] args) {
        // Creating a new HashMap
        HashMap map = new HashMap();

        // Adding key-value pairs to the HashMap
        map.put("John", 30);
        map.put("Jane", 25);
        map.put("Bob", 35);
        map.put("Alice", 28);

        // Retrieving values from the HashMap
        int johnAge = map.get("John");
        int janeAge = map.get("Jane");
        int bobAge = map.get("Bob");
        int aliceAge = map.get("Alice");

        System.out.println("John's age: " + johnAge);       
        System.out.println("Jane's age: " + janeAge);   

        System.out.println("Bob's age: " + bobAge);      

        System.out.println("Alice's age: " + aliceAge);

    }
}

Output

John’s age: 25
Jane’s age: 25
Bob’s age: 35
Alice’s age: 28

Explanation for Internal Hashmap Implementation:
In this example, we create a new HashMap object and add four key-value pairs to it using the put method. The HashMap internally uses a hash function to map the keys to indices in an array. When retrieving values from the HashMap using the get method, the hash function is used again to locate the index of the value associated with the given key in the array.

Advantages of Internal HashMap:

Here are the advantages of internal HashMap in brief:

• Fast access to key-value pairs (O(1) time complexity).
• Efficient memory usage without the need for additional data structures.
• Simple implementation and maintenance.
• Customizable hash functions to optimize performance.

Disadvantages of Internal HashMap:

Here are the disadvantages of internal HashMap in small lines:

• Internal HashMaps don’t maintain the order of key-value pairs.
• Collisions can negatively impact performance.
• HashMaps can use significant memory resources as the number of key-value pairs grows.
• HashMaps are not thread-safe by default, which can cause data inconsistencies.

Conclusion:
In conclusion, the HashMap data structure is a vital component in the realm of software development due to its efficient key-value pair storage and retrieval mechanisms. By exploring its internal workings, developers gain insights into how HashMap manages collisions, handles resizing, and optimizes performance. Harnessing this knowledge empowers programmers to make informed decisions while utilizing HashMap in their applications, leading to more robust, scalable, and efficient code.

Frequently Asked Questions(FAQS) on HashMap:

Here are some FAQs related to HashMap.

1. How does HashMap handle collisions?
HashMap handles collisions by employing a technique called chaining. If multiple keys hash to the same index in the underlying array, elements with the same hash code are stored as a linked list at that index.

2. What happens when a HashMap is resized?
When the number of elements in a HashMap exceeds a certain threshold, the HashMap is resized to increase its capacity. This involves creating a new, larger array, rehashing existing elements, and redistributing them based on new hash codes.

3. What is the significance of the hash code in HashMap?
The hash code of keys determines the index at which the corresponding key-value pair will be stored in the underlying array. It helps optimize the retrieval process by narrowing down the search space.

4. How does HashMap ensure key uniqueness?
HashMap ensures key uniqueness by internally using the equals() method to compare keys. If two keys are equal according to the equals() method, only one key-value pair is stored in the HashMap.

5. Is HashMap thread-safe?
The standard HashMap implementation in Java (HashMap) is not thread-safe. For concurrent access, developers can use ConcurrentHashMap or synchronize access externally using constructs like Collections.synchronizedMap().

6. What is the time complexity of HashMap operations?
In the average case, the time complexity of basic operations like get() and put() in a HashMap is O(1). However, in the worst case (due to collisions), these operations can degrade to O(n).

7. Can we store null keys or values in a HashMap?
Yes, HashMap in Java allows both null keys and null values. There can be at most one null key and multiple null values stored in a HashMap.

8. How can I iterate through HashMap’s key-value pairs?
Developers can iterate through a HashMap’s key-value pairs using iterators, enhanced for loops, or forEach() methods available in Java, enabling access to keys and their corresponding values.