DEV Community: Zeyad Mohamed

System Design: Horizontal vs Vertical Scaling

Zeyad Mohamed — Sat, 09 Aug 2025 20:01:07 +0000

When your app is just starting out, scaling isn’t something you think about much , and one decent server usually does the job. But as traffic grows, you eventually hit a wall and have to decide: do you make your server stronger or add more servers to share the load? Let’s break down these two approaches.

Scalability

When we first launch an app, the traffic is usually pretty manageable.

But as it becomes more popular, we might start getting way more requests than our current setup can handle.

The ability to deal with this increased number of requests is known as scalability.

We are essentially handling more requests by throwing “more money” at the problem.

There are two common approaches to this:

Vertical Scaling → Buy a bigger machine.

Horizontal Scaling → Buy more machines of the same capability.

Horizontal Scaling

Pros

Better fault tolerance. If one machine fails, we can still redirect requests to the others.
Auto scaling is very easy with deployment platforms like Kubernetes.
This makes horizontal scaling very responsive to an application’s fluctuating demands, leading to high availability.

Cons

We have to use a load balancer to distribute the requests across the different instances.

Could introduce network calls (RPCs) for coordination even in monoliths, leading to more complexity and increased latency.
It is harder to maintain data consistency, especially if each instance has its own independent copy of the DB (big big no).
If we use a strategy where we have one primary write-DB and multiple read replicas, we are still left with eventual consistency in our read operations because the read replicas are updated asynchronously so that write performance is not affected negatively.

If we decide to shard the DB so that each instance owns a portion of the data, then fetching data which may exist in different instances might become very hard.

This might require us to denormalize the database so that joins are less frequent, but this would introduce duplicated data.
If we want to apply transactional operations and the data is spread over different instances, this will be hard unless we use the Saga pattern, which is more complex than traditional transactions on a single DB.

Vertical Scaling

Pros

Data consistency.
Does not introduce the added complexity that comes with a load balancer.
Communication always stays within the same app (no RPCs).
Transactions are easy to implement as we are dealing with a single DB.

Cons

We can only upgrade a single machine’s capabilities so much until we hit a limit.
Might have availability issues because the app must be re-deployed when we change the machine’s resources, leading to possible downtime.
Single point of failure.

Wrapping Up

Vertical scaling is simpler but limited in growth and has a single point of failure.
Horizontal scaling is more resilient and easier to grow, but comes with complexity in coordination, consistency, and transactions.

Think of it like this:

Vertical scaling is putting a bigger engine in one car.
Horizontal scaling is adding more cars to your fleet.

All in all, scaling is one of those things that looks simple on paper but gets tricky fast once you factor in real-world trade-offs. Both approaches have their place, and which one you choose depends on your app’s needs and constraints.

Which scaling approach have you used before, and what challenges did you run into?

Leetcode 146: LRU Cache

Zeyad Mohamed — Fri, 04 Jul 2025 13:37:25 +0000

In this post, I break down how to implement a Least Recently Used cache using a HashMap and a doubly linked list.

Problem Breakdown

In this leetcode problem, we are asked to implement a data structure that follows the constraints of a Least Recently Used (LRU) cache.

We are required to implement the following methods with these requirements:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return 1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

It is not made very clear in the problem description, but the premise is that whenever we call get() or put() on a key then this counts as using that key, and so it will be moved to the most recently used end of our cache (previous to tail).

We are also required to make the get() and put() functions run in O(1) time.

This is a fundamental design problem that simulates a pattern that is actually used very often in real-world systems.

A classic real-world example of an LRU cache is found in Redis, a popular in-memory key-value store used for caching and high-speed data access.

Redis allows developers to set a maximum memory limit for the cache, and once this limit is reached, it automatically evicts keys using an LRU (Least Recently Used) policy.
This means that:
- Frequently accessed keys are kept in memory.
- Least recently used keys are discarded first to make room for new entries.
- The system stays memory-efficient while still delivering fast access for the frequently used data.

Our LRU cache solution mimics this behaviour on a smaller scale: using a HashMap for quick lookups and a doubly linked list to track usage order.

Provided Example

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Hopefully now you have an idea of what we are trying to solve in this problem. Lets now get into the solution.

Solution Breakdown

Overview

I will try to explain the solution step by step with small code snippets and visuals along the way. The full code is found down below.

