Hashing Flow
-DAA used the space u. How can I shrink the space u to m?
Division Hash Function
Formula: H(k)=kmodm
Problem: Collision between keys
Universal Hash Function
Formula:
hab(k) = ((ak+b)modp)modm
H(p,m) = {hab(k)| a,b (- {0,1,…p-1} where a!=0} a,b: Random integer
p: Prime number
m: Size of HashTable

Hashing Details

[Hashing Introduction] (https://www.geeksforgeeks.org/what-is-hashing/)

Hashing

popular technique for storing and retrieving data as fast as possible. Why to use Hashing?
Searching in Binary tree requires the time complexity O(logn)
In hashing, the above operations take an average time complexity of O(1).
Ex. We want to design a system for storing employee records with phone numbers.
Basic Operations
Hash Table: Create a new Hash Table.
Delete: Delete a perfect key-value pair from the hash table.
Get: Search a key in the hash table and return the value associated with that key.
Put: Insert a new key-value pair inside the hash table.
Delete HashTable: Delete all the HashTable

Hashing components
Hash Table: An array that stores pointers to records corresponding to a given number.
If no existing phone number has function value equal to the index for the entry, hash table is NIL.
Data is stored in a way that is easy to find those terms later if required.
Hash Function: A function that converts a given big phone number to a small practical integer value.
The mapped integer value is used as an index of the hash table.
Its main job is to map each and possible key to a unique slot index. If every key is mapped to a unique slot index, then the hash function is known as a perfect hash function
Collision Handling: Since a hash function gets us a small number of a big key, there is the possibility that two keys result in the same value. A newly inserted key maps to an already occupied slot in the hash table is called a collision and must be handled using collision handling technique.
-Chaining: Make each cell of the hash table to a linked list of records that have the same hash function value.
It is simple, but requires additional memory outside the table.
-Open addressing: All elements are stored in the hash table itself. Each table entry either contains a record or NIL. When searching for an element, we examine the slot one by one until the desire element is found or it is clear that the element is not in the table.

Hashing Code
https://gist.github.com/growingpenguin/5ac7dab9c105de7d4a13738e855e6a48