Hashing is a mechanism for storing, finding, and eliminating items in near real-time. Double Hashing is accomplished by the use of a hash function, which creates an index for a given input, which can then be used to search the items, save an element, or delete that element from that index.
A hash function is a function that maps data components to their positions in the data structure is utilized.
For example, if we use an array to hold the integer elements, the hash function will create a location for each element such that finding, storing, and deleting operations on the array may be performed in constant time regardless of the number of items in the array.
Take a look at the sample below for a better understanding.
Now we have a difficulty if two integers with the same position are created, for example, elements 1 and 14.
1 % 13 = 1
14 % 13 = 1
So, when we obtain 1, we store it in the first slot, but when we receive 14, we find that spot 1 is already occupied, indicating a collision.
We utilize many collision resolution techniques to handle collisions. Here, we utilize double hashing to resolve collision.
In Double Hashing, instead of one hash function, we have two, and we may utilize a combination of these two functions to produce new positions and determine if the new positions discovered are empty or not.
We use the formula below to determine the new Position.
new_Position = (i*h1(element) + h2(element)) % SIZE;
where I is a prime number
SIZE refers to the hash table’s size.
Must Read ➜ Recursion Function in Python
Double Hashing Program Example
# Program to implement Double Hashing
class doubleHashTable:
# initialize hash Table
def __init__(self):
self.size = int(input(“Enter the Size of the hash table : “))
self.num = 5
# initialize table with all elements 0
self.table = list(0 for i in range(self.size))
self.elementCount = 0
self.comparisons = 0
# method that checks if the hash table is full or not
def isFull(self):
if self.elementCount == self.size:
return True
else:
return False
# method that returns position for a given element
# replace with your own hash function
def h1(self, element):
return element % self.size
# method that returns position for a given element
def h2(self, element):
return element % self.num
# method to resolve collision by quadratic probing method
def doubleHashing(self, element, position):
posFound = False
# limit variable is used to restrict the function from going into infinite loop
# limit is useful when the table is 80% full
limit = 50
i = 2
# start a loop to find the position
while i <= limit:
# calculate new position by quadratic probing
newPosition = (i*self.h1(element) + self.h2(element)) % self.size
# if newPosition is empty then break out of loop and return new Position
if self.table[newPosition] == 0:
posFound = True
break
else:
# as the position is not empty increase i
i += 1
return posFound, newPosition
# method that inserts element inside the hash table
def insert(self, element):
# checking if the table is full
if self.isFull():
print(“Hash Table Full”)
return False
posFound = False
position = self.h1(element)
# checking if the position is empty
if self.table[position] == 0:
# empty position found , store the element and print the message
self.table[position] = element
print(“Element “ + str(element) + ” at position “ + str(position))
isStored = True
self.elementCount += 1
# collision occured hence we do linear probing
else:
while not posFound:
print(“Collision has occured for element “ + str(element) + ” at position “ + str(position) + ” finding new Position.”)
posFound, position = self.doubleHashing(element, position)
if posFound:
self.table[position] = element
self.elementCount += 1
return posFound
# method that searches for an element in the table
# returns position of element if found
# else returns False
def search(self, element):
found = False
position = self.h1(element)
self.comparisons += 1
if(self.table[position] == element):
return position
# if element is not found at position returned hash function
# then we search element using double hashing
else:
limit = 50
i = 2
newPosition = position
# start a loop to find the position
while i <= limit:
# calculate new position by double Hashing
position = (i*self.h1(element) + self.h2(element)) % self.size
self.comparisons += 1
# if element at newPosition is equal to the required element
if self.table[position] == element:
found = True
break
elif self.table[position] == 0:
found = False
break
else:
# as the position is not empty increase i
i += 1
if found:
return position
else:
print(“Element not Found”)
return found
# method to remove an element from the table
def remove(self, element):
position = self.search(element)
if position is not False:
self.table[position] = 0
print(“Element “ + str(element) + ” is Deleted”)
self.elementCount –= 1
else:
print(“Element is not present in the Hash Table”)
return
# method to display the hash table
def display(self):
print(“\n“)
for i in range(self.size):
print(str(i) + ” = “ + str(self.table[i]))
print(“The number of element is the Table are : “ + str(self.elementCount))
# main function
table1 = doubleHashTable()
# storing elements in table
table1.insert(12)
table1.insert(26)
table1.insert(31)
table1.insert(17)
table1.insert(90)
table1.insert(28)
table1.insert(88)
table1.insert(40)
table1.insert(77) # element that causes collision at position 0
# displaying the Table
table1.display()
print()
# printing position of elements
print(“The position of element 31 is : “ + str(table1.search(31)))
print(“The position of element 28 is : “ + str(table1.search(28)))
print(“The position of element 90 is : “ + str(table1.search(90)))
print(“The position of element 77 is : “ + str(table1.search(77)))
print(“The position of element 1 is : “ + str(table1.search(1)))
print(“\nTotal number of comaprisons done for searching = “ + str(table1.comparisons))
print()
table1.remove(90)
table1.remove(12)
table1.display()
Output :
Enter the Size of the hash table : 13
Element 12 at position 12
Element 26 at position 0
Element 31 at position 5
Element 17 at position 4
Collision has occurred for element 90 at position 12 finding a new Position.
Element 28 at position 2
Element 88 at position 10
Element 40 at position 1
Collision has occurred for element 77 at position 12 finding a new Position.
0 = 26
1 = 40
2 = 28
3 = 0
4 = 17
5 = 31
6 = 0
7 = 0
8 = 0
9 = 77
10 = 88
11 = 90
12 = 12
The number of element is the Table are: 9
The position of element 31 is: 5
The position of element 28 is: 2
The position of element 90 is: 11
The position of element 77 is: 9
Element not Found
The position of element 1 is: False
Total number of comparisons done for searching = 12
Element 90 is Deleted
Element 12 is Deleted
0 = 26
1 = 40
2 = 28
3 = 0
4 = 17
5 = 31
6 = 0
7 = 0
8 = 0
9 = 77
10 = 88
11 = 0
12 = 0
The number of element is the Table are : 7
