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)
else:
# 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
return
if curr.next is None:
break
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:
return
if curr.key == key:
self.table[index] = curr.next
else:
while curr:
if curr.key == key:
prev.next = curr.next
return
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'
hash_map.remove(2)
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
else:
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.