think like dictionaries / objects in Python, JS etc.
structures such as linked lists, arrays, trees etc. are ordered containers
we can give each element an ‘index’
associative containers map ‘keys’ to various values, and there is no sense of order
keys are typically strings
we can convert our key into a number via a hash function ‘h’ — this is called hashing
then subsequently store the value in an array
our hash function needs these requirements:
h(x) will always return the same value for a given x (i.e., if x = y, h(x) = h(y))
h(x) will always return unique values for different inputs (i.e., if x ≠ y, h(x) ≠ h(y) for all x, y)
hash table ADT & functions
hash table implementation