To design an efficient LRU cache that optimizes memory as well as performance, we will do the following:
- Use a HashMap for storing unique keys referencing their respective Nodes.
- A static Node class will be used to encapsulate an entry in our cache.
- A doubly linked list will be used for efficient insertions and removals of nodes.
- The head of the list will always point to the least recently used entry in our cache.
- The tail of the list will have a previous pointer that points to the most recently used entry in our cache. Even though this problem does not require retrieval of the most recently used element, the tail node just avoids any null-pointer edge cases by keeping our list connected from both sides.
- Maintain an efficient O(1) time complexity for all operations.

In a large-scale production system, we might not implement the LRU cache using raw linked list nodes. Instead, we’d often store actual domain-specific objects in the cache and maintain a separate variable which stores the least recently used key so we can easily access it from the map.

For example, we could have UserSession, ProductInfo, or QueryResult, and manage them via a Map.

Data Structure Design

This is the given class we must implement:

class LRUCache {

    public LRUCache(int capacity) {

    }

    public int get(int key) {

    }

    public void put(int key, int value) {

    }
}

We begin by defining our static Node class which will represent the entries in our cache:
```
static class Node {
      int key, val;
      Node prev, next;
      Node(int key, int val) {
          this.key = key;
          this.val = val;
      }
}
```
- Each Node stores a key and a val as well as references to the previous and next nodes in the linked list (prev and next).
- The HashMap we use will map each key in our cache to a Node.

The LRUCache class maintains the following:
```
private int capacity;
private Map<Integer, Node> cache;
private Node head, tail;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.cache = new HashMap<>();
    this.head = new Node(0, 0);        // dummy node
    this.tail = new Node(0, 0);        // dummy node

    // connect the head and tail
    this.head.next = this.tail;
    this.tail.prev = this.head;
}
```
- capacity is the maximum capacity that our cache can hold.
- cache is the map used to store the key-value pairs in our cache. The keys are of type Integer and the values are of type Node.
- head represents the left-most node in our doubly linked list. It will always be pointing to the least recently used element in our cache.
- prev represents the right-most node in our doubly linked list. Its previous pointer will always point to the most recently used element in our cache.
- We make sure to connect head and tail so that all elements to be added will go in between those two nodes. We do this by assigning head.next to point to tail and tail.prev to head.

This is how our cache looks like initially:

Insertion and Removal Logic

Before we get into the implementations of the two main functions, we first need to discuss the two helper methods we will use throughout our code: insert() and remove().

Lets start with insert():
```
// inserts a node to the tail of the list
private void insert(Node node) {
    node.next = tail;
    node.prev = tail.prev;
    tail.prev.next = node;
    tail.prev = node;
}
```
- This function will be used to insert a node to the right-end of the linked list, just before the tail.
- We insert the node at the end of the list, just before the tail dummy node, by performing the following steps in order:
  - Set the next pointer of the new node to point to tail.
  - Set its prev pointer to point to the current last node (i.e., the node currently referenced by tail.prev).
  - At this point, the new node’s internal links (prev and next) are correctly set.
  - Now, update the next pointer of the previous last node (tail.prev.next) to point to the new node.
  - Finally, update tail.prev to point to the new node, completing the insertion.

Below is an illustration of this operation:

We can see how the new node is inserted between head and tail. If we keep calling the insert() method, new nodes will keep being inserted to the right end of the list.

Now lets move on to remove():
```
// removes node from anywhere in the list
private void remove(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}
```
- This method removes a given node from any position in the doubly linked list
- It first updates the next pointer of the node’s previous node (node.prev.next) to point to node.next.
- Then, it updates the prev pointer of the node’s next node (node.next.prev) to point to node.prev.
- These two pointer adjustments effectively unlink the node from the list, eliminating all references to it
- After this, the node becomes unreachable (assuming no external references), and can be garbage-collected.
- Note: The order of these two operations doesn’t matter, since they independently update the neighboring nodes.

This is a visual the illustrates this removal:

Method Implementation

Now that we understood the helper functions to be used, lets look at the get() method:
```
public int get(int key) {
    if (!cache.containsKey(key)) return -1;

    Node node = cache.get(key);

    // remove node from its current place in the list
    remove(node);

    // move node to the tail of the list (most recently used)
    insert(node);

    return node.val;
}
```
- This functions checks whether a key exists in our cache or not.
- If the key does not exist, it returns -1.
- If the key exists, then we do the following:
  - We remove the node referenced by key from its current position in the list.
  - We then insert the node to the tail-end of the list so that it is now the most recently used node.
  - We then return the val property of the node.

