Algorithms in a Nutshell

Hash-based Search | 123

Searching

Our algorithm then requires approximately 4.6 times the space required for the

characters in thestrings. One might argue that this is the price of using the classes

in the JDK. The engineering tradeoff must weigh the simplicity and reuse of the

classes compared to a more complex implementation that reduces the memory.

When memory is at a premium, you can use one of several variations discussed

later to optimize the memory usage. If, however, you have available memory, a

reasonable hash function that does not produce too many collisions, and a ready-

to-use linked list implementation, the JDK solution is usually acceptable.

As long as the hash function distributes the elements in the collection fairly

evenly, hash-based searching has excellent performance. The average time

required to search for an element is constant, or O(1).

There are other forces that affect the implementation. The major ones deal with

the static or dynamic nature of the collection. In our example, we know how big

our word list is, and we are not going to add or remove words from the list—at

least not during a single program execution. If, however, we have a dynamic

collection that requires many additions and deletions of elements, we must

choose a data structure for the hash table that optimizes these operations. Our

collision handling in the example works quite well since inserting into a linked list

can be done in constant time and deleting an item is proportional to the length of

the list. If the hash function distributes the elements well, the individual lists are

relatively short.

Solution

There are two parts to the solution for HASH-BASEDSEARCH. The first is to create

the hash table. The code in Example 5-7 shows how to use linked lists to hold the

elements that hash into a specific table element. The input elements from collec-

tionC are retrieved using anIterator.

Example 5-7. Loading the hash table

public void load (Iterator<V> it) {

listTable = (LinkedList<V>[]) new LinkedList[tableSize];

// Pull each value from the iterator and find desired bin h.

// Add to existing list or create new one into which value is added.

while (it.hasNext( )) {

V v = it.next( );

int h = hashMethod.hash(v);

if (listTable[h] == null) {

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

}

// Add element into linked list for bin 'h'

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

list.add(v);

}

}

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