usrbinenv 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 hash1key i hash2key tablesize where hash1 and hash2 are hash functions and tablesize is size of hash table reference https en wikipedia orgwikidoublehashing hash table example with open addressing and double hash examples 1 try to add three data elements when the size is three dh doublehash3 dh insertdata10 dh insertdata20 dh insertdata30 dh keys 1 10 2 20 0 30 2 try to add three data elements when the size is two dh doublehash2 dh insertdata10 dh insertdata20 dh insertdata30 dh keys 10 10 9 20 8 30 3 try to add three data elements when the size is four dh doublehash4 dh insertdata10 dh insertdata20 dh insertdata30 dh keys 9 20 10 10 8 30 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 hash table example with open addressing and double hash gt bigger than 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
from .hash_table import HashTable
from .number_theory.prime_numbers import is_prime, next_prime


class DoubleHash(HashTable):
    

    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 is_prime(value % self.size_table)
            else value % self.size_table
        )  
        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


if __name__ == "__main__":
    import doctest

    doctest.testmod()