Now onto the put() method:

public void put(int key, int value) {
      if (cache.containsKey(key)) {       // key already exists
          Node node = cache.get(key);

          // remove node from its current position in the list
          remove(node);
      }

      Node newNode = new Node(key, value);
      cache.put(key, newNode);
      insert(newNode);

      // evict the lru node if cache exceeds capacity
      if (cache.size() > capacity) {
          Node lruNode = head.next;
          int lruKey = lruNode.key;

          remove(lruNode);        // remove lru node from the list
          cache.remove(lruKey);       // remove reference to lru node from map
      }
}

The put() method inserts a new key-value pair into the cache, or updates the existing value if the key already exists.
It first checks whether the key is already present in the cache. If it is, we retrieve the corresponding node and remove it from its current position in the linked list.
Regardless of whether the key existed or not, we then create a new node with the provided key and value.
We update the cache map so that this key now points to the new node
The new node is inserted at the tail end of the linked list, representing the most recently used key.
Since this operation could increase the size of the cache, we then check whether we've exceeded the allowed capacity.
If we have, we identify the least recently used node, which is always located at head.next, and remove it from both the linked list and the cache map.

Example Walkthrough

Lets now run through an example showcasing how our LRU cache will work:
- LRUCache lRUCache = new LRUCache(2);
- lRUCache.put(1, 1);
- lRUCache.put(2, 2);
- lRUCache.get(1); // returns 1 and 1=1 becomes the mru key
- lRUCache.put(3, 3); // 2=2 is the lru key and is removed due to capacity constraint
- lRUCache.get(2); // returns -1
- lRUCache.put(4, 4); // 1=1 is the lru key and is removed due to capacity constraint
- lRUCache.get(1); // returns -1
- lRUCache.get(3); // returns 3 and 3=3 becomes the mru key
- lRUCache.get(4); // returns 4 and 4=4 becomes the mru key

Full Code

class LRUCache {
    static class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int capacity;
    private Map<Integer, Node> cache;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(0, 0);        // dummy node
        this.tail = new Node(0, 0);        // dummy node

        // connect the head and tail
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;

        Node node = cache.get(key);

        // remove node from its current place in the list
        remove(node);

        // move node to the tail of the list (most recently used)
        insert(node);

        return node.val;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {       // key already exists
            Node node = cache.get(key);

            // remove node from its current position in the list
            remove(node);
        }

        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        insert(newNode);        // inserted at tail end (most recently used)

        // evict the lru node if cache exceeds capacity
        if (cache.size() > capacity) {
            Node lruNode = head.next;
            int lruKey = lruNode.key;

            remove(lruNode);                 
            cache.remove(lruKey);
        }
    }

    // inserts a node to the tail of the list
    private void insert(Node node) {
        node.next = tail;
        node.prev = tail.prev;
        tail.prev.next = node;
        tail.prev = node;
    }

    // removes node from anywhere in the list
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Complexity Analysis

Time Complexity

Operation	Time Complexity	Explanation
`get(key)`	O(1)	`HashMap` lookup + list node removal and re-insertion take constant time
`put(key, val)`	O(1)	`HashMap` update + doubly linked list insert/remove take constant time

Space Complexity

Component	Space Complexity	Explanation
HashMap (cache)	O(capacity)	Stores up to `capacity` key → node mappings
Doubly Linked List	O(capacity)	Stores up to `capacity` nodes with key-value pairs
Total	O(capacity)	Linear space usage in terms of the max number of keys the cache holds

If this breakdown helped or you approached it differently, I’d love to hear your thoughts.

Drop a comment, leave a ❤️, or share how you'd extend or optimize the design.

Follow for more deep dives into LeetCode systems problems and backend design patterns.

LeetCode 705: Design HashSet

Zeyad Mohamed — Tue, 01 Jul 2025 18:33:29 +0000

In this post, I break down how to implement a memory-efficient HashSet from scratch in Java using separate chaining, dynamic resizing, and amortized analysis, without relying on built-in data structures.

Problem Breakdown

In this leetcode problem, we are asked to implement a class that simulates the functionality of a HashSet without using any built-in HashSet data structure.

