data_structures.hashing.double_hash

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

Classes

DoubleHash

Hash Table example with open addressing and Double Hash

Module Contents

class data_structures.hashing.double_hash.DoubleHash(*args, **kwargs)

Bases: data_structures.hashing.hash_table.HashTable

Hash Table example with open addressing and Double Hash

__hash_double_function(key, data, increment)

__hash_function_2(value, data)

_collision_resolution(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}