(^118) | Chapter 5: Searching
store all of thenelements from the original collection. When this happens, it is
common forAto store a set of elements (typically in a linked list) in each of itsb
bins, as shown in options “store elements” and “store keys” in Figure 5-4.*
Improper hash function design can lead to poor distribution of the keys in the
primary storage. A poorly designed hash function has two consequences: many
slots in the hash table may be unused—wasting space—and there will be many
collisions where the keys map into the same slot, which worsens performance.
There will inevitably be collisions with keys with most input. The collision-handling
strategy has a significant impact on a search algorithm’s performance, especially
as the expected number of collisions increases.
Input/Output
To search for a target itemt, it must have one or more properties that can be used
as a keyk; these keys determine the universeU. Unlike BINARYSEARCH, the orig-
inal collectionCdoes not need to be ordered. Indeed, even if the elements inC
Figure 5-4. General approach to hashing
- Alternatively, if the elements themselves are stored directly inA(as shown by the “store elements,
no lists” option in Figure 5-4), then you need to deal with collisions; otherwise, elements inserted
into the hash table may be lost.
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