Map Interface and Classes - Praful Vaishnav

Core Java

About Lesson

The Map interface in Java represents a collection of key-value pairs where each key is associated with exactly one value. Keys are unique within a Map, while values can be duplicated.

A Map can have null values but only one null key (in implementations that allow null keys).

Common Methods

V put(K key, V value): Associates the specified value with the specified key in the map. If the map previously contained a mapping for the key, the old value is replaced.

void putAll(Map<? extends K, ? extends V> m): Copies all of the mappings from the specified map to this map.

V get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

boolean containsKey(Object key): Returns true if this map contains a mapping for the specified key.

boolean containsValue(Object value): Returns true if this map maps one or more keys to the specified value.

V remove(Object key): Removes the mapping for the specified key from this map if present.

void clear(): Removes all mappings from this map.

int size(): Returns the number of key-value mappings in this map.

boolean isEmpty(): Returns true if this map contains no key-value mappings.

Set<K> keySet(): Returns a set view of the keys contained in this map.

Collection<V> values(): Returns a collection view of the values contained in this map.

Set<Map.Entry<K, V>> entrySet(): Returns a set view of the mappings contained in this map.

V getOrDefault(Object key, V defaultValue): Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

void replaceAll(BiFunction<? super K, ? super V, ? extends V> function): Replaces each entry’s value with the result of applying the given function to that entry.

Implementation Classes

HashMap: HashMap is implemented using a hash table. It does not maintain any order of the keys or values. The order can change over time. Allows one null key and multiple null values. Offers average O(1) time complexity for get and put operations. Not thread-safe. Concurrent modifications may lead to undefined behavior or exceptions (such as ConcurrentModificationException).
LinkedHashMap: LinkedHashMap extends HashMap and maintains a doubly-linked list across all entries. Maintains insertion order or access order, depending on the constructor used. Allows one null key and multiple null values. Similar performance characteristics to HashMap for basic operations, but slightly slower due to the overhead of maintaining the linked list. Iterating through a LinkedHashMap is faster than iterating through a HashMap of the same size.
TreeMap: TreeMap is implemented as a Red-Black tree, a self-balancing binary search tree. Maintains natural ordering (ascending) of keys or can be customized using a Comparator provided at construction time. Does not allow null keys. Allows multiple null values. Offers O(log n) time complexity for most operations, making it suitable for scenarios where keys need to be sorted.
ConcurrentHashMap: ConcurrentHashMap is implemented using a hash table similar to HashMap but with concurrency support i.e it is thread safe. Designed for high concurrency. Allows multiple threads to read from the map without blocking, and it supports a high level of concurrent updates.

HashTable

Hash table is defined as a data structure used to insert, look up, and remove key-value pairs quickly. It operates on the hashing concept where each key is translated by a hash function into a distinct index in an array. The index functions as a storage location for the matching value

Hashing is a process used to map data of arbitrary size to fixed-size values, typically integers, called hash codes. In the context of Java collections like HashMap, hashing is used to efficiently store and retrieve elements based on their keys.

A hash function is a mathematical function that takes an input (or key) and returns a fixed-size integer hash code. For a given input, a hash function always produces the same hash code.

In Java, the hashCode() method is used to generate hash codes for objects. This method is inherited from the Object class and should be overridden in custom classes to provide meaningful hash codes.

HashMap and HashSet: In these collections, hash codes are used to determine the bucket where elements are stored based on their keys. When retrieving an element, the hash code helps in quickly locating the bucket and then comparing the actual objects using equals() to handle potential collisions.

Hashing collision occurs when two different keys hash to the same index (or bucket) in a hash table or hash map. Hash codes are typically integers, but there are a limited number of possible hash codes compared to the potentially infinite number of objects. Most hash table implementations (like HashMap in Java) use chaining to handle collisions. Chaining involves storing multiple elements (with the same hash code) in the same bucket, typically as a linked list or a balanced tree in Java 8

HashMap

HashMap is implemented using a hash table data structure. Allows one null key and multiple null values.

HashMap uses a hash function to convert the key into an index within the underlying array (bucket). This index is used to store and retrieve the associated value. In case of hash collisions (two different keys hashing to the same index), HashMap uses chaining (linked list of entries) or in Java 8 and later versions, balanced trees (red-black trees) to store multiple entries in the same bucket.

To use a custom class as a key in HashMap, the class must override the equals() and hashCode() methods. These methods are used by HashMap to determine equality and calculate hash codes, respectively.

