What is hash map? - New Dev Point

A HashMap is a data structure in Java that implements the Map interface. It stores key-value pairs, where each key is associated with exactly one value. It is widely used when you need to efficiently retrieve, update, or delete elements based on a key. HashMap is part of the Java Collections Framework and provides constant-time complexity (on average) for basic operations like get, put, remove, and containsKey.

Key Characteristics of HashMap:

Key-Value Pairs: Each element in a HashMap is stored as a key-value pair (Map.Entry<K, V>).
No Duplicates in Keys: A HashMap cannot contain duplicate keys, but values can be duplicated.
Allows Null Values and Keys: HashMap allows one null key and multiple null values.
Unordered: The elements in a HashMap are unordered. The order of keys and values may change, as HashMap does not guarantee any specific order (e.g., insertion order).
Non-Synchronized: HashMap is not thread-safe, meaning it is not synchronized for use in a multi-threaded environment unless explicitly handled.
Efficiency: HashMap is highly efficient, with an average time complexity of O(1) for search, insert, and delete operations.

Internal Working of HashMap

HashMap uses a technique called hashing to store key-value pairs. Hashing converts an object (key) into a number called a hash code, which is then used as an index to place the key-value pair in the internal array.

The basic process of storing and retrieving data in HashMap works like this:

Hashing: The key’s hashCode() method is called to compute a hash value. The hash value determines where in the internal array the key-value pair should be placed.
Bucket: The internal array is divided into buckets, where each bucket can hold multiple entries. The hash value maps the key to a specific bucket.
Collision Handling: If two keys have the same hash value (a hash collision), the keys and their values are stored in the same bucket. HashMap uses a linked list or tree (since Java 8) within each bucket to handle collisions.

Basic HashMap Operations

Inserting Data (put):
- You can insert a key-value pair into the map using the put(K key, V value) method.
  
  HashMap<String, Integer> map = new HashMap<>(); map.put("Apple", 1); map.put("Banana", 2);
  
  1
  2
  3
  
  HashMap<String, Integer> map = new HashMap<>();
  map.put("Apple", 1);
  map.put("Banana", 2);
Retrieving Data (get):
- You can retrieve a value associated with a key using the get(K key) method.
  
  Integer value = map.get("Apple"); // returns 1
  
  1
  
  Integer value = map.get("Apple"); // returns 1
Removing Data (remove):
- You can remove a key-value pair by calling the remove(K key) method.
  
  map.remove("Apple"); // removes the key "Apple"
  
  1
  
  map.remove("Apple"); // removes the key "Apple"
Checking for Existence of Key (containsKey):
- You can check if a specific key exists in the HashMap using the containsKey(K key) method.
  
  boolean exists = map.containsKey("Banana"); // returns true
  
  1
  
  boolean exists = map.containsKey("Banana"); // returns true
Checking for Existence of Value (containsValue):
- You can check if a specific value exists in the HashMap using the containsValue(V value) method.
  
  boolean exists = map.containsValue(2); // returns true
  
  1
  
  boolean exists = map.containsValue(2); // returns true
Iteration:
- You can iterate over the keys, values, or key-value pairs using various methods.
  
  for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }
  
  1
  2
  3
  
  for (Map.Entry<String, Integer> entry : map.entrySet()) {
  System.out.println(entry.getKey() + ": " + entry.getValue());
  }

Example of Using HashMap:

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // Create a HashMap to store String keys and Integer values
        HashMap&lt;String, Integer&gt; map = new HashMap&lt;&gt;();

        // Adding elements to the HashMap
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Orange", 3);

        // Retrieving elements from the HashMap
        System.out.println("Apple value: " + map.get("Apple"));  // Output: 1

        // Checking if a key exists
        if (map.containsKey("Banana")) {
            System.out.println("Banana exists in the map");
        }

        // Iterating through the HashMap
        for (Map.Entry&lt;String, Integer&gt; entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }

        // Removing an element
        map.remove("Orange");

        // Displaying the HashMap after removal
        System.out.println("HashMap after removing Orange: " + map);
    }
}

import java.util.HashMap;

public class HashMapExample {

public static void main(String[] args) {

// Create a HashMap to store String keys and Integer values

HashMap<String, Integer> map = new HashMap<>();

// Adding elements to the HashMap

map.put("Apple", 1);

map.put("Banana", 2);

map.put("Orange", 3);

// Retrieving elements from the HashMap

System.out.println("Apple value: " + map.get("Apple")); // Output: 1

// Checking if a key exists

if (map.containsKey("Banana")) {

System.out.println("Banana exists in the map");

}

// Iterating through the HashMap

for (Map.Entry<String, Integer> entry : map.entrySet()) {

System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());

}

// Removing an element

map.remove("Orange");

// Displaying the HashMap after removal

System.out.println("HashMap after removing Orange: " + map);

}

Collision Handling in HashMap

HashMap uses a chaining mechanism to handle collisions. When multiple keys are mapped to the same bucket (due to the same hash code), they are stored in a linked list or tree structure within that bucket.

Since Java 8, when the number of elements in a bucket exceeds a certain threshold (usually 8), the internal structure of that bucket is transformed from a linked list to a red-black tree. This improves the time complexity for collision-heavy buckets from O(n) to O(log n).

HashMap Performance

Time Complexity:
- Best Case: O(1) for insertion, retrieval, and deletion (in the absence of collisions).
- Worst Case: O(n) if all keys hash to the same bucket and collisions are poorly handled, though this is rare due to proper hash distribution and the tree-based structure for collision management since Java 8.
Space Complexity: HashMap internally resizes its array (doubles its size) when the load factor exceeds a threshold (typically 0.75). The load factor controls how full the HashMap can get before resizing, ensuring good performance.

Common Use Cases of HashMap

Caching: Used to cache frequently accessed data, where key-value pairs are stored for quick retrieval.
Database Indexing: HashMaps are often used to index data by keys for fast lookups, like in-memory key-value stores.
Word Counting: HashMap is often used to count occurrences of words in documents (e.g., frequency counts).
Configuration Management: Store configurations with key-value pairs where quick lookup is needed.

Limitations of HashMap

Thread Safety: HashMap is not synchronized by default, meaning it is unsafe to use in multi-threaded environments without external synchronization. Use ConcurrentHashMap in multi-threaded contexts.
Unordered: HashMap does not maintain the order of insertion or any predictable order. For ordered maps, consider LinkedHashMap.
Memory Overhead: HashMap can have a significant memory overhead due to its need to maintain buckets and rehash when resizing.

HashMap vs Other Map Implementations

Feature	HashMap	LinkedHashMap	TreeMap
Order	No guaranteed order	Maintains insertion order	Sorted according to keys
Performance	O(1) average	O(1) average	O(log n) for all operations
Null Keys	Allows one `null` key	Allows one `null` key	Does not allow `null` keys
Thread Safety	Not thread-safe	Not thread-safe	Not thread-safe
Use Case	Best for general use cases	Best for ordered data	Best for sorted data

Conclusion

A HashMap is a powerful and efficient data structure in Java for storing and retrieving key-value pairs. It is highly efficient due to its use of hashing and is a go-to choice for many situations where quick lookups are needed. However, it’s important to consider its limitations, such as lack of thread safety and unpredictable order, and choose alternative implementations like ConcurrentHashMap, TreeMap, or LinkedHashMap when specific requirements like sorting or multi-threading are necessary.