HashMap • 17 min read

Key Concepts:

Hashing

• HashMap uses a hash function to map keys to their respective buckets.
• A good hash function generates a unique hash code for each key, but collisions can still occur. The hash map in Java does not maintain insertion order.

Performance

• HashMap provides constant-time performance (O(1)) for get() and put() operations.
• Performance can degrade to O(n) in the worst case, especially if there are many hash collisions.

Key and Value Types

• HashMap allows any non-null object as a key and any object (including null) as a value.
• For a class to be used as a key, it must implement the equals() and hashCode() methods.

Iteration:

• HashMap provides methods like keySet(), values(), and entrySet() for iterating over key-value pairs.
• The entrySet() method returns a Set view of key-value pairs, allowing iteration and modification.

Thread Safety

• HashMap is not thread-safe. For thread-safe operations, use ConcurrentHashMap.

HashMaps in Java - Pet Registry Example

public class Pet {
    private final String name;
    private final int age;
    private final String color;

    public Pet(String name, int age, String color) {
        this.name = name;
        this.age = age;
        this.color = color;
    }

    public String getName() {
        return this.name;
    }

    public int getAge() {
        return this.age;
    }

    public String getColor() {
        return this.color;
    }
}

public class PetsRegistry {
    private HashMap<String, Pet> petRegistry = new HashMap<>();

    public PetsRegistry() {
        // Add some pets to the registry
        petRegistry.put("Leo", new Pet("Lion", 8, "Gold"));
        petRegistry.put("Porky", new Pet("Pig", 3, "Pink"));
        petRegistry.put("Ro-Ro", new Pet("Robin", 7, "Red"));
        petRegistry.put("Midnight", new Pet("Cat", 10, "Black"));
        petRegistry.put("Hobbes", new Pet("Kitty", 1, "Calico"));
        petRegistry.put("Duke", new Pet("Dog", 14, "Brown"));
    }

    public Pet removePet(String name) {
        // Remove a pet by name
        return petRegistry.remove(name);
    }

    public void printRegistry() {
        // Iterate over the registry and print pet information
        for (String name : petRegistry.keySet()) {
            Pet pet = petRegistry.get(name);
            System.out.println(name + " is a " + pet.getColor() + " " + pet.getName() +
                    " and is " + pet.getAge() + " years old.");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Initialize the pet registry
        PetsRegistry petsRegistry = new PetsRegistry();
        petsRegistry.printRegistry();

        // Remove a pet
        String petNameToRemove = "Hobbes";
        Pet removedPet = petsRegistry.removePet(petNameToRemove);
        if (removedPet == null) {
            System.out.println(petNameToRemove + " not found");
        } else {
            System.out.println("Removed: " + petNameToRemove + ", " + removedPet);
        }

        // Print the updated registry
        petsRegistry.printRegistry();
    }
}
PetsRegistry.main(null)

Hobbes is a Calico Kitty and is 1 years old.
Leo is a Gold Lion and is 8 years old.
Porky is a Pink Pig and is 3 years old.
Ro-Ro is a Red Robin and is 7 years old.
Duke is a Brown Dog and is 14 years old.
Midnight is a Black Cat and is 10 years old.

Removed: Hobbes, REPL.$JShell$16E$Pet@63b16b54
Leo is a Gold Lion and is 8 years old.
Porky is a Pink Pig and is 3 years old.
Ro-Ro is a Red Robin and is 7 years old.
Duke is a Brown Dog and is 14 years old.
Midnight is a Black Cat and is 10 years old.

Example 2 - Student Registry

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

public class Student {
    private final int id;
    private final String name;
    private final int age;

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

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @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 &&
                age == student.age &&
                Objects.equals(name, student.name);
    }

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

public class StudentRegistry {
    private final Map<Integer, Student> studentMap = new HashMap<>();

    public StudentRegistry() {
        // Add some students to the registry
        studentMap.put(1, new Student(1, "Alice", 20));
        studentMap.put(2, new Student(2, "Bob", 22));
        studentMap.put(3, new Student(3, "Charlie", 21));
    }

    public Student getStudent(int studentId) {
        return studentMap.get(studentId);
    }

    public void printRegistry() {
        // Iterate over the registry and print student information
        for (Map.Entry<Integer, Student> entry : studentMap.entrySet()) {
            int id = entry.getKey();
            Student student = entry.getValue();
            System.out.println("Student ID: " + id + ", Name: " + student.getName() + ", Age: " + student.getAge());
        }
    }
}

// Instantiate and use the StudentRegistry class
StudentRegistry studentRegistry = new StudentRegistry();
studentRegistry.printRegistry();
 

Student ID: 1, Name: Alice, Age: 20
Student ID: 2, Name: Bob, Age: 22
Student ID: 3, Name: Charlie, Age: 21

Popcorn HACK 1

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

public class HashMapTest {
    public static void main(String[] args) {
        // Create a new HashMap with Integer keys and String values
        Map<Integer, String> myMap = new HashMap<>();

        // Add some key-value pairs to the HashMap
        myMap.put(1, "Apple");
        myMap.put(2, "Banana");
        myMap.put(3, "Cherry");

        // Fill in the blanks: Retrieve and print the value for key 2
        String valueForKey2 = myMap.get(___);
        System.out.println("Value for key 2: " + valueForKey2);

        // Fill in the blanks: Check if the HashMap contains key 4
        boolean containsKey4 = myMap.containsKey(___);
        System.out.println("Does the map contain key 4? " + containsKey4);

        // Fill in the blanks: Remove the entry with key 1 from the HashMap
        myMap.remove(___);

        // Print the updated contents of the HashMap
        System.out.println("Updated HashMap:");
        for (Map.Entry<Integer, String> entry : myMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

Popcorn HACK 2 - Quiz

Multiple Choice:

Question 1: Hashing in HashMap

What is the primary purpose of a hash function in a HashMap?

• A) To encrypt the keys
• B) To map keys to corresponding buckets
• C) To validate the keys
• D) To generate random numbers

Question 2: Performance of HashMap

What is the time complexity of the get() and put() operations in a well-distributed HashMap?

• A) O(log n)
• B) O(n)
• C) O(1)
• D) O(n^2)

Free Response:

Question 3: Key and Value Types in HashMap

Describe the types of objects that can be used as keys and values in a HashMap. Additionally, explain the methods that a class should implement if used as a key.

---

---

---

Question 4: Iteration in HashMap

Provide brief explanations for two methods in HashMap that can be used to iterate over its key-value pairs.

---

---

---

Question 5: Thread Safety in HashMap

Explain why HashMap is not thread-safe and what issues might arise when multiple threads access the same HashMap instance concurrently. Suggest an alternative class that can be used for concurrent access and explain its benefits.

---

---

---