import java.util.*;

// Custom class for using as a key in HashMap
class Student {
    private String name;
    private int id;

    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }

    // Getters, setters, equals, and hashCode methods
    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", id=" + id +
                '}';
    }
}

public class HashMapExample {
    public static void main(String[] args) {
        // Creating a HashMap
        HashMap<String, Integer> map = new HashMap<>();

        // Adding entries
        map.put("Alice", 30);
        map.put("Bob", 25);
        map.put("Charlie", 40);
        System.out.println("HashMap after adding entries: " + map);

        // Getting and updating values
        int ageOfAlice = map.get("Alice");
        System.out.println("Age of Alice: " + ageOfAlice);

        // Checking if key exists
        boolean containsBob = map.containsKey("Bob");
        System.out.println("Does map contain key 'Bob'? " + containsBob);

        // Removing an entry
        map.remove("Charlie");
        System.out.println("HashMap after removing 'Charlie': " + map);

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

        // Clearing the map
        map.clear();
        System.out.println("HashMap after clearing: " + map);

        // Using custom class as key
        HashMap<Student, String> studentMap = new HashMap<>();
        Student s1 = new Student("Alice", 1001);
        Student s2 = new Student("Bob", 1002);

        studentMap.put(s1, "Math");
        studentMap.put(s2, "History");

        // Retrieving values using custom class keys
        System.out.println("Subject of Alice: " + studentMap.get(s1));
        System.out.println("Subject of Bob: " + studentMap.get(s2));
    }
}

LinkedHashMap

LinkedHashMap is implemented as a hash table with each entry in the LinkedHashMap maintains a bidirectional link to both the next and previous entries in the iteration order.

Maintains insertion order by default. This means when iterating through the map, the elements are returned in the order they were inserted. Optionally, LinkedHashMap can maintain access order (last accessed order), useful for implementing LRU (Least Recently Used) caches.

Iteration over entries is faster than iteration in HashMap due to the linked list maintaining order.

Not thread-safe by default. If concurrent access is needed, synchronization mechanisms must be implemented externally, such as using Collections.synchronizedMap()

To use a custom class as a key in LinkedHashMap, the class must override the equals() and hashCode() methods, just like in HashMap. These methods determine how equality and hashing are defined for instances of the class used as keys.

import java.util.*;

// Custom class for using as a key in LinkedHashMap
class Employee {
    private String name;
    private int id;

    public Employee(String name, int id) {
        this.name = name;
        this.id = id;
    }

    // Getters, setters, equals, and hashCode methods
    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return id == employee.id && Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", id=" + id +
                '}';
    }
}

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // Creating a LinkedHashMap with access order (last accessed order)
        LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);

        // Adding entries
        linkedHashMap.put("Alice", 30);
        linkedHashMap.put("Bob", 25);
        linkedHashMap.put("Charlie", 40);
        System.out.println("LinkedHashMap after adding entries: " + linkedHashMap);

        // Getting and updating values
        int ageOfAlice = linkedHashMap.get("Alice");
        System.out.println("Age of Alice: " + ageOfAlice);

        // Checking if key exists
        boolean containsBob = linkedHashMap.containsKey("Bob");
        System.out.println("Does linkedHashMap contain key 'Bob'? " + containsBob);

        // Removing an entry
        linkedHashMap.remove("Charlie");
        System.out.println("LinkedHashMap after removing 'Charlie': " + linkedHashMap);

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

        // Clearing the map
        linkedHashMap.clear();
        System.out.println("LinkedHashMap after clearing: " + linkedHashMap);

        // Using custom class as key
        LinkedHashMap<Employee, String> employeeMap = new LinkedHashMap<>();
        Employee e1 = new Employee("Alice", 1001);
        Employee e2 = new Employee("Bob", 1002);

        employeeMap.put(e1, "Engineering");
        employeeMap.put(e2, "Finance");

        // Retrieving values using custom class keys
        System.out.println("Department of Alice: " + employeeMap.get(e1));
        System.out.println("Department of Bob: " + employeeMap.get(e2));
    }
}

TreeMap

TreeMap is implemented as a Red-Black tree, a self-balancing binary search tree. Elements in TreeMap are stored in a sorted order based on the natural ordering of its keys or a custom Comparator provided at construction time.

Does not allow null keys. Allows multiple null values. Not thread-safe.

To use a custom class as a key in TreeMap, the class must implement the Comparable interface to define the natural ordering of its instances or a custom Comparator must be provided at TreeMap construction time. The compareTo() method (or the Comparator’s compare() method) determines how keys are compared and sorted.

