 (35).png)
Custom Implementation of LinkedHashSet in Java
Combining Uniqueness with Order Preservation
Introduction
A LinkedHashSet in Java combines the unique element guarantee of a HashSet with the predictable iteration order of a LinkedHashMap.
Essentially, it is a hybrid that maintains insertion order while ensuring that no duplicates exist.
LinkedHashSet is widely used when:
- You need to remove duplicates but maintain order.
- You require fast lookups along with predictable iteration order.
In this blog, we will:
- Understand the internal working of LinkedHashSet.
- Learn why it internally uses LinkedHashMap.
- Build a custom implementation step-by-step.
- Compare it with HashSet and LinkedHashMap.
- Explore advantages, disadvantages, and applications.
How LinkedHashSet Works Internally
In Java, LinkedHashSet is implemented internally using a LinkedHashMap.
When an element is added to a LinkedHashSet, it is stored as a key in the backing LinkedHashMap, with a constant dummy object as its value.
Example:
LinkedHashSet set = new LinkedHashSet<>();
set.add("Java");
set.add("Python");
set.add("C++");
Internally:
LinkedHashMap:
[Java=null, Python=null, C++=null]
Thus:
- Uniqueness comes from HashMap keys.
- Order preservation comes from LinkedHashMap’s linked list mechanism.
Designing a Custom LinkedHashSet
Since LinkedHashSet relies on LinkedHashMap, our custom version will use our previously implemented CustomLinkedHashMap.
Step 1: Define the CustomLinkedHashSet Class
public class CustomLinkedHashSet {
private static final Object DUMMY = new Object();
private CustomLinkedHashMap map;
public CustomLinkedHashSet() {
map = new CustomLinkedHashMap<>();
}
}
Here:
- We store all set elements as keys in our CustomLinkedHashMap.
- A single dummy object is used as the value.
Step 2: Implement the add() Method
Adds an element to the set if it doesn’t already exist.
public boolean add(K key) {
if (map.get(key) == null) {
map.put(key, DUMMY);
return true;
}
return false; // element already exists
}
Step 3: Implement the contains() Method
Checks if an element exists in the set.
public boolean contains(K key) {
return map.get(key) != null;
}
Step 4: Implement the remove() Method
Removes the element from the set.
public boolean remove(K key) {
return map.remove(key);
}
Step 5: Implement the display() Method
Displays elements in insertion order.
public void display() {
map.display();
}
Step 6: Testing CustomLinkedHashSet
public class TestCustomLinkedHashSet {
public static void main(String[] args) {
CustomLinkedHashSet set = new CustomLinkedHashSet<>();
set.add("Java");
set.add("Python");
set.add("C++");
set.add("Java"); // duplicate element
set.display();
System.out.println("Contains Python? " + set.contains("Python"));
System.out.println("Contains Ruby? " + set.contains("Ruby"));
set.remove("Python");
set.display();
}
}
Expected Output
[Java] [Python] [C++]
Contains Python? true
Contains Ruby? false
[Java] [C++]
This output shows:
- Uniqueness is preserved (Java wasn’t added twice).
- Insertion order is maintained even after removal.
Custom LinkedHashSet Implementation
// Custom LinkedHashMap Implementation (used internally by LinkedHashSet)
class LinkedEntry<K, V> {
K key;
V value;
LinkedEntry<K, V> next; // for bucket chaining
LinkedEntry<K, V> before; // previous in insertion order
LinkedEntry<K, V> after; // next in insertion order
public LinkedEntry(K key, V value, LinkedEntry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
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];
}
// Add or update key-value pair
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;
}
}
// Retrieve value by key
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;
}
// Remove a key-value pair
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 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;
}
// Display entries in insertion order
public void display() {
LinkedEntry<K, V> current = head;
while (current != null) {
System.out.print("[" + current.key + "] ");
current = current.after;
}
System.out.println();
}
}
// Custom LinkedHashSet Implementation
public class CustomLinkedHashSet<K> {
private static final Object DUMMY = new Object();
private CustomLinkedHashMap<K, Object> map;
public CustomLinkedHashSet() {
map = new CustomLinkedHashMap<>();
}
// Add element if not already present
public boolean add(K key) {
if (map.get(key) == null) {
map.put(key, DUMMY);
return true;
}
return false;
}
// Check if element exists
public boolean contains(K key) {
return map.get(key) != null;
}
// Remove element
public boolean remove(K key) {
return map.remove(key);
}
// Display elements in insertion order
public void display() {
map.display();
}
}
// Testing CustomLinkedHashSet
class TestCustomLinkedHashSet {
public static void main(String[] args) {
CustomLinkedHashSet<String> set = new CustomLinkedHashSet<>();
set.add("Java");
set.add("Python");
set.add("C++");
set.add("Java"); // duplicate
set.display();
System.out.println("Contains Python? " + set.contains("Python"));
System.out.println("Contains Ruby? " + set.contains("Ruby"));
set.remove("Python");
set.display();
}
}
Expected Output
[Java] [Python] [C++]
Contains Python? true
Contains Ruby? false
[Java] [C++]
This implementation ensures:
- Uniqueness (no duplicates allowed)
- Preserved insertion order
- Built entirely on top of your CustomLinkedHashMap
Time Complexity of LinkedHashSet Operations
| Operation | Average Case | Worst Case |
|---|---|---|
| add() | O(1) | O(n) |
| contains() | O(1) | O(n) |
| remove() | O(1) | O(n) |
Performance depends on the underlying LinkedHashMap, which uses hashing and chaining/tree structures for collision handling.
Differences Between HashSet and LinkedHashSet
| Feature | HashSet | LinkedHashSet |
|---|---|---|
| Order | No guarantee | Maintains insertion order |
| Backing Structure | HashMap | LinkedHashMap |
| Memory Overhead | Less | Slightly more |
| Null Values | Allows one null | Allows one null |
Advantages of LinkedHashSet
- Maintains insertion order.
- Ensures uniqueness.
- Allows fast lookups (O(1) average case).
- Useful for applications requiring order preservation and uniqueness.
Disadvantages of LinkedHashSet
- Slightly higher memory consumption than HashSet.
- Slightly slower than HashSet due to linked list maintenance.
- Not synchronized (use Collections.synchronizedSet() for thread safety).
Real-World Applications
- Removing duplicates from a collection while preserving order.
- Maintaining an ordered set of unique configuration entries.
- Building LRU caches.
- Storing unique items in predictable order for reporting or display.
Conclusion
By implementing a CustomLinkedHashSet, we have:
- Seen how Java’s LinkedHashSet is a wrapper around LinkedHashMap.
- Understood the importance of order preservation and uniqueness.
- Built a working model that demonstrates these principles in action.
LinkedHashSet is especially useful in cases where order matters but uniqueness cannot be compromised.
Next Blog- Custom Implementation of ArrayList 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)
 (34).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)
