Hash Table With Linked List


Hash Table with Linked List, also known as Chaining, is a collision resolution technique used in hash table implementations. It combines the concept of a hash table with that of a linked list to handle collisions that occur when two or more keys map to the same hash value.

In this approach, each bucket or slot of the hash table contains a linked list. When inserting a key-value pair into the hash table, the hash function is used to compute the index or bucket location. If there is no existing key-value pair in that bucket, a new node containing the key-value pair is added to the linked list. If there are already nodes in the linked list, the new node is appended to the end of the list.

When searching for a key in the hash table, the hash function is used again to compute the bucket location. Then, the linked list in that bucket is traversed to find the node with the matching key. If found, the corresponding value is returned.

Now let's see an example implementation of a Hash Table with Linked List in Python:

# Implementation of a Node for the Linked List
class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

# Implementation of a Hash Table with Linked List
class MyHashMap:
    def __init__(self):
        self.size = 1000  # Size of the hash table
        self.table = [None] * self.size

    def _hash(self, key):
        return key % self.size  # Hash function to compute bucket index

    def put(self, key, value):
        index = self._hash(key)
        if self.table[index] is None:
            # If bucket is empty, create a new node and assign it to the bucket
            self.table[index] = ListNode(key, value)
            # If bucket is not empty, traverse the linked list and update the value if key exists
            curr = self.table[index]
            while curr:
                if curr.key == key:
                    curr.val = value
                if curr.next is None:
                curr = curr.next
            curr.next = ListNode(key, value)

    def get(self, key):
        index = self._hash(key)
        curr = self.table[index]
        while curr:
            if curr.key == key:
                return curr.val
            curr = curr.next
        return -1  # Key not found

    def remove(self, key):
        index = self._hash(key)
        curr = prev = self.table[index]
        if not curr:
        if curr.key == key:
            self.table[index] = curr.next
            while curr:
                if curr.key == key:
                    prev.next = curr.next
                prev = curr
                curr = curr.next

# Example usage:
hash_map = MyHashMap()
hash_map.put(1, 'One')
hash_map.put(2, 'Two')
hash_map.put(3, 'Three')
print(hash_map.get(1))  # Output: 'One'
print(hash_map.get(2))  # Output: 'Two'
print(hash_map.get(3))  # Output: 'Three'
print(hash_map.get(2))  # Output: -1 (Key not found)

In this example, we create a class MyHashMap that represents the hash table. It has methods put, get, and remove for inserting, retrieving, and removing key-value pairs, respectively. The _hash method computes the bucket index using a simple modulus operation.

The time complexity of operations in a Hash Table with Linked List depends on the size of the hash table and the number of elements stored in it. In the average case, with a well-distributed hash function and a reasonable load factor, the time complexity is O(1) for all operations. However, in the worst case, when all keys map to the same bucket and the linked list becomes linear, the time complexity can be O(n), where n is the number of elements.

The space complexity of the hash table is O(m + n), where m is the size of the hash table (number of buckets) and n is the number of elements stored in it.

Let's solve a problem using the concept of a Hash Table with Linked List. The problem we'll solve is "Two Sum," where we need to find two numbers in an array that add up to a specific target.

Here's the solution using a Hash Table with Linked List:

class ListNode:
    def __init__(self, key, index):
        self.key = key
        self.index = index
        self.next = None

class Solution:
    def twoSum(self, nums, target):
        # Create a hash table
        size = len(nums)
        table = [None] * size

        for i, num in enumerate(nums):
            complement = target - num
            index = self._hash(complement, size)

            if table[index] is not None:
                # Check the linked list for the complement
                node = table[index]
                while node:
                    if nums[node.index] == complement:
                        return [node.index, i]
                    node = node.next

            # Add the current number to the hash table
            node = ListNode(num, i)
            if table[index] is None:
                table[index] = node
                curr = table[index]
                while curr.next:
                    curr = curr.next
                curr.next = node

        return []

    def _hash(self, key, size):
        return abs(key) % size

In this solution, we create a hash table with a size equal to the length of the nums array. We iterate through the nums array and for each number, we calculate the complement needed to reach the target. We use the _hash function to compute the index in the hash table.

If the index in the hash table is empty, we create a new node and assign it to that index. If the index is not empty, we traverse the linked list at that index to check if any node has the complement as its key. If we find a match, we return the indices of the two numbers. If we reach the end of the linked list without finding a match, we add a new node at the end.

If we complete the loop without finding a valid pair, we return an empty list [].

The time complexity of this solution is O(n), where n is the number of elements in the nums array. This is because in the worst case, we may need to traverse the entire linked list at each index.

The space complexity is O(n) as well, considering the worst case scenario where all elements have different keys and all nodes are stored in the hash table.




Next Post Previous Post