import java.util.*;

// Custom class implementing Comparable interface
class Product implements Comparable<Product> {
    private String name;
    private double price;

    public Product(String name, double price) {
        this.name = name;
        this.price = price;
    }

    // Getters and setters
    public String getName() {
        return name;
    }

    public double getPrice() {
        return price;
    }

    // Implementing compareTo method for natural ordering
    @Override
    public int compareTo(Product other) {
        return Double.compare(this.price, other.price);
    }

    @Override
    public String toString() {
        return "Product{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

public class TreeMapExample {
    public static void main(String[] args) {
        // Creating a TreeMap with natural ordering (based on price)
        TreeMap<Product, Integer> treeMap = new TreeMap<>();

        // Adding entries
        treeMap.put(new Product("Laptop", 1200.0), 10);
        treeMap.put(new Product("Phone", 800.0), 20);
        treeMap.put(new Product("Tablet", 500.0), 15);
        System.out.println("TreeMap after adding entries: " + treeMap);

        // Getting and updating values
        Product laptop = new Product("Laptop", 1200.0);
        int quantityOfLaptop = treeMap.get(laptop);
        System.out.println("Quantity of Laptops: " + quantityOfLaptop);

        // Checking if key exists
        boolean containsTablet = treeMap.containsKey(new Product("Tablet", 500.0));
        System.out.println("Does treeMap contain Tablet? " + containsTablet);

        // Removing an entry
        treeMap.remove(new Product("Phone", 800.0));
        System.out.println("TreeMap after removing 'Phone': " + treeMap);

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

        // Clearing the map
        treeMap.clear();
        System.out.println("TreeMap after clearing: " + treeMap);
    }
}

ConcurrentHashMap

ConcurrentHashMap is implemented using a hash table data structure, similar to HashMap. It uses a technique called “lock striping” to achieve concurrency. Instead of a single lock for the entire data structure, ConcurrentHashMap divides the map into segments (default 16 segments in Java 8), and each segment is independently locked.

Allows multiple threads to read from the map concurrently, and a limited number of threads can modify it concurrently, based on the number of segments.

Does not allow null keys or values. Attempts to insert null keys or values will result in a NullPointerException.

Iteration over ConcurrentHashMap is weakly consistent. It reflects the state of the map at some point during the iteration but may not include all updates.

To use a custom class as a key in ConcurrentHashMap, the class must override the equals() and hashCode() methods, just like in HashMap.

import java.util.*;
import java.util.concurrent.*;

// Custom class for using as a key in ConcurrentHashMap
class Employee {
    private String name;
    private int id;

    public Employee(String name, int id) {
        this.name = name;
        this.id = id;
    }

    // Getters, setters, equals, and hashCode methods
    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return id == employee.id && Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", id=" + id +
                '}';
    }
}

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        // Creating a ConcurrentHashMap
        ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

        // Adding entries
        concurrentMap.put("Alice", 30);
        concurrentMap.put("Bob", 25);
        concurrentMap.put("Charlie", 40);
        System.out.println("ConcurrentHashMap after adding entries: " + concurrentMap);

        // Getting and updating values
        int ageOfAlice = concurrentMap.get("Alice");
        System.out.println("Age of Alice: " + ageOfAlice);

        // Checking if key exists
        boolean containsBob = concurrentMap.containsKey("Bob");
        System.out.println("Does concurrentMap contain key 'Bob'? " + containsBob);

        // Removing an entry
        concurrentMap.remove("Charlie");
        System.out.println("ConcurrentHashMap after removing 'Charlie': " + concurrentMap);

        // Iterating over entries
        System.out.println("Iterating over ConcurrentHashMap entries:");
        for (Map.Entry<String, Integer> entry : concurrentMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }

        // Clearing the map
        concurrentMap.clear();
        System.out.println("ConcurrentHashMap after clearing: " + concurrentMap);

        // Using custom class as key
        ConcurrentHashMap<Employee, String> employeeMap = new ConcurrentHashMap<>();
        Employee e1 = new Employee("Alice", 1001);
        Employee e2 = new Employee("Bob", 1002);

        employeeMap.put(e1, "Engineering");
        employeeMap.put(e2, "Finance");

        // Retrieving values using custom class keys
        System.out.println("Department of Alice: " + employeeMap.get(e1));
        System.out.println("Department of Bob: " + employeeMap.get(e2));
    }
}