HashMap - Notes By ShariqSP

HashMap in Java

HashMap is an implementation of the Map interface in Java that stores key-value pairs. It provides efficient retrieval and insertion operations, allowing fast access to elements based on their keys.

Definition:

A HashMap is a collection that stores key-value pairs in an unordered manner. It does not allow duplicate keys, but allows null values and one null key. Elements are stored based on the hash code of their keys, providing fast access to elements using their keys.

Methods:

put(K key, V value): Associates the specified value with the specified key in the map.
get(Object key): Returns the value associated with the specified key, or null if the key is not present in the map.
remove(Object key): Removes the mapping for the specified key from the map, if present.
containsKey(Object key): Returns true if the map contains a mapping for the specified key.
isEmpty(): Returns true if the map contains no key-value mappings.
size(): Returns the number of key-value mappings in the map.
clear(): Removes all key-value mappings from the map.

Example:


            import java.util.HashMap;
            
            public class Main {
                public static void main(String[] args) {
                    // Create a HashMap of strings
                    HashMap map = new HashMap<>();
            
                    // Add key-value pairs to the map
                    map.put("Java", 1);
                    map.put("Python", 2);
                    map.put("C++", 3);
            
                    // Display the map
                    System.out.println("Elements in the map:");
                    System.out.println(map);
            
                    // Remove a key-value pair
                    map.remove("Python");
            
                    // Display the modified map
                    System.out.println("\nElements after removal:");
                    System.out.println(map);
                }
            }

In this example, a HashMap is created to store key-value pairs of strings and integers. Key-value pairs are added to the map using the put() method, and a key-value pair is removed using the remove() method.

Difference between HashMap and HashTable in Java

HashMap and HashTable are both implementations of the Map interface in Java and provide key-value pair mappings. However, there are several differences between them:

Hashing in HashMap

Hashing is a fundamental concept used in HashMap to efficiently store and retrieve key-value pairs. In a HashMap, each key is associated with a unique hash code, which is computed using the hashCode() method of the key object. The hash code is then used to determine the index or bucket in the underlying array where the corresponding value should be stored.

Hash Function

The process of generating a hash code from a key object is performed by a hash function. The hash function takes the key object as input and produces a hash code, which is typically an integer value. The goal of a good hash function is to evenly distribute hash codes across the available range of indices or buckets in the HashMap's underlying array.

Collision Resolution

Since multiple keys can sometimes produce the same hash code (a phenomenon known as a collision), HashMap employs various techniques to handle collisions:

Chaining: In chaining, each bucket in the HashMap's array maintains a linked list of key-value pairs that hash to the same index. When a collision occurs, the new key-value pair is simply appended to the end of the linked list.
Open Addressing: In open addressing, when a collision occurs, the HashMap probes for an alternative empty bucket to store the key-value pair. This can be done using techniques like linear probing or quadratic probing.

Load Factor and Rehashing

The load factor of a HashMap is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the load factor exceeds a certain threshold, the HashMap is resized and rehashed to ensure efficient performance. This process is known as rehashing.

By default, the load factor of a HashMap is 0.75, meaning that the HashMap will be resized and rehashed when it is 75% full. Adjusting the load factor can affect the trade-off between space and time complexity.

Advantages and Disadvantages of HashMap in Java

Advantages:

Fast Access: HashMap provides constant-time performance for basic operations like get and put, making it efficient for large datasets.
Flexible Key-Value Pair Storage: HashMap allows storing key-value pairs of any data type, providing flexibility in usage.
Automatic Resizing: HashMap automatically increases its capacity and rehashes its elements when necessary, ensuring efficient performance even with dynamic datasets.
Iterating Over Elements: HashMap provides efficient ways to iterate over its elements, making it suitable for use in loops and iterations.
Null Values and Keys: HashMap allows storing null values and a single null key, providing flexibility in handling edge cases.

Disadvantages:

Not Thread-Safe: By default, HashMap is not synchronized and not thread-safe. Concurrent modifications can lead to unexpected behavior and data corruption in multi-threaded environments.
Performance Degradation with Collisions: If multiple keys produce the same hash code (collision), performance can degrade due to increased time spent on collision resolution, particularly with chaining.
Space Overhead: HashMap requires additional memory to store hash codes and maintain internal data structures, leading to a space overhead compared to simpler data structures like arrays or lists.
Ordering: HashMap does not guarantee any specific order of elements, which can be problematic if iteration order or sorting is required.

Feature	HashMap	HashTable
Null keys and values	Allows null keys and values	Does not allow null keys and values. Throws `NullPointerException`
Thread-safety	Not synchronized. Not thread-safe	Synchronized. Thread-safe
Performance	Generally faster as it's not synchronized	Slower due to synchronization overhead
Iterator	`Fail-fast` iterator	`Enumerator` interface used for iteration
Inheritance	HashMap is not a legacy class	HashTable is a legacy class

It's generally recommended to use HashMap over HashTable due to its better performance and flexibility, unless synchronization is explicitly required.

Interview Questions and MCQs on HashMap in Java

Interview Questions:

What is a HashMap in Java?
How does HashMap store key-value pairs internally?
What is the difference between HashMap and HashTable?
How do you add key-value pairs to a HashMap?
Can HashMap contain duplicate keys?
How do you retrieve a value associated with a key from a HashMap?
How do you remove a key-value pair from a HashMap?
Explain the concept of hashing in HashMap.
What is the significance of the initial capacity and load factor in HashMap?
What are the advantages and disadvantages of using HashMap?

Multiple Choice Questions (MCQs):

Which interface does HashMap implement?
a) List
b) Set
c) Map
d) Collection
Answer: c) Map
How are key-value pairs stored internally in a HashMap?
a) Based on their hash codes
b) Based on their indexes
c) In insertion order
d) In sorted order
Answer: a) Based on their hash codes
What happens when you try to add a key-value pair with a duplicate key to a HashMap?
a) The key-value pair is added without any changes
b) An exception is thrown
c) The existing value associated with the key is replaced with the new one
d) The new key-value pair is ignored
Answer: c) The existing value associated with the key is replaced with the new one
Which method is used to remove all key-value pairs from a HashMap?
a) removeAll()
b) clear()
c) deleteAll()
d) erase()
Answer: b) clear()
How do you check if a HashMap contains a specific key?
a) containsKey()
b) contains()
c) containsValue()
d) hasKey()
Answer: a) containsKey()