 (34).png)
Custom Implementation of LinkedHashMap in Java
Preserving Order with Efficiency
Introduction
The LinkedHashMap is a powerful Java collection that combines the fast lookup of a HashMap with the ordering of a linked list.
While a HashMap makes no guarantees about the order of elements, a LinkedHashMap preserves either insertion order or access order (depending on configuration).
This is particularly useful when order matters, for example:
- Maintaining a cache with least-recently-used eviction.
- Preserving configuration settings in the order they were loaded.
In this blog, we will:
- Understand the internal structure of LinkedHashMap.
- Learn about its ordering mechanism.
- Build a custom LinkedHashMap step-by-step.
- Compare it with HashMap.
- Discuss pros, cons, and use cases.
Internal Working of LinkedHashMap
LinkedHashMap extends HashMap and adds a doubly-linked list running through all entries.
This allows it to maintain order while still having constant-time performance for operations.
Structure
Hash Table (array of buckets) + Doubly Linked List
Each entry contains:
- Key
- Value
- Hash code
- Next (for bucket chaining)
- Before and After pointers (for linked list order)
This linked list connects entries in the order they were inserted (or accessed).
Two Ordering Modes
- Insertion order — entries remain in the order they were inserted. (Default mode)
- Access order — entries are moved to the end of the list when accessed.
Designing a Custom LinkedHashMap
We will implement a simplified version of LinkedHashMap that preserves insertion order.
Step 1: Define the Entry Class
This will hold the key-value pair along with pointers for linked list order.
class LinkedEntry {
K key;
V value;
LinkedEntry next; // for bucket chaining
LinkedEntry before; // previous entry in linked list
LinkedEntry after; // next entry in linked list
public LinkedEntry(K key, V value, LinkedEntry next) {
this.key = key;
this.value = value;
this.next = next;
}
}
Step 2: Create the CustomLinkedHashMap Class
public class CustomLinkedHashMap {
private int capacity = 16;
private LinkedEntry[] table;
private LinkedEntry head; // start of linked list
private LinkedEntry tail; // end of linked list
public CustomLinkedHashMap() {
table = new LinkedEntry[capacity];
}
}
Step 3: Implement the put() Method
The put method will:
- Compute the bucket index using hashCode.
- Add the new entry at the head of the bucket chain (hashing).
- Add the entry at the end of the linked list (insertion order).
public void put(K key, V value) {
int hash = Math.abs(key.hashCode()) % capacity;
LinkedEntry newEntry = new LinkedEntry<>(key, value, null);
if (table[hash] == null) {
table[hash] = newEntry;
} else {
LinkedEntry current = table[hash];
LinkedEntry prev = null;
while (current != null) {
if (current.key.equals(key)) {
current.value = value; // update value
return;
}
prev = current;
current = current.next;
}
prev.next = newEntry;
}
// Maintain insertion order
if (head == null) {
head = tail = newEntry;
} else {
tail.after = newEntry;
newEntry.before = tail;
tail = newEntry;
}
}
Step 4: Implement the get() Method
Retrieve value by key without disturbing order.
public V get(K key) {
int hash = Math.abs(key.hashCode()) % capacity;
LinkedEntry current = table[hash];
while (current != null) {
if (current.key.equals(key)) {
return current.value;
}
current = current.next;
}
return null;
}
Step 5: Implement the remove() Method
Remove entry from both the bucket chain and the linked list.
public boolean remove(K key) {
int hash = Math.abs(key.hashCode()) % capacity;
LinkedEntry current = table[hash];
LinkedEntry prev = null;
while (current != null) {
if (current.key.equals(key)) {
if (prev == null) {
table[hash] = current.next;
} else {
prev.next = current.next;
}
// Remove from linked list
if (current.before != null) {
current.before.after = current.after;
} else {
head = current.after;
}
if (current.after != null) {
current.after.before = current.before;
} else {
tail = current.before;
}
return true;
}
prev = current;
current = current.next;
}
return false;
}
Step 6: Implement display() Method
Display all entries in insertion order.
public void display() {
LinkedEntry current = head;
while (current != null) {
System.out.print("[" + current.key + "=" + current.value + "] ");
current = current.after;
}
System.out.println();
}
Step 7: Testing CustomLinkedHashMap
public class TestCustomLinkedHashMap {
public static void main(String[] args) {
CustomLinkedHashMap map = new CustomLinkedHashMap<>();
map.put(1, "Java");
map.put(2, "Python");
map.put(3, "C++");
map.put(17, "Go"); // collision with key=1
map.display();
System.out.println("Get key 2: " + map.get(2));
map.remove(1);
map.display();
}
}
Expected Output
[1=Java] [2=Python] [3=C++] [17=Go]
Get key 2: Python
[2=Python] [3=C++] [17=Go]
This shows that insertion order is preserved even after deletions.
Custom LinkedHashMap Implementation
// Custom LinkedHashMap Implementation
// Preserves insertion order like java.util.LinkedHashMap
class LinkedEntry<K, V> {
K key;
V value;
LinkedEntry<K, V> next; // For bucket chaining (hash collisions)
LinkedEntry<K, V> before; // Previous entry in insertion order
LinkedEntry<K, V> after; // Next entry in insertion order
public LinkedEntry(K key, V value, LinkedEntry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public class CustomLinkedHashMap<K, V> {
private int capacity = 16;
private LinkedEntry<K, V>[] table;
private LinkedEntry<K, V> head; // Start of insertion order
private LinkedEntry<K, V> tail; // End of insertion order
@SuppressWarnings("unchecked")
public CustomLinkedHashMap() {
table = new LinkedEntry[capacity];
}
// Step 1: Put method
public void put(K key, V value) {
int hash = Math.abs(key.hashCode()) % capacity;
LinkedEntry<K, V> newEntry = new LinkedEntry<>(key, value, null);
if (table[hash] == null) {
table[hash] = newEntry;
} else {
LinkedEntry<K, V> current = table[hash];
LinkedEntry<K, V> prev = null;
while (current != null) {
if (current.key.equals(key)) {
current.value = value; // update existing key
return;
}
prev = current;
current = current.next;
}
prev.next = newEntry;
}
// Maintain insertion order
if (head == null) {
head = tail = newEntry;
} else {
tail.after = newEntry;
newEntry.before = tail;
tail = newEntry;
}
}
// Step 2: Get method
public V get(K key) {
int hash = Math.abs(key.hashCode()) % capacity;
LinkedEntry<K, V> current = table[hash];
while (current != null) {
if (current.key.equals(key)) {
return current.value;
}
current = current.next;
}
return null;
}
// Step 3: Remove method
public boolean remove(K key) {
int hash = Math.abs(key.hashCode()) % capacity;
LinkedEntry<K, V> current = table[hash];
LinkedEntry<K, V> prev = null;
while (current != null) {
if (current.key.equals(key)) {
// Remove from hash bucket
if (prev == null) {
table[hash] = current.next;
} else {
prev.next = current.next;
}
// Remove from linked list (insertion order)
if (current.before != null) {
current.before.after = current.after;
} else {
head = current.after;
}
if (current.after != null) {
current.after.before = current.before;
} else {
tail = current.before;
}
return true;
}
prev = current;
current = current.next;
}
return false;
}
// Step 4: Display method — prints in insertion order
public void display() {
LinkedEntry<K, V> current = head;
while (current != null) {
System.out.print("[" + current.key + "=" + current.value + "] ");
current = current.after;
}
System.out.println();
}
}
// Step 5: Test the CustomLinkedHashMap
class TestCustomLinkedHashMap {
public static void main(String[] args) {
CustomLinkedHashMap<Integer, String> map = new CustomLinkedHashMap<>();
map.put(1, "Java");
map.put(2, "Python");
map.put(3, "C++");
map.put(17, "Go"); // Collision with key=1 (same bucket likely)
map.display();
System.out.println("Get key 2: " + map.get(2));
map.remove(1);
map.display();
}
}
Expected Output
[1=Java] [2=Python] [3=C++] [17=Go]
Get key 2: Python
[2=Python] [3=C++] [17=Go]
Advantages of LinkedHashMap
- Maintains insertion or access order.
- Provides predictable iteration order.
- Almost the same performance as HashMap.
- Useful in caching scenarios.
Disadvantages of LinkedHashMap
- Slightly more memory usage due to linked list pointers.
- Slightly slower than HashMap due to maintaining order.
- Not synchronized (use Collections.synchronizedMap() or ConcurrentHashMap for thread safety).
Real-World Applications
- Implementing LRU Caches.
- Maintaining order-sensitive data, e.g., configuration settings.
- Building index-based systems where order matters.
Conclusion
In this blog, we created a CustomLinkedHashMap to understand how Java’s LinkedHashMap preserves order while maintaining efficient access.
We learned:
- How it combines a hash table with a doubly-linked list.
- How insertion and deletion maintain order.
- The internal mechanics behind one of Java’s most versatile data structures.
Next Blog- Custom Implementation of LinkedHashSet in Java
 (17).png)
.png)
 (53).png)
 (18).png)
.png)
.png)
 (1).png)
 (2).png)
 (3).png)
 (4).png)
 (5).png)
 (6).png)
 (9).png)
 (7).png)
 (10).png)
 (8).png)
 (10).png)
 (12).png)
 (13).png)
 (13).png)
 (15).png)
 (16).png)
 (19).png)
 (20).png)
 (21).png)
 (22).png)
 (23).png)
 (24).png)
 (25).png)
 (26).png)
 (27).png)
 (28).png)
 (29).png)
 (30).png)
 (31).png)
 (32).png)
 (54).png)
 (33).png)
 (35).png)
 (36).png)
 (37).png)
 (38).png)
 (39).png)
 (40).png)
 (41).png)
 (42).png)
 (45).png)
 (46).png)
 (47).png)
 (48).png)
 (55).png)
 (50).png)
 (51).png)
 (52).png)
 (56).png)
.png)
 (44).png)
