# An Implementation of Hash Tables Chaining with Doubly Linked Lists

A hash table is a data structure that stores items in an array of buckets/ slots. It has a hash function that takes a key as an input and generates a hash code as an output. The hash code represents an index into an array of buckets. We put the value of the key at that index. To handle collisions, i.e., when multiple keys get mapped to the same index, we use the separate chaining method. Now, each array item points to a linked list that contains (key, value) pairs. Moreover, nodes in the same linked list have the same hash code (index). The linked list that we will use is a doubly-linked list, which is similar to the implementation of hash tables using a singly linked list, except now every node will have access to the previous node and the next node. This implementation allows us to do a faster addition and deletion. Consider the following example. Suppose we want to delete the node with value 5, and we have also been given this node. To remove it, we need access to its previous node. For a singly linked list, we would have to traverse the list from the start to get the node with value 4. Therefore, the time complexity will be O(n). However, for a doubly-linked list, we have access to the previous node through the given node, and thus, we can perform deletion in O(1) time.

## Implementation of Hash Tables Chaining with Doubly Linked Lists

Let’s now go ahead and implement hash tables chaining with doubly-linked lists. It will have the following functionalities.

• Insert: It takes a key and a value. If the key already exists, then it updates the value. Otherwise, it adds a new item.
• Delete: It takes a key and removes an item with that key. It also returns the value of the deleted item. If no element with the given key exists, it throws an error.
• Search: The input is a key, and the output is the value of that key. If not found, then an error gets thrown.
• Traverse: It displays all (key, value) pairs.

The code is given below.

```class Node:
def __init__(self, key=None, value=None, next=None, prev=None):
self.key = key
self.value = value
self.next = next
self.prev =  prev

#implementation of doubly linked list for the hash table
def __init__(self):

#add or update a node, return 0 if node added and 1 if node updated
def insert(self, key, value):

if self.head == None: #if list is empty insert a node at the start
return 0
else:
#iterate through the list till last node is found or key already exists
while temp.next:
if temp.key == key: #update value if key already exists
temp.value = value
return 1
else:
temp = temp.next

if temp.key == key: #update value if key already exists
temp.value = value
return 1
temp.next = Node(key, value, prev=temp) #adding a new node
return 0

#find a node with the key in the list or throw an error
def search(self, key):
#iterate through the list
while temp:
if temp.key == key:
return temp.value
else:
temp = temp.next

raise KeyError(f'Item with the key {key} does not exist')

#remove the node with the given key from the list or throw an error
def delete(self, key):
if self.head: #if the list is not empty
#iterate through the list
while temp:
if temp.key == key: #node found
value = temp.value
if temp.prev:
temp.prev.next = temp.next
else:  #node to be deleted is the first node
if temp.next:
temp.next.prev = temp.prev
del temp
return value
else:
temp = temp.next

raise KeyError(f'Item with the key {key} does not exist')

#traverse the linked list in the forward direction
def traverse(self):
while temp:
print(f"{temp.key}\t{temp.value}")
temp = temp.next

class HashTable:
def __init__(self):
self.capacity = 10 #maximum size of the array of buckets
self.length = 0 #length of inserted items
self.buckets = [LinkedList() for i in range(0, self.capacity)]

#get the length
def len(self):
return self.length

def hash(self, key): #get the index into an array of buckets
return hash(key)%self.capacity

def insert(self, key, value): #insert or update an item
index = self.hash(key) #get the index for the key
if add == 0: #increase the length if new item is added
self.length += 1

def search(self, key): #find the value of the given item
index = self.hash(key)
return self.buckets[index].search(key)

def delete(self, key): #remove the item and return its value
index = self.hash(key)
value = self.buckets[index].delete(key)
if value:
self.length -= 1
return value

def traverse(self): #print all the (key, value) pairs
for i in range(0, self.capacity):
self.buckets[i].traverse()

ht = HashTable() #create a hash table
print("Length:", ht.len())

ht.insert("ashton", 99) #add a new item
ht.insert("agar", 87) #add a new item
ht.insert("ar", 87) #add a new item
ht.insert("arr", 70) #add a new item
ht.insert("emily", 90) #add a new item
ht.insert("agar", 89) #update

key = "emily"
print(f"The score of {key} is {ht.search(key)}") #searching score

print(f"The score of deleted item with name/key {key} is {ht.delete(key)}") #deleting item

print("Length:", ht.len())

print("\nGet all items\n")
ht.traverse()
```

Output

```Length: 0
The score of emily is 90
The score of deleted item with name/key emily is 90
Length: 4

Get all items

ashton	99
agar	89
ar	87
arr	70
```

Back to: Data Structure > Data Structure - Linked List