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.

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
class LinkedList:
  def __init__(self):
    self.head = None
  
  #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
      self.head = Node(key, value)
      return 0
    else:
      temp = self.head
      #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):
    temp = self.head
    #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
      temp = self.head
      #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
              self.head = temp.next
            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):
    temp = self.head
    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
    add = self.buckets[index].insert(key, value) #add an item in the appropriate linked list
    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