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 a *O(n)* search is very small. The expected
time forms a * geometric series*:
* 1 / 2 + 1 / 4 + 1 / 8 + 1 / 16 + ... = 1 *

- Randomized time delays for retry can prevent collisions.
- Randomized choice of a communication path or server can avoid failures.