data-driven-docs

Selft training repo

Project maintained by ggranados Hosted on GitHub Pages — Theme by mattgraham

Map Interface

Table of Contents

Map Interface Characteristics

In Java, the Map interface is part of the Java Collections Framework and represents a collection of key-value pairs.

Each key in the Map is unique, and it is used to retrieve its corresponding value.

Some key characteristics of the Map interface include:

Back to top

Most Used Map Implementations

Java provides several implementations of the Map interface, each with different characteristics and use cases. Here are the most commonly used Map implementations:

Back to top

HashMap

Preferred for fast and unordered key-value mapping

Example:

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();

        // Adding key-value pairs to the HashMap
        hashMap.put("Apple", 1);
        hashMap.put("Banana", 2);
        hashMap.put("Orange", 3);
        hashMap.put("Grapes", 4);

        // Accessing the value associated with a key
        int value = hashMap.get("Apple");
        System.out.println("Value associated with 'Apple': " + value);

        // Updating the value associated with a key
        hashMap.put("Apple", 10);
        System.out.println("Updated value associated with 'Apple': " + hashMap.get("Apple"));

        // Size of the HashMap
        System.out.println("Size of the HashMap: " + hashMap.size());

        // Iterating through the HashMap using entrySet()
        System.out.println("Iterating through the HashMap:");
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Hashmap internally

Internally, a HashMap in Java is implemented as an array of Node objects (called the hash table) with a linked list or a balanced tree (starting from Java 8) to handle hash collisions. The Node class represents key-value pairs stored in the HashMap

Steps:

  1. Hashing the Key: When put a key-value pair into a HashMap, Java calculates the hash code of the key using the hashCode() method of the key object. The hash code is an integer value that determines the bucket in the hash table where the key-value pair will be stored.

  2. Index Calculation: To convert the hash code into a valid index in the hash table, Java applies the following computation: index = hashcode & (table.length - 1). The table.length represents the current size of the hash table, which is usually a power of two. The & operation with (table.length - 1) ensures that the index stays within the valid range of the array.

  3. Handling Collisions: If two different keys produce the same index after hashing, a collision occurs. To handle collisions, Java uses separate chaining: each bucket in the hash table can hold multiple Node objects (key-value pairs) forming a linked list or a balanced tree (in case of high collisions).

  4. Linked List or Balanced Tree: In older versions of Java, collisions are resolved using a linked list. In Java 8 and later, if a bucket’s linked list exceeds a certain threshold (TREEIFY_THRESHOLD, 8 by default), the linked list is transformed into a balanced tree (red-black tree) to improve lookup time in case of high collisions.

  5. Performance and Load Factor: The HashMap maintains a load factor, which represents the ratio of the number of key-value pairs to the number of buckets in the hash table. When the number of elements exceeds the load factor threshold (LOAD_FACTOR, 0.75 by default), the hash table is resized to accommodate more buckets and reduce the chance of collisions, thereby maintaining performance.

  6. Resizing: When resizing occurs, the number of buckets (array size) is doubled, and each key-value pair is rehashed to determine its new bucket in the resized hash table. This operation may be expensive, but it ensures that the HashMap remains efficient even with a large number of elements.

  7. Iterating through HashMap: Iterating through a HashMap can be done using an iterator or by using enhanced for-each loop through the entrySet(), keySet(), or values().

img.png

Keep in mind that the HashMap is not thread-safe. If you need a thread-safe version of HashMap, you can use ConcurrentHashMap, which provides better concurrency and performance in multi-threaded environments.

Back to top

Hash Collision

A hash collision occurs in a hash table or hash-based data structure when two different keys produce the same hash code or index in the underlying data storage. In other words, multiple keys are mapped to the same location in the hash table, even though they should ideally be stored in different locations.

Hash collisions can happen due to various reasons, including:

To handle hash collisions, data structures that rely on hashing typically use one of the following techniques:

Back to top

TreeMap

Suitable when the keys need to be sorted.

Example:

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> treeMap = new TreeMap<>();

        // Adding key-value pairs to the TreeMap
        treeMap.put("Apple", 1);
        treeMap.put("Banana", 2);
        treeMap.put("Orange", 3);
        treeMap.put("Grapes", 4);

        // Accessing the value associated with a key
        int value = treeMap.get("Apple");
        System.out.println("Value associated with 'Apple': " + value);

        // Updating the value associated with a key
        treeMap.put("Apple", 10);
        System.out.println("Updated value associated with 'Apple': " + treeMap.get("Apple"));

        // Size of the TreeMap
        System.out.println("Size of the TreeMap: " + treeMap.size());

        // Iterating through the TreeMap using entrySet()
        System.out.println("Iterating through the TreeMap:");
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Back to top

LinkedHashMap

Useful when you want to preserve the order of keys as they were inserted.

Example:

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapDemo {
public static void main(String[] args) {
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();

        // Adding key-value pairs to the LinkedHashMap
        linkedHashMap.put("Apple", 1);
        linkedHashMap.put("Banana", 2);
        linkedHashMap.put("Orange", 3);
        linkedHashMap.put("Grapes", 4);

        // Accessing the value associated with a key
        int value = linkedHashMap.get("Apple");
        System.out.println("Value associated with 'Apple': " + value);

        // Updating the value associated with a key
        linkedHashMap.put("Apple", 10);
        System.out.println("Updated value associated with 'Apple': " + linkedHashMap.get("Apple"));

        // Size of the LinkedHashMap
        System.out.println("Size of the LinkedHashMap: " + linkedHashMap.size());

        // Iterating through the LinkedHashMap using entrySet()
        System.out.println("Iterating through the LinkedHashMap:");
        for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Back to top

Choose the appropriate implementation

Choose the appropriate Map implementation based on your specific use case, considering the performance and ordering requirements of your application.

If you need fast operations and don’t care about the order, go with HashMap.

For sorted elements, TreeMap is a good choice.

If you need to maintain insertion order, LinkedHashMap fits the bill.

Back to top

Comparison Table

Characteristic HashMap TreeMap LinkedHashMap
Underlying Data Structure Hash Table Red-Black Tree Hash Table
Ordering No ordering Sorted according to keys Insertion order
Duplicates Allowed No No No
Null Elements Allowed Yes No Yes
Iteration Performance O(n) O(log n) O(n)
Use Cases General-purpose Map When keys need to be sorted When order of insertion is important

Back to top

Ref.

https://www.geeksforgeeks.org/map-interface-java-examples/?ref=lbp https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

Get Started | Languages | Java Development | Original Collections API | Updated Collections