What is Hashing
This process involves transforming an object into an integer value, which is beneficial for indexing and facilitating quicker searches.
In essence, hashing is a method employed to distinguish a particular item from a collection of similar items.
What is HashMap
A fundamental component of the Java collection framework is the HashMap, which employs a method known as Hashing and adheres to the map interface. Data in a HashMap is stored in Key-Value pairs. Within a HashMap, data is organized in an array of nodes, where each node is embodied as a class. Internally, HashMap utilizes an array and the data structure LinkedList to store Key-Value pairs. HashMap comprises four distinct fields.
Before understanding the internal workings of HashMap, we must be aware of hashCode and equals methods.
- equals: It checks the equality of two objects. It compares the Key, whether they are equal or not. It is a method of the Object class. It can be overridden. If you override the equals method, then it is mandatory to override the hashCode method.
- hashCode: This is the method of the object class. It returns the memory reference of the object in integer form. The value received from the method is used as the bucket number. The bucket number is the address of the element inside the map. Hash code of null Key is 0.
- Buckets: Array of the node is called buckets. Each node has a data structure like a LinkedList. More than one node can share the same bucket. It may be different in capacity.
Hash Function
In the context of hashing, a hash function takes an input (or key) and produces a predetermined-length string or number, typically referred to as a hash code. This hash code is then utilized to access specific entries in a hash table, akin to how arrays work in HashMap. The main objective of a hash function is to reduce collisions and uniformly distribute inputs across the hash table.
Insert Key, Value Pair in HashMap
The insertion of a Key-Value pair into a HashMap is achieved using the put method. By default, a HashMap has a size of 16, ranging from 0 to 15.
Example
In this instance, we aim to add three pairs of (Key, Value) into the HashMap.
HashMap<string , integer> map = new HashMap<>();
map.put("Aman", 19);
map.put("Sunny", 29);
map.put("Ritesh", 39);
</string>
Let's determine the index at which the key-value pair will be stored in the Hash Map. Upon invoking the put function, it computes the hash code of the Key "Aman". Assuming the hash code of "Aman" is 2657860. In order to store the Key in memory, the index needs to be calculated.
Calculating Index
The index serves to reduce the array's size. The calculation formula for determining the index is as follows:
Index = hashcode(Key) & (n-1)
Considering the size of the array as n, the index value for the element "Aman" would be:
Index = 2657860 & (16-1) = 4
The index value 4 is determined through computation for storing the Key and value in a HashMap.
Hash Collision
In situations where two or more Keys result in the same calculated index value, we encounter a collision. To illustrate this, let's consider the Key "Sunny" and determine its hash code as 63281940. When storing this Key in memory, we must determine its index using the prescribed formula.
Index=63281940 & (16-1) = 4
The index value 4 is determined as the position where the Key will be placed within the HashMap. The equals method is utilized to compare if both Keys are identical. If the Keys match, the current value replaces the existing value. Otherwise, the new node object is linked to the previous node object through a LinkedList. As a result, both Keys are stored at index 4 in the HashMap.
In the same manner, let's store the Key "Ritesh." Assuming the hash code for this Key is 2349873, it will be placed at index 1 in the storage.
Handling Collisions
Although attempts are made to reduce collisions, they are bound to happen. There are two primary approaches to managing collisions:
- Chaining: This involves saving all items that are hashed to the same location in a linked list or tree.
- Open Addressing: This method entails locating another available space within the hash table by probing, such as through techniques like linear probing or quadratic probing, in the event of a collision.
HashMap.get Method
The get function retrieves a value based on its corresponding Key. It will not return a value if the Key is unknown. Upon invoking the get(K Key) function, it computes the hash code of the provided Key.
Assuming we need to retrieve the Key "Aman," the method below will be invoked.
map.get(new Key("Aman"));
The hash code produced is 2657860. Next, we determine the index value of 2657860 by applying the index formula, resulting in an index value of 4, as determined earlier. The functionality of the get method involves searching for the index value 4. It begins by comparing the initial Key element with the provided Key. Should the keys match, the corresponding value is returned; if not, the search continues to the subsequent element in the node, if available. In this specific case, the first element of the node matches, and consequently, the value 19 is returned.
Let's fetch another Key "Sunny."
The hash code generated for the Key "Sunny" is 63281940, resulting in an index value of 4 when using the put method. Proceed to the 4th index of the array and verify if the Key matches the first element's Key. The comparison also extends to Keys. In this instance, the specified Key corresponds to the second element, with the subsequent node being null. The comparison is made between the Key of the second element and the specified Key, resulting in a value of 29. If the next node is null, a null value is returned.
HashMap Traversal
In Java, there are different methods available like entrySet, keySet, and values that can be used to iterate through a hash map. These methods enable the iteration over the keys, values, or key-value pairs stored in the HashMap. Let's examine the code example below.
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
Rehashing and Load Factor
In order to sustain optimal performance, a HashMap undergoes resizing, known as rehashing, when the quantity of elements expands significantly. This process is determined by the load factor, which indicates how full the hash table can become before its size is automatically increased.
- Load Factor: The default load factor for a HashMap is set at 0.75. This signifies that when the hash table reaches 75% capacity, it will undergo a resizing operation by doubling its current capacity.
- Rehashing: During the rehashing process, a new and larger array is generated, and all existing entries are recalculated to new positions in the array. This procedure guarantees that the hash table maintains an optimal equilibrium between time and space complexity.
Advantages and Disadvantages of HashMap
Advantages
- Fast Access: Offers average O(1) time complexity for put and get operations.
- Flexibility: Can store null keys and values.
- Non-synchronized: Higher performance due to lack of synchronization overhead (but not thread-safe).
Disadvantages
- Non-synchronized: Not thread-safe, requiring manual synchronization if used in a multi-threaded environment.
- Memory Overhead: Can consume significant memory due to its internal structure.
- Unordered: Does not maintain any order of its keys or values.
Conclusion
The HashMap in Java is a widely used and adaptable data structure known for its efficient storage and retrieval through hashing. Understanding its internal mechanisms such as traversal techniques, collision management, rehashing, and hash functions is essential for leveraging its capabilities effectively.
While HashMap offers great efficiency for most tasks, developers should be mindful of its limitations such as memory consumption and absence of thread safety. By following best practices and considering the specific needs of your application, you can maximize performance and functionality with HashMap.