Java HashMap

The Java HashMap Class

The HashMap class is the most common implementation of the Map interface. It stores data in (Key, Value) pairs, and you can access them by an index of another type (e.g. a String).

It uses a hash table to store the map. This allows the execution time of get() and put() to remain constant (O(1)) on average, regardless of the size of the map.

Key Characteristics of HashMap

• Key-Value Pairs: It stores items in key/value pairs.
• Unique Keys: Keys must be unique. If you try to insert a duplicate key, the old value will be replaced.
• Unordered: It makes no guarantees as to the iteration order of the map. The order may even change over time.
• Allows null: A HashMap can have one null key and multiple null values.
• Fast Performance: It offers constant time performance (O(1)) for get and put operations on average.

How HashMap Works

Similar to HashSet, a HashMap uses the key's hashCode() method to determine where to store the (Key, Value) entry. When you want to retrieve a value, it uses the key's hashCode() to quickly find the location, and then uses the key's equals() method to find the exact entry.

Important: If you use custom objects as keys in a HashMap, you must properly implement both the hashCode() and equals() methods in your key class.

When to Use HashMap

HashMap is the ideal choice when you need to map keys to values and:

1. You do not need the entries to be stored in any particular order.
2. You require the fastest possible performance for retrieving, adding, and removing entries.

It is the most frequently used Map implementation in Java.

HashMap Example

Here is an example demonstrating common operations on a HashMap.

import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    // Create a HashMap object called capitalCities
    HashMap<String, String> capitalCities = new HashMap<String, String>();
    // Add keys and values (Country, City)
    capitalCities.put("England", "London");
    capitalCities.put("Germany", "Berlin");
    capitalCities.put("Norway", "Oslo");
    capitalCities.put("USA", "Washington DC");
    System.out.println(capitalCities);
    // Access an item
    System.out.println("Capital of England: " + capitalCities.get("England"));
    // Remove an item
    capitalCities.remove("England");
    System.out.println("After removing England: " + capitalCities);
    // Get the size
    System.out.println("Size of the map: " + capitalCities.size());
    // Loop through a HashMap
    System.out.println("--- Looping through keys ---");
    for (String country : capitalCities.keySet()) {
      System.out.println("key: " + country + " value: " + capitalCities.get(country));
    }
  }
}

Advanced: Default Values with getOrDefault() (Java 8+)

A very common problem when reading from a map is handling cases where a key doesn't exist. Instead of writing if checks to prevent NullPointerExceptions, Java 8 introduced getOrDefault().

import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    HashMap<String, Integer> scores = new HashMap<>();
    scores.put("Alice", 85);
    // Bob doesn't exist in the map, so it returns the default value (0)
    int bobScore = scores.getOrDefault("Bob", 0);
    System.out.println("Bob's Score: " + bobScore); // Outputs 0
  }
}

Advanced: Hash Collisions (Java 8 Optimization)

A Hash Collision occurs when two completely different keys produce the exact same hashCode(), meaning they are assigned to the same "bucket" in the underlying hash table.

Historically, HashMap handled collisions by placing the entries in a linked list inside that bucket, which degrades performance to O(n) if many collisions occur.

Java 8 Optimization: To protect against this performance degradation (which could be exploited in Denial of Service attacks), Java 8 updated HashMap. When a single bucket accumulates too many collisions (specifically, 8 or more), the linked list is automatically converted into a balanced Red-Black Tree, restoring performance to O(log n) for those problematic buckets!