src.pydasa.structs.tools.hashing
================================

.. py:module:: src.pydasa.structs.tools.hashing

.. autoapi-nested-parse::

   Module helpers.py
   ===========================================

   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:

       #. Algorithms, 4th Edition, Robert Sedgewick and Kevin Wayne.
       #. Data Structure and Algorithms in Python, M.T. Goodrich, R. Tamassia, M.H. Goldwasser.



Functions
---------

.. autoapisummary::

   src.pydasa.structs.tools.hashing.mad_hash


Module Contents
---------------

.. py:function:: 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

   :param key: key to calculate the index in the Hash table, Can be any native data type in Python or user-defined.
   :type key: Hashable
   :param scale: line slope of the compression function.
   :type scale: int
   :param shift: offset of the compression function.
   :type shift: int
   :param prime: prime number much greater than the capacity of the Hash table.
   :type prime: int
   :param mcap: size of the Hash table, it is a prime number to avoid collisions.
   :type mcap: int

   :returns: the index of the element in the Hash table.
   :rtype: int