We are required to implement the following methods:
- void add(key) - Inserts the value key into the HashSet.
- bool contains(key) - Returns whether the value key exists in the HashSet or not.
- void remove(key) - Removes the value key from the HashSet. If key does not exist, do nothing.

At first glance, this may seem straightforward, especially if you have used HashSet in any language before. But the real challenge lies in achieving:
- O(1) average time complexity for all operations (add, contains, remove).
- Efficient memory usage, especially when we only store a small subset of values within the large keyspace that can go up to 1,000,000.

I saw many solutions essentially just initialising a boolean array of size 1,000,001 and toggle the entries based on the key. This approach works, but it is extremely wasteful in terms of space, particularly if only a few keys are used.

Hence we get to the crux of our problem: How can we minimize memory usage while still maintaining fast performance?

Lets dive into a proper design that balances time efficiency and space optimization using a real-world inspired data structure: a dynamic array of linked lists (i.e., buckets).

Solution Breakdown

Overview

I will try to explain the solution step by step with small code snippets along the way. The full code is found down below.

First, to design an efficient HashSet from scratch, we draw inspiration from how real-world hash tables work under the hood. The core idea is to:
- Use an array of buckets, where each bucket is implemented as a singly linked list.
- Store key values as Node instances within these buckets.
- Dynamically resize the hash table as more keys are added based on a load factor threshold.
- Maintain average O(1) time complexity for add, remove, and contains, while using memory more efficiently than a flat 1-million-element array.

But why use this more complicated approach? Well, simpler solutions do exist (e.g., initializing a boolean array of size 1,000,001), however, they are extremely memory-inefficient in scenarios where few keys are inserted.

Our approach aims to offer a balance of time efficiency and space optimization, using a hash-based strategy with separate chaining.

Data Structure Design

This is the given class we must implement:

class MyHashSet {

    public MyHashSet() {

    }

    public void add(int key) {

    }

    public void remove(int key) {

    }

    public boolean contains(int key) {

    }
}

We begin by defining a static Node class to represent elements stored in each bucket
```
static class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
    }
}
```
- Each Node stores a key (val) and a reference to the next node in the linked list (next).
- Buckets are simply linked lists of these nodes.

The MyHashSet class maintains:

    private Node[] hashTable;
    private int size;

    public MyHashSet() {
        this.hashTable = new Node[16];
    }

hashTable is the array of buckets (initially of size 16).
size tracks the total number of keys currently inserted.

Hashing and Indexing Logic

We define a helper method to compute a stable hash value and another one to derive the target index within the hash table:
```
private int hashKey(int key) {
    return Math.abs(Integer.hashCode(key));
}

private int getIndex(int key) {
    return hashKey(key) % hashTable.length;
}
```
- Integer.hashCode(key) returns the hash of the integer key (in this case, the key itself).
- Taking the modulo of the hash with the array length ensures the key maps to a valid index.
- We use Math.abs to avoid negative indices.

Load Factor and Resizing

To avoid performance degradation due to collisions, we use the load factor to determine when to resize the hash table.
```
    private double getLoadFactor() {
        return (double) size / hashTable.length;      // resize occurs at >= 0.75
    }
```
- When the load factor reaches 0.75, we double the capacity of the hash table.
- This reduces the likelihood of collisions and keeps average operation time close to O(1).
- For example, if we our hash table can hold 16 elements and it currently has 12 elements stored, this gives us a load factor of exactly 0.75.
- At this point we would call the resize() function, which will now be discussed.

The resize() method handles this reallocation:
```
    private void resize() {
        int newSize = hashTable.length * 2;
        Node[] newHashTable = new Node[newSize];     // new map will be twice the size
        for (Node head : hashTable) {
            while (head != null) {
                Node next = head.next;
                int newIndex = hashKey(head.val) % newSize;
                head.next = newHashTable[newIndex];         // in case of a collision, we insert node at the head
                newHashTable[newIndex] = head;
                head = next;
            }
        }
        hashTable = newHashTable;     // re-assign old hash table to new hash table
    }
```
- This function creates a new hash table in memory, which is twice the size of the old hash table.
- It then loops through each linked list (Node) in the old hash table.
- For each bucket/linked list, we traverse each node using a while loop.
- The first thing we do inside the while loop is store a reference to the next node in the linked list so that we don’t lose it.
- We then compute the index of the current node in the new hash table and store this value in newIndex.
- We then insert the current node to the head of the linked list found at newHashTable[newIndex].
  - I was initially confused by this part, but we basically do this because of possible collisions that may also occur during the copying phase.
  - Meaning that newHashTable[newIndex] could already have one or more elements stored there, and so if we just do newHashTable[newIndex] = head then we would overwrite that entire linked list possibly stored at newHashTable[newIndex].
