Home Engineering Double Hashing Technique in Python (With Formula & Examples)

Double Hashing Technique in Python (With Formula & Examples)

Double Hashing

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