Hash-table principles (1)
If a map’s keys are small integers, we can represent the map by a key-indexed array. Search, insertion, and deletion then have time complexity O(1).
Can we approach this performance with keys of other types? Yes!
Hashing: translate each key to a small integer, and use that integer to index an array.
A hash table is an array of m buckets, together with a hash function hash(k) that translates each key k to a bucket index (in the range 0…m–1).