5 Tricky Interview Questions on Hashmap | Java 8

Ankit Wasankar
3 min readJun 3, 2023

--

  1. How Hashmap is stored in memory — Memory Structure ?
  2. What is Hash Collision during hashmap.put() operation ?
  3. What is the significance of equals() and hashcode() in Hashmap ?
  4. Why the searching time-complexity of HashMap is O(1) ?
  5. What is Hashmap treefy threshold and why it is introduced in Java 8 ?

Watch the video, to know find out answers to these questions.

This video is a comprehensive guide to HashMap related interview questions and enhacenments that are done to HashMap internal working in Java 8.

#java #javainterviewquestions #interviewquestions #hashmap #webencylop

— — — — — — — — — — — — — — — — — —

  1. Memory Structure of Hashmap:

A Hashmap is typically implemented as an array of linked lists or as an array of balanced binary search trees (from Java 8 onwards, when the threshold is crossed). The array provides the buckets to store key-value pairs. Each bucket can hold multiple entries (either in a linked list or a tree) to handle hash collisions. The index of the array is calculated using the hash code of the key.

2. Hash Collision during hashmap.put():

Hash collision occurs when two different keys have the same hash code. In a Hashmap, when a collision occurs during the put() operation, the new key-value pair is added to the existing bucket. If the bucket uses a linked list, the new entry is appended to the list. If the bucket uses a tree (after reaching the treefy threshold), the tree structure is used to handle collisions.

3. Significance of equals() and hashCode() in Hashmap:

The equals() and hashCode() methods are crucial for proper functioning of a Hashmap. The hashCode() method is used to calculate the hash code of a key, which determines the index of the bucket where the key-value pair is stored. The equals() method is used to compare keys for equality when there is a hash collision. It helps identify if two keys are the same or different, enabling proper retrieval of values from the Hashmap.

4. Searching time-complexity of HashMap is O(1):

The searching time-complexity of a Hashmap is O(1) on average, which means it has constant-time performance for most operations. This is possible because Hashmap uses a hashing technique to calculate the index where a key-value pair is stored. With a properly distributed hash function, the time complexity to retrieve a value is independent of the number of elements stored in the Hashmap.

5. Hashmap treefy threshold and its introduction in Java 8:

The “treefy threshold” is the number of entries a bucket can hold before it is converted from a linked list to a balanced binary search tree. In Java 8, an optimization was introduced to convert a bucket to a tree structure when the number of entries in that bucket exceeds a certain threshold (usually 8). This was done to improve the worst-case performance of the Hashmap, as a long linked list can lead to degraded search performance. By using a tree, the time complexity for search operations in a bucket is reduced from O(n) to O(log n), resulting in more predictable and improved performance.

Internal working of HashMap.put() method — webencyclop (https://youtu.be/-oafFAPgLao)

--

--