Algorithms in a Nutshell

Hash-based Search | 117

Searching

determine the binA[h] into which to inserte, where 0≤h<b. Once the hash table

Ais constructed, then searching for an itemtis transformed into a search fort

withinA[h] whereh=hash(t).

The general pattern for hash-based searching is shown in Figure 5-4 with a small

example. The components of HASH-BASEDSEARCH are:

• The universeUthat defines the set of possible keys. Each elemente∈Cmaps
  to a keyk∈U.


• The hash table,A, which stores thenelements from the original collectionC.
  Amay contain just the elements themselves or it may contain the key values
  of the elements. There areb locations withinA.


• The hash function,hash, which computes an integer indexhinto the hash
  table usingkey(e), where 0≤h<b.
  There are two main concerns when implementing HASH-BASEDSEARCH: the
  design of the hash function, and how to handlecollisions(when two keys map to
  the same bin inA). Collisions occur in almost all cases whereb<<|U|, that is,
  whenbis much smaller than the number of potential keys that exist in the
  universeU. Note that ifb<nthere won’t be enough space in the hash tableAto

Figure 5-3. Hash-based Search fact sheet

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use