Hash tables - Data Structures and Problem Solving Using Java - page 804

IN PRACTICE
20.12

Implement linear probing.

For the probing hash table, implement the rehashing code without
making a recursive call to add .

20.13

Experiment with a hash function that examines every other character
in a string. Is this a better choice than the one in the text? Explain.

20.14

Experiment with the following alternative for line 12 in Figure 20.2:

20.15

hashVal = ( hashVal << 5 ) ^ hashVal ^ key.charAt( i );

Provide a complete implementation of HashSet using separate chaining.

20.16

PROGRAMMING PROBLEMS
20.17

Find yourself a large online dictionary. Choose a table size that is
twice as large as the dictionary. Apply the hash function described in
the text to each word, and store a count of the number of times each
position is hashed to. You will get a distribution: Some percentage of
the positions will not be hashed to, some will be hashed to once, some
twice, and so on. Compare this distribution with what would occur for
theoretical random numbers (discussed in Section 9.3).

Perform simulations to compare the observed performance of hashing
with the theoretical results. Declare a probing hash table, insert
10,000 randomly generated integers into the table, and count the aver-
age number of probes used. This number is the average cost of a suc-
cessful search. Repeat the test several times for a good average. Run it
for both linear probing and quadratic probing, and do it for final load
factors 0.1, 0.2, ..., 0.9. Always declare the table so that no rehashing
is needed. Thus the test for load factor 0.4 would declare a table of
size approximately 25,000 (adjusted to be prime).

20.18

Compare the time required to perform successful searches and inser-
tions in a separate chaining table with load factor 1 and a quadratic
probing table with load factor 0.5. Run it for simple integers, strings,
and complex records in which the search key is a string.

20.19

A BASIC program consists of a series of statements, each of which is
numbered in ascending order. Control is passed by use of a goto or
gosub and a statement number. Write a program that reads a legal
BASIC program and renumbers the statements so that the first starts at
number F and each statement has a number D higher than the previous

20.20