HashMap, TreeMap, HashSet, and TreeSet use different internal data structures and algorithms to achieve efficient storage, retrieval, insertion, and deletion operations. Understanding these internal implementations helps explain their performance characteristics and appropriate use cases.
Key Points: • HashMap uses hashing for fast access to key-value pairs. • TreeMap uses a Red-Black Tree to maintain sorted keys. • HashSet internally relies on HashMap to store unique elements. • TreeSet internally relies on TreeMap to maintain sorted unique elements. • The choice of internal data structure directly impacts performance and ordering behavior.
HashMap Internal Technique
HashMap stores data using:
• Array of buckets • Hashing algorithm • Linked Lists (for collisions) • Red-Black Trees (Java 8+)
How It Works:
1. hashCode() generates a hash value. 2. HashMap determines the bucket index. 3. The entry is stored in that bucket. 4. equals() is used to identify the exact key.
Collision Handling:
Before Java 8:
Bucket
KeyA -> KeyB -> KeyC
After Java 8 (Heavy Collisions):
KeyB
/ \KeyA KeyC
Technique Used:
• Hashing • Chaining • Red-Black Tree optimization
Average Complexity:
• put() → O(1) • get() → O(1) • remove() → O(1)
TreeMap Internal Technique
TreeMap stores entries using a Red-Black Tree.
A Red-Black Tree is:
• A self-balancing Binary Search Tree • Automatically balanced after insertion and deletion
Structure:
50
/ \30 70 / \ / \ 20 40 60 80
Each node stores:
• Key • Value • Parent reference • Left child • Right child
Technique Used:
• Binary Search Tree • Red-Black Tree balancing
Complexity:
• put() → O(log n) • get() → O(log n) • remove() → O(log n)
HashSet Internal Technique
HashSet does not have its own storage structure.
Internally:
HashSet uses HashMap.
Simplified Representation:
HashSet<String> set =
new HashSet<>();Internally behaves like:
HashMap<String, Object> map =
new HashMap<>();Stored Form:
Key Value
Java PRESENT
Spring PRESENT
Only keys matter.
Values are dummy objects.
Technique Used:
• Hashing • HashMap-based storage
Complexity:
• add() → O(1) • contains() → O(1) • remove() → O(1)
TreeSet Internal Technique
TreeSet internally uses TreeMap.
Simplified Representation:
TreeSet<Integer> set =
new TreeSet<>();Internally behaves like:
TreeMap<Integer, Object> map =
new TreeMap<>();Stored Form:
Key Value
10 PRESENT
20 PRESENT
30 PRESENT
Elements become TreeMap keys.
Technique Used:
• Red-Black Tree • TreeMap-based storage
Complexity:
• add() → O(log n) • contains() → O(log n) • remove() → O(log n)
Example: Suppose we store employee IDs.
HashSet:
101, 102, 103
Internally:
HashMap
101 → PRESENT 102 → PRESENT 103 → PRESENT
TreeSet:
101, 102, 103
Internally:
Red-Black Tree
102
/ \101 103
Comparison Table
HashMap:
• Internal Structure → Array + Hashing + Linked List/Tree • Ordering → No • Duplicate Keys → No • Average Complexity → O(1)
TreeMap:
• Internal Structure → Red-Black Tree • Ordering → Sorted Keys • Duplicate Keys → No • Average Complexity → O(log n)
HashSet:
• Internal Structure → HashMap • Ordering → No • Duplicate Elements → No • Average Complexity → O(1)
TreeSet:
• Internal Structure → TreeMap (Red-Black Tree) • Ordering → Sorted Elements • Duplicate Elements → No • Average Complexity → O(log n)
Interview Tip: A concise interview answer is:
"HashMap uses hashing with an array of buckets and handles collisions using Linked Lists or Red-Black Trees. TreeMap uses a Red-Black Tree to maintain sorted key-value pairs. HashSet is internally backed by a HashMap and stores elements as keys, while TreeSet is backed by a TreeMap and stores elements in a Red-Black Tree structure. These internal implementations determine their ordering behavior and performance characteristics."