Algorithms in a Nutshell

Hash-based Search

The previous sections on searching apply in specific cases that require a small number of elements (Sequential Search) or an ordered collection (Binary Search). We need more powerful techniques for searching larger collections that are not necessarily ordered. One of the most common approaches is to use a hash function to transform one or more characteristics of the searched-for item into a value that is used to index into an indexed hash table. Hash-based searching has better average-case performance than the other search algorithms described in this chapter. Many books on algorithms discuss hash-based searching under the topic of hash tables (Chapter 11 in Cormen et al., 2001); you may also find this topic in books on data structures that describe hash tables.

In Hash-based Search (Figure 5-3), the n elements of a collection C are first loaded into a hash table A that has b bins. The concept of a key enables this to happen. Each element e∈C can be mapped to a key value k=key(e) such that if e_i=e_j then key(e_i)=key(e_j).^[14] A hash function h=hash(e) uses the key value key(e) to determine the bin A[h] into which to insert e, where 0≤h<b. Once the hash table A is constructed, then searching for an item t is transformed into a search for t within A[h] where h=hash(t).

Figure 5-3. Hash-based Search fact sheet

The general pattern for hash-based searching is shown in Figure ...