think like dictionaries / objects in Python, JS etc.

ordered and associative containers

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

hashing

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