double hash Algorithm
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs use an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.
In January 1953, Hans Peter Luhn write an internal IBM memorandum that used hashing with chaining. gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel implemented a plan use hashing at about the same time. open addressing with linear probing (relatively prime stepping) is credited to Amdahl, but Ershov (in Russia) had the same idea.
#!/usr/bin/env python3
from hash_table import HashTable
from number_theory.prime_numbers import next_prime, check_prime
class DoubleHash(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)
if not check_prime(value % self.size_table)
else value % self.size_table
) # gt = bigger than
return next_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):
i = 1
new_key = self.hash_function(data)
while self.values[new_key] is not None and self.values[new_key] != key:
new_key = (
self.__hash_double_function(key, data, i)
if self.balanced_factor() >= self.lim_charge
else None
)
if new_key is None:
break
else:
i += 1
return new_key
