[prev] [index] [next]

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