double_hash.py

#!/usr/bin/env python3
"""
Double hashing is a collision resolving technique in Open Addressed Hash tables.
Double hashing uses the idea of applying a second hash function to key when a collision
occurs. The advantage of Double hashing is that it is one of the best form of probing,
producing a uniform distribution of records throughout a hash table. This technique
does not yield any clusters. It is one of effective method for resolving collisions.

Double hashing can be done using: (hash1(key) + i * hash2(key)) % TABLE_SIZE
Where hash1() and hash2() are hash functions and TABLE_SIZE is size of hash table.

Reference: https://en.wikipedia.org/wiki/Double_hashing
"""

from .hash_tableimportHashTable
from .number_theory.prime_numbersimportis_prime, next_prime


classDoubleHash(HashTable):
"""
 Hash Table example with open addressing and Double Hash
 """

def__init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)

def__hash_function_2(self, value, data):
next_prime_gt= (
next_prime(value%self.size_table)
ifnotis_prime(value%self.size_table)
elsevalue%self.size_table
 ) # gt = bigger than
returnnext_prime_gt- (data%next_prime_gt)

def__hash_double_function(self, key, data, increment):
return (increment*self.__hash_function_2(key, data)) %self.size_table

def_collision_resolution(self, key, data=None):
"""
 Examples:

 1. Try to add three data elements when the size is three
 >>> dh = DoubleHash(3)
 >>> dh.insert_data(10)
 >>> dh.insert_data(20)
 >>> dh.insert_data(30)
 >>> dh.keys()
 {1: 10, 2: 20, 0: 30}

 2. Try to add three data elements when the size is two
 >>> dh = DoubleHash(2)
 >>> dh.insert_data(10)
 >>> dh.insert_data(20)
 >>> dh.insert_data(30)
 >>> dh.keys()
 {10: 10, 9: 20, 8: 30}

 3. Try to add three data elements when the size is four
 >>> dh = DoubleHash(4)
 >>> dh.insert_data(10)
 >>> dh.insert_data(20)
 >>> dh.insert_data(30)
 >>> dh.keys()
 {9: 20, 10: 10, 8: 30}
 """
i=1
new_key=self.hash_function(data)

whileself.values[new_key] isnotNoneandself.values[new_key] !=key:
new_key= (
self.__hash_double_function(key, data, i)
ifself.balanced_factor() >=self.lim_charge
elseNone
 )
ifnew_keyisNone:
break
else:
i+=1

returnnew_key


if__name__=="__main__":
importdoctest

doctest.testmod()