HashMap: secret rooms, magic and collisions

Let's imagine a HashMap as a castle with secret rooms (buckets), where each room is preceded by magic doors - hash functions. How does this magical mechanism work and what happens when two magical entities collide in the same place? Let's dive into the secret world of HashMap. First, let's look at what a HashMap consists of.

Basic Components of a HashMap

table array: This array is the main data storage. Each array cell (or bucket) contains a unique index, where chains of values ​​or even a binary tree in the case of a large number of elements can be stored.

LoadFactor: LoadFactor specifies how much a HashMap can be filled before expanding it. The default load factor is 0.75, which strikes a balance between memory savings and access speed. When the HashMap is 75% full, it doubles the size of the table and redistributes the elements to maintain efficiency.

Threshold: Threshold is the point at which the HashMap decides to expand the table. Calculated as(capacity * loadFactor). For example, if capacity is 16 and loadFactor is 0.75, then threshold will be 12. When the HashMap reaches 12 elements, it increases its size.

The size keeps track of the current number of key-value pairs in the HashMap.

Each key-value pair in a HashMap is stored in a structure called a Node containing:

key - key of the pair,
value—the value of the pair,
hash - hash calculated based on the hashCode() key,
next - a link to the next element in the chain in case of collisions.

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

Each Node is connected to the next one in the same bucket upon collision, creating a linked list. These lists automatically turn into a balanced binary tree if more than eight elements accumulate in the bucket.

Hash Function: How Keys Find Their Rooms

Imagine that HashMap is a huge castle with many rooms. Each room has a unique number, but how do the keys decide which room to go to? This is the task of the hash function, a magical tool that helps determine which bucket (room) a particular key will be placed in.

When we add a key, the putVal method calls the hashCode() method of the key to create a hash, which is then refined to be distributed evenly across the buckets.
Index Calculation: Using the formula int index = hashCode & (length- 1) , HashMap calculates the index that points to the bucket in the table array.

Here hashCode is the unique code that the key receives through the hash function. We then perform a bitwise AND operation on length - 1. This is equivalent to calculating the remainder of the hash code divided by the number of buckets, and thus we determine the index in the bucket array.

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

As a result, each key passes through a hash function and ends up in its own unique room, the index of which is calculated using bitwise AND.

Collision check: If the bucket is empty, a new key-value pair is added. If not, putVal checks if the key matches:

Matches *—the value is updated.
*Does not match - a conflict arises - more about them further.

Collisions: Secret rooms that open into one another

What happens if two keys end up in the same room (several keys lead to one bucket)? In HashMap this is called a collision. This is when two keys have the same hash code and are trying to get into the same bucket. When is this possible? For example, we incorrectly overridden the hash code.

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

In this example, the KeyWithSameHash class has an overridden hashCode() method that returns the same value for all instances, causing all keys to end up in the same cell of the table array:

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

For all keys, the hashCode() value will be 42, so every time a key is added, the bucket index in the table will be the same.

But instead of bumping heads, the keys open additional doors, turning the room into a magical corridor that leads to new rooms. These new rooms are essentially ways to solve collisions.

Linked Lists: When two keys with the same hash codes end up in the same bucket, HashMap creates a linked list in that bucket. The keys continue to be stored in this list, and if necessary, a check is made using the equals() method to ensure that the keys are indeed the same.

Red-black trees: When the number of collisions in one bucket becomes too high (the corridor becomes too long), HashMap converts it to a red-black tree. This helps speed up searches and prevent slowdowns under heavy loads.

How equals() and hashCode() work

For HashMap magic to work correctly, it is important that two identical keys with the same value return the same hash codes, and are also compared correctly using the equals() method. It's like a spell that checks whether two objects are the same, even though they may be represented in different ways.

hashCode(): Each object must have its own unique hash code. This allows the HashMap to efficiently find the bucket where the key needs to be placed.
equals(): If two objects have the same hash code, the equals() method checks to see if the objects are actually the same.
If this check were not present, HashMap could confuse two different keys, which would lead to incorrect program behavior.

Conclusion

The world of HashMap is a world of magic where hash functions and collisions help keys find their rooms and keep the castle in order. Each key has its own path leading to a unique index, thanks to a hash function. And when two keys collide in the same bucket, the magic continues to work, opening new doors in the form of linked lists or red-black trees to find the right path.

So, thanks to hashCode(), equals() and magical collision corridors, HashMap continues to be one of the most powerful tools in a Java developer's arsenal, guaranteeing efficiency and accuracy even in the most confusing situations.

The above is the detailed content of HashMap: secret rooms, magic and collisions. For more information, please follow other related articles on the PHP Chinese website!