Java Map Data Structure Interface

Maps in Java are part of the java.util package and are used to store key-value pairs, where each key maps to exactly one value. They are widely used for fast lookups, inserting, and updating elements by their keys.

1. Overview of the Map Interface:

• The Map interface represents a collection of key-value pairs.

• Commonly used implementations include:

  • HashMap

  • LinkedHashMap

  • TreeMap

  • ConcurrentHashMap

2. Basic Operations on Maps:

• Adding Elements:

  • To add or update an element in a map, you use the put() method:

      Map<String, Integer> map = new HashMap<>();
      map.put("Alice", 25);  // Adds a key-value pair to the map
      map.put("Bob", 30);    // Adds another key-value pair
      map.put("Alice", 28);  // Updates the value for the key "Alice" to 28
    

• Retrieving Elements:

  • You can retrieve a value using the get() method by providing the key:

      int age = map.get("Alice");  // Retrieves the value associated with "Alice", which is 28
    

  • If the key does not exist in the map, get() returns null (or a default value in certain cases).

• Checking for Keys/Values:

  • Use containsKey() to check if a key exists:

      boolean hasAlice = map.containsKey("Alice");  // true
    

  • Use containsValue() to check if a specific value exists:

      boolean hasValue30 = map.containsValue(30);  // true
    

3. Important Map Implementations:

HashMap

• Underlying Structure: Uses a hash table for storing key-value pairs.

• Time Complexity: Average-case O(1) for adding, searching, and removing elements. This is due to efficient hash-based indexing.

• Ordering: Does not guarantee any specific order of keys or values.

• Hashing Mechanism:

  • When a key-value pair is added, the key's hashCode() is computed, and it determines the index (bucket) where the pair is stored.

  • If two keys have the same hash code, a collision occurs. Collisions are handled using linked lists or balanced trees (since Java 8) within each bucket.

LinkedHashMap

• Similar to HashMap, but maintains the insertion order of keys (or access order if configured).

• Useful when you need predictable iteration order.

TreeMap

• Underlying Structure: Uses a Red-Black Tree.

• Time Complexity: O(log n) for adding, searching, and removing elements.

• Ordering: Keeps keys sorted based on their natural order or a specified comparator.

• Useful when you need ordered key-value pairs.

4. Adding Elements to a HashMap:

• When you use put(key, value) in a HashMap:

  • The hashCode() of the key is computed to determine the bucket.

  • The key-value pair is added to the appropriate bucket.

  • If there’s already a pair with the same key, the old value is replaced with the new value.

5. Searching for Elements in a HashMap:

• To search for a key, get(key) is called.

• The hashCode() of the key is computed again, and it helps locate the bucket.

• The equals() method is used within the bucket to find the exact key (if collisions exist).

6. Example Demonstrating HashMap Behavior:

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
map.put("Alice", 28);  // Updates the value for "Alice" to 28

System.out.println(map.get("Alice"));  // Outputs: 28
System.out.println(map.containsKey("Bob"));  // Outputs: true
System.out.println(map.containsValue(25));  // Outputs: false (value was updated)

// Iterating over keys and values
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

7. Considerations for Using Maps:

• equals() and hashCode() Implementation: When using custom objects as keys, ensure they properly override equals() and hashCode() for correct behavior in HashMap and HashSet.

• Null Keys/Values:

  • HashMap allows one null key and multiple null values.

  • TreeMap does not allow null keys (it uses comparison logic that would throw NullPointerException).

Summary Table of Map Implementations:

more on equals() and hashcode(): https://hashnode.com/post/cm3yaoaky001b09mealgiemu2