• maps keys to integers
• uses some hash(key) function
• each key $k$ has one unique value
  • if entry $(k,v)$ exists, and we try to insert $(k,w)$, the prior will be overwritten

hashing — the process used to convert input data of any size into a fixed-size value or key

hash function — a specific algorithm used in hashing to map data of an arbitrary size to data of a fixed size

hash table — a data structure that implements an associative array abstract data type, thus able to map keys to values

rollinghash algorithm

division method

multiplication method