- For this reason, we first do head.next = newHashTable[newIndex] so that the current node head is pointing to the beginning of that list.
- After that we can safely do newHashTable[newIndex] = head so that a reference to head is stored at newHashTable[newIndex].
- After that, we then move to the next element of the linked list by doing head = next. See why we stored a reference to the next node earlier?
- After the entire old hash table is copied over to the new one, we make sure that hashTable points to newHashTable.

Method Implementation

Now that we understood the helper functions to be used, lets start with the add() method:
```
public void add(int key) {
    if (getLoadFactor() >= 0.75) {
        resize();   // copy the map over to a new one
    }

    // check if node already exists in map
    if (contains(key)) return;

    // get key's index
    int index = getIndex(key);

    // insert new node at beginning of bucket at index
    Node newNode = new Node(key);
    newNode.next = hashTable[index];
    hashTable[index] = newNode;

    size++;
}
```
- Before adding the key, we first check if we have reached the maximum threshold for the load factor. If we did, then we call resize() to create a new hash table that is double the current hash table in size and copy all the elements over (as we have seen above).
- This step is important because if we just keep adding elements to our hash table while it remains fixed in size, the number of collisions will keep increasing until it is virtually guaranteed that any new element to be inserted will map to a hash value that already exists (i.e. collision).
- Not resizing will cause our other two methods remove() and contains(), to degrade to a time complexity of O(k) instead of O(1), where k is the number of elements in a given bucket in our hash table.
- The add() method, on the other hand, is guaranteed to always run in O(1) time even if we do not resize the hash table. Adding the call to resize() makes the method occasionally run in O(n) time, but calls to resize() decrease exponentially as the hash table grows, making the add() method run in amortized O(1) time.
  - Amortization is a term we use whenever there is a fixed cost within our system, and we reduce the frequency at which this cost is incurred.
  - In our example here, we decrease the frequency at which the hash table is resized over time, thus amortizing the cost of the add() function to run in O(1) time.
- After we have checked for the load factor, we then check if the key already exists in the hash table by calling the contains() method (discussed below). For now, just know that this method also has amortized O(1) time complexity as the size of the hash table grows, but can run in O(k) time if there are collisions.
- If the key does not exist in the hash table, we get the index of the bucket/list it will be inserted in.
- We then create a new Node instance storing the key, and insert this node at the head of the linked list found at hashTable[index].

Now lets go on to the discuss the remove() method:
```
public void remove(int key) {
    int index = getIndex(key);
    if (hashTable[index] == null) return;        // key does not exist

    Node cur = hashTable[index];
    // key is the first in the bucket
    if (cur.val == key) {
        hashTable[index] = cur.next;
        size--;
        return;
    }

    // find prev to the key that needs to be removed
    while (cur != null && cur.next != null) {
        if (cur.next.val == key) {
            cur.next = cur.next.next;
            size--;
            return;
        }
        cur = cur.next;
    }

    // key does not exist
}
```
- The first thing we do is we get the index of key and check if an element exists. If not, that means key does not exist in our hash table.
- However, if there exists a Node at hashTable[index], then that means there is a possibility that key does exist. We are still not 100% sure due to the possibility of collisions.
- Before traversing the list, we check if key is stored at the head. If it is, we remove it from the hash table by overwriting the value stored at hashTable[index] with cur.next, which is the second element in the list. We also decrement the size of our hash table and then exit the function.
- If the key is not stored at the head of the list, we must traverse the list to find the node previous to the key.
- We are looking for the node previous to the one that stores key so that we can remove any reference to it by changing the next pointer of that previous node to point to the node after key.
  - This effectively unlinks the key node from the list.
- The garbage collector will then automatically remove any reference to key from memory since it is no longer being referenced anywhere in our program.
- If we traverse the entire list and we do not find the node storing key, then that means it does not exist.

Finally, we can now look at contains(), our last and final method:
```
    public boolean contains(int key) {
        int index = getIndex(key);
        Node cur = hashTable[index];
        while (cur != null) {
            if (cur.val == key) return true;
            cur = cur.next;
        }

        return false;
    }
```
- This method simply checks if a key exists in our hash table or not.
- It does that by finding the index that the key would map to.
- It then traverses the list found at hashTable[index] and checks the val property of each node with key.
- We return true if we find the node with a value equal to key; otherwise, we will return false after exiting the loop.

Full Code

class MyHashSet {
    static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    private Node[] hashTable;
    private int size;

    public MyHashSet() {
        this.hashTable = new Node[16];
    }

    /**
    * Worst-case time complexity: O(k), where k is the number of nodes in a bucket (due to collisions).
    * Amortized time complexity: O(1) for add/remove/contains when hashTable are well-distributed.
    */
    public void add(int key) {
        if (getLoadFactor() >= 0.75) {
            resize();   // copy the map over to a new one
        }

        // check if node already exists in map
        if (contains(key)) return;

        // get key's index
        int index = getIndex(key);

        // insert new node at beginning of bucket at index
        Node newNode = new Node(key);
        newNode.next = hashTable[index];
        hashTable[index] = newNode;

        size++;
    }

    public void remove(int key) {
        int index = getIndex(key);
        if (hashTable[index] == null) return;        // key does not exist

        Node cur = hashTable[index];
        // key is the first in the bucket
        if (cur.val == key) {
            hashTable[index] = cur.next;
            size--;
            return;
        }

        // find prev to the key that needs to be removed
        while (cur != null && cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                size--;
                return;
            }
            cur = cur.next;
        }

        // key does not exist
    }

    public boolean contains(int key) {
        int index = getIndex(key);
        Node cur = hashTable[index];
        while (cur != null) {
            if (cur.val == key) return true;
            cur = cur.next;
        }

        return false;
    }

    private int getIndex(int key) {
        return hashKey(key) % hashTable.length;
    }

    private int hashKey(int key) {
        return Math.abs(Integer.hashCode(key));
    }

    private double getLoadFactor() {
        return (double) size / hashTable.length;      // resize occurs at >= 0.75
    }

    private void resize() {
        int newSize = hashTable.length * 2;
        Node[] newHashTable = new Node[newSize];     // new map will be twice the size
        for (Node head : hashTable) {
            while (head != null) {
                Node next = head.next;
                int newIndex = hashKey(head.val) % newSize;
                head.next = newHashTable[newIndex];         // in case of a collision, we insert node at the head
                newHashTable[newIndex] = head;
                head = next;
            }
        }
        hashTable = newHashTable;     // re-assign old hash table to new hash table
    }
}

Complexity Analysis

The hash set uses separate chaining to handle collisions, storing elements in linked lists within each bucket. Operations like add, remove, and contains are generally O(1) on average when keys are well-distributed.

In the worst case, when all keys hash to the same bucket, operations degrade to O(k), where k is the number of elements in that bucket as we have already mentioned before.

The hash table resizes (doubles in capacity) when the load factor reaches 0.75, which ensures low collision probability.

Resizing is O(n) but occurs infrequently, so its cost is amortized over multiple operations.

Space complexity accounts for both the hash table array (m buckets) and all inserted elements (n keys).

Time Complexity Table

Operation	Average Case	Worst Case
`add()`	O(1) (amortized)	O(k)
`remove()`	O(1) (amortized)	O(k)
`contains()`	O(1) (amortized)	O(k)

Space Complexity Table

Component	Space Used	Explanation
Hash Table Array	O(m)	`m` is the number of buckets (doubles on resize)
Stored Elements	O(n)	Each inserted key is stored as a node in a linked list
Total Space	O(n + m)	Accounts for both table size and number of elements

Possible Improvements

In production-grade hash tables like Java's HashMap, buckets that exceed a certain threshold (typically 8 nodes) are converted from linked lists into balanced trees (e.g., red-black trees) to improve worst-case lookup time from O(k) to O(log k), where k is the total number of elements in the bucket.

Memory usage can be further optimized by shrinking the hash table when the load factor drops below a lower threshold (commonly 0.25), which helps avoid wasted space after many deletions.

Advanced hash functions or open addressing (e.g., linear probing, quadratic probing) could be explored as alternatives to separate chaining, though they come with their own trade-offs.

If you found this breakdown helpful or took a different approach to designing HashSet, I’d love to hear your thoughts!
Feel free to drop a comment, leave a ❤️, or share how you'd optimize it further.

Follow me for more deep dives into LeetCode design problems and backend engineering concepts.