Professor Recitation
Hashing Instead of allocating a lot of space, let’s allocate less space.
Store the items in a smaller dynamic direct access array with m = O(n) slots instead of u.
Why dynamic? m grows and shrinks depending on the number of items.

Two solutions are possible to avoid collision.
3.1 Division hash function
h(k) = k mod m
If it is uniform, this is a good idea. However, what if all keys have the same reminder.
This is a terrible choice.
How about randomly choose the hash function?
3.2.Universal hash function
hab(k) = ((ak+b)mod p)mod m
H(p,m) = {hab(k)| $a, b \in [0,1,…p-1]$} where a!=0 (a,b are random integers, p is the prime number greater than the range of keys, and m is the size of the hash table)

Understanding through Examples

Implementation using C++