Randomization

Hashing is our first example of randomized algorithms, since a hash function is a somewhat random function of the key.

Randomized algorithms can be used to avoid clustering.

As an example, suppose that a table contains an equal number of a and b. The worst case of searching for a b with any predefined strategy is O(n); for example, a linear search would be O(n) if all the a entries are at the front.

If we use a randomized search, though, the expected time is O(1) and the probability of O(n) search is very small. The expected time forms a geometric series: 1 / 2 + 1 / 4 + 1 / 8 + 1 / 16 + ... = 1

• Random delays for retry can prevent collisions.

• Randomized choice of a communication path or server can avoid failures.

• MapReduce randomizes using hashing for load balancing.

• Spies randomize their route to work to avoid assassins.