Double Hashing Technique in Python (With Formula & Examples)

September 30, 2021

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