1 Arrays and Strings

Hash Tables

A hash table is a data structure that maps keys to values for highly efficient lookup.

A simple way to implement may be like this:

  1. Compute the key’s hash code. Two different keys could have the same hash code.
  2. Map the hsh ode to an index in the array. Can be done like hash(key) % array_length.

Worst case runtime is O(n). Assume good implementation that keeps collisions to minimum, lookup time is O(1).

Implementing a Hash Table Using Swift

Following Ray Wenderlich