Algorithms in a Nutshell

(^124) | Chapter 5: Searching
Note how the table is composed oftableSizebins, each of which is of type
LinkedList.*Also note how the table stores the actual objects from the collec-
tionC in the chained link lists of the hash table rather than just the key values.
Searching the table for elements now becomes trivial. The code in Example 5-8 does
the job. Once the hash function returns an index into the hash table, we look to see
whether the table bin is empty. If it’s empty, we returnfalse, indicating that the
searched-for string is not in the collection. Otherwise, we search the linked list at
that bin to determine the presence or absence of the searched-for string.
Note that thehashfunction ensures that the hash index is in the range [0,table-
Size). With thehashCodefunction for theStringclass, the hash function must
cover the case when the integer arithmetic inhashCodeoverflows and returns a
negative number. This is necessary because the modulo operator (%) returns a
negative number if given a negative value.†For example, using the JDKhashCode
method forString objects, the string “aaaaaa” returns the value –1,425,372,064.
Consequences
Perhaps more than any other search method, HASH-BASEDSEARCHexhibits the
consequences of the design decisions we make when selecting the data structure
to store the elements in the collection. It is imperative to understand the dynamic
properties of the input and choose the structure accordingly.
Analysis
HASH-BASEDSEARCHhas excellent performance characteristics. We analyze it in
parts. The components to searching for an element in a hash table are:

• Computing the hash value


• Accessing the item in the table indexed by the hash value


• Finding the specified item in the presence of collisions

*<V> is the typed parameter for theHashTable to allow it to store any type of element.

Example 5-8. Searching for an element

public boolean search (V v){

int h = hashMethod.hash(v);

LinkedList<V> list = (LinkedList<V>) listTable[h];

if (list == null) { return false; }

return list.contains(v);

}

// The following is the implementation of the hash method above.

int hash(V v){

int h = v.hashCode( );

if (h < 0) { h = 0 - h; }

return h % tableSize;

}

† In Java, the expression –5%3 is equal to the value –2.

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

Licensed by

Ming Yi