usrbinenv python3 basic hash table example with open addressing using quadratic probing quadratic probing is an open addressing scheme used for resolving collisions in hash table it works by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until open slot is found hash 1 hash 2 hash 3 hash n reference https en wikipedia orgwikiquadraticprobing e g 1 create hash table with size 7 qp quadraticprobing7 qp insertdata90 qp insertdata340 qp insertdata24 qp insertdata45 qp insertdata99 qp insertdata73 qp insertdata7 qp keys 11 45 14 99 7 24 0 340 5 73 6 90 8 7 2 create hash table with size 8 qp quadraticprobing8 qp insertdata0 qp insertdata999 qp insertdata111 qp keys 0 0 7 999 3 111 3 try to add three data elements when the size is two qp quadraticprobing2 qp insertdata0 qp insertdata999 qp insertdata111 qp keys 0 0 4 999 1 111 4 try to add three data elements when the size is one qp quadraticprobing1 qp insertdata0 qp insertdata999 qp insertdata111 qp keys 4 999 1 111 usr bin env python3 basic hash table example with open addressing using quadratic probing quadratic probing is an open addressing scheme used for resolving collisions in hash table it works by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until open slot is found hash 1² hash 2² hash 3² hash n² reference https en wikipedia org wiki quadratic_probing e g 1 create hash table with size 7 qp quadraticprobing 7 qp insert_data 90 qp insert_data 340 qp insert_data 24 qp insert_data 45 qp insert_data 99 qp insert_data 73 qp insert_data 7 qp keys 11 45 14 99 7 24 0 340 5 73 6 90 8 7 2 create hash table with size 8 qp quadraticprobing 8 qp insert_data 0 qp insert_data 999 qp insert_data 111 qp keys 0 0 7 999 3 111 3 try to add three data elements when the size is two qp quadraticprobing 2 qp insert_data 0 qp insert_data 999 qp insert_data 111 qp keys 0 0 4 999 1 111 4 try to add three data elements when the size is one qp quadraticprobing 1 qp insert_data 0 qp insert_data 999 qp insert_data 111 qp keys 4 999 1 111
from .hash_table import HashTable


class QuadraticProbing(HashTable):
    

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

    def _collision_resolution(self, key, data=None):
        

        i = 1
        new_key = self.hash_function(key + i * i)

        while self.values[new_key] is not None and self.values[new_key] != key:
            i += 1
            new_key = (
                self.hash_function(key + i * i)
                if not self.balanced_factor() >= self.lim_charge
                else None
            )

            if new_key is None:
                break

        return new_key


if __name__ == "__main__":
    import doctest

    doctest.testmod()