📖 What is a HashMap?
HashMapis a Java class that implements the
A Mapinterface and allows you to store data as
key-value pairs. It providesfast accessto elementsusing hashing.
Key Characteristics
● 🗝️
Key: Unique identifier for a value.
● 📦
Value: Data associated with the key.
● ✅
Allows nulls: One nullkey and multiple
nullvalues.
● 🔀
Unordered: Does not maintain insertion order.
● ⚡ put()and
Efficient: O(1) time complexity (average case) for get()operations.
● 🔒Not thread-safe: Use
ConcurrentHashMapfor multithreadedenvironments.
🌟 Features of HashMap
.
1 ashing: Keys are hashed into bucket indices for fastlookup.
H
2. Collision Handling: Uses linked lists or balancedtrees for collisions.
3. Resizing: Automatically resizes when the load factoris exceeded.
4. Customizable Capacity and Load Factor: You can configurethem for performance
optimization.
🛠️ How HashMap Works Internally
1. Hashing
hashCode()determines the bucket index using:
hekey's
T
index = (hashCode & (capacity - 1))
●
2. Buckets
T
● he hash table is an array of buckets.
● Each bucket can store multiple entries if collisions occur.
3. Collision Handling
B
● efore Java 8: Linked lists are used within buckets.
● Java 8 and later: Converts linked lists to balancedtrees for faster lookups if a bucket
has more than 8 entries.
4. Resizing
● W HashMap
hen the number of elements exceeds the threshold (capacity × load factor),
resizes:
1. Doubles the array size.
2. Rehashes all existing entries into the new table.
🌟Visualizing HashMap's Internal Structure
Diagram Explanation
put()
● HashMap: Manages the hash table and provides APIslike get()
, , and
emove()
r .
● Hash Table: The underlying array of buckets wheredata is stored.
Bucket: Each bucket contains a linked list or balancedtree (depending on Java version
●
and collision frequency).
● Entry: Represents each key-value pair in theHashMap ,with a pointer to the next entry
in case of collisions.
🛠️ Commonly Used Methods in HashMap
✍️ Examples
Example 1: Basic Usage
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<>();
map.put("Alice", "123-456");
map.put("Bob", "987-654");
System.out.println(map.get("Alice")); // Output: 123-456
}
}
Example 2: Word Counter
Count occurrences of words in a string:
String text = "Java is fun and Java is powerful";
HashMap<String, Integer> wordCount = new HashMap<>();
for (String word : text.split(" ")) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
System.out.println(wordCount); // Output: {Java=2, is=2, fun=1, and=1, powerful=1}
🔄 Iteration Methods
1. Key Set Iteration
for (String key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
}
2. Entry Set Iteration (Preferred)
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
3. Java 8 forEach
map.forEach((key, value) -> System.out.println(key + ": " + value));
🔒 Thread Safety in HashMap
HashMapisnot thread-safe. For multithreading, use:
Synchronized HashMap:
Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
.
1
2. ConcurrentHashMap:
D
○ ivides the hash table into segments for thread-safe concurrent access.
○ Does not allownullkeys or values.
⚠️ Common Pitfalls
1. Using Mutable Keys:
If a key's state changes after insertion, it becomes unretrievable.
○
○ Always use immutable objects like Stringas keys.
hashCode()and
2. Improper equals()
:
hashCode()and
Ensure
○ equals()are consistent forcustom keys.
3. High Load Factors:
○ A
high load factor (e.g., >0.75) increases collision chances and reduces
performance.
🎯 Real-World Use Cases
1. Caching:
Store frequently accessed data for fast retrieval.
○
2. Indexing:
Use for indexing data in databases or search engines.
○
3. Grouping Data:
○ Group data based on a common key, like organizing employees by department.
🎓 Interview-Specific Questions
Beginner-Level
1. What is a HashMap?
○ A data structure that stores key-value pairs using hashing.
2. What is the default capacity and load factor of HashMap?
○ Default capacity:16, default load factor:0.75.
Intermediate-Level
3. What happens if two keys have the same hash code?
○ A
collision occurs. Colliding entries are stored in the same bucket, using a linked
list or balanced tree.
4. H
ow does HashMap resize?
○ H
ashMap resizes when the size exceeds capacity × load factor, doubling its
capacity and redistributing entries.
Advanced-Level
5. Why is HashMap's capacity always a power of 2?
Ensures efficient bucket calculation using bitwise operations.
○
6. What is the difference between HashMap and ConcurrentHashMap?
○ H
ashMapis not thread-safe, while
ConcurrentHashMapis thread-safe and
optimized for concurrency.
🏅 Coding Challenges
Challenge 1: Find the First Non-Repeating Character
public class NonRepeating {
public static void main(String[] args) {
String str = "swiss";
HashMap<Character, Integer> charCount = new HashMap<>();
for (char c : str.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
for (char c : str.toCharArray()) {
if (charCount.get(c) == 1) {
System.out.println("First non-repeating character: " + c);
break;
}
}
}
}
Challenge 2: Group Anagrams
import java.util.*;
public class GroupAnagrams {
public static void main(String[] args) {
String[] words = {"bat", "tab", "cat", "act", "dog"};
HashMap<String, List<String>> anagramGroups = new HashMap<>();
for (String word : words) {
char[] chars = word.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
anagramGroups.putIfAbsent(sorted, new ArrayList<>());
anagramGroups.get(sorted).add(word);
}
System.out.println(anagramGroups.values());
}
}
Output:
[[bat, tab], [cat, act], [dog]]
🔍Additional Insights
1. Load Factor Tuning
● T he default load factor (0.75) provides a good trade-off between space and time
complexity.
● When to adjust?
○ If memory is limited and read operations dominate, ahigher load factorreduces
space usage but increases collision likelihood.
○ If fast access is crucial, alower load factorminimizescollisions at the cost of
higher memory usage.
2. Comparison with Other Data Structures
Feature HashMap TreeMap LinkedHashMap
Order Unordered orted (natural or
S Insertion order
custom) preserved
Performance O(1) for get/put O(log n) for get/put O(1) for get/put
Use Case Fast lookups Sorted data access Ordered iteration
3. Custom Key Class for HashMap
HashMap
If you use a custom object as a key in a hashCode()and
,youmust override
equals()
HashMapwill not workcorrectly.
. Without this, the
Example:
class Employee {
int id;
String name;
Employee(int id, String name) {
this.id = id;
this.name = name;
}
Override
@
public int hashCode() {
return id; // Use ID as a unique hash
}
Override
@
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Employee other = (Employee) obj;
return id == other.id;
}
}
public class Main {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<>();
map.put(new Employee(1, "Alice"), "Developer");
map.put(new Employee(2, "Bob"), "Manager");
System.out.println(map.get(new Employee(1, "Alice"))); // Output: Developer
}
}
4. HashMap Performance Optimization
1. Avoid Poorly Distributed HashCodes:
○ A poorly implemented hashCode()can lead to excessivecollisions.
○ Use prime numbers in hash code calculations for better distribution.
2. Minimize Resizing:
HashMapwith an appropriate size ifyou know the approximate
○ Initialize the
number of elements.
5. Debugging HashMap Issues
● Common Issues:
○ Missing entries due to incorrect hashCode()orequals()implementation.
○ Performance degradation caused by excessive collisions.
● Tools:
○ Use Java Profiler (e.g., JVisualVM) to monitor bucket usage and resizing
behavior.
hashCode()values and bucket indices to diagnosecollision problems.
○ Log
🎓 Tips for Interviews
1. Understand When to Use HashMap
● Use aHashMapwhen:
○ You needconstant time performancefor lookups andinserts.
○ Order of elements doesn’t matter.
2. Explain the Evolution of Collision Resolution
● B HashMapevolved from linkedlists (Java 7) to balanced trees
e ready to explain how
(Java 8+) to improve performance.
3. Real-World Use Case Examples
● Be prepared to discuss scenarios like:
○ Caching in web applications.
○ Indexing in databases.
○ Grouping data(e.g., anagram grouping, word frequencycounting).
🛠️ Practice Coding Challenges
1. Find All Duplicates in an Array
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class FindDuplicates {
public static List<Integer> findDuplicates(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
List<Integer> duplicates = new ArrayList<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int key : map.keySet()) {
if (map.get(key) > 1) {
duplicates.add(key);
}
}
return duplicates;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1, 2, 4};
System.out.println(findDuplicates(nums)); // Output: [1, 2]
}
}
2. Top K Frequent Elements
import java.util.*;
public class TopKFrequent {
public static List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
(a, b) -> b.getValue() - a.getValue()
);
pq.addAll(map.entrySet());
ist<Integer> result = new ArrayList<>();
L
while (k-- > 0) {
result.add(pq.poll().getKey());
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, 2, 3};
int k = 2;
System.out.println(topKFrequent(nums, k)); // Output: [1, 2]
}
}
🔑 Key Takeaways
● U nderstand Internals: Explain hashing, bucket mechanics,collision handling, and
resizing.
● Apply Best Practices: Use immutable keys, tune capacity/loadfactor, and ensure
proper hashCode()and equals()implementations.
● Showcase Problem Solving: Discuss real-world use casesand demonstrate coding
proficiency with practical challenges.
