Cover by Gary Pollice, Stanley Selkow, George T. Heineman

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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 eC can be mapped to a key value k=key(e) such that if ei=ej then key(ei)=key(ej).[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).

Hash-based Search fact sheet

Figure 5-3. Hash-based Search fact sheet

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

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required