src.pydasa.structs.tools.hashing#

Module with utility functions for handling memory allocation in the Data Structures of PyDASA.

Module with utility functions for handling data in the maps of PyDASA. Specifically for Separate Chaining and Linear Probing Hash Tables.

IMPORTANT: based on the implementations proposed by the following authors/books:

  1. Algorithms, 4th Edition, Robert Sedgewick and Kevin Wayne.

  2. Data Structure and Algorithms in Python, M.T. Goodrich, R. Tamassia, M.H. Goldwasser.

Functions#

mad_hash(key, scale, shift, prime, mcap)

mad_hash() function to compress the indices of the Hash tables using the MAD (Multiply-Add-and-Divide) method.

Module Contents#

src.pydasa.structs.tools.hashing.mad_hash(key, scale, shift, prime, mcap)#

mad_hash() function to compress the indices of the Hash tables using the MAD (Multiply-Add-and-Divide) method.

MAD is defined as: mad_hash(y) = ((a*y + b) % p) % M, where:

a (scale) and b (shift) are random integers in the range [0,p-1], with a > 0 p (prime) is a prime number greater than M, M (capacity) is the size of the table, prime

Parameters:

  • key (Hashable) – key to calculate the index in the Hash table, Can be any native data type in Python or user-defined.

  • scale (int) – line slope of the compression function.

  • shift (int) – offset of the compression function.

  • prime (int) – prime number much greater than the capacity of the Hash table.

  • mcap (int) – size of the Hash table, it is a prime number to avoid collisions.

Returns:

the index of the element in the Hash table.

Return type:

int