Hashing
Key-indexed arrays had "perfect" search performance O(1)
- but required a dense range of index values
- used a fixed-size array (max size ever needed)
- bigger array ⇒ more useful but wastes more space
Hashing allows us to approximate this performance, but
- allows arbitrary types of keys
- map (hash) keys into compact range of index values
- store items in array, accessed by index value
|