Java Reference
In-Depth Information
5.
Imagine a collection of names that are instances of the class
Name
, as modified in Exercise 1 of Chapter 21. For
each name, imagine a string that represents a nickname. Suppose that each nickname is a search key, and you plan
to add nickname-name pairs to a dictionary that is an instance of the class
HashMap
, as described in Segment 22.18.
a.
Suppose that you plan to add 1000 entries to this dictionary. Create an instance of the class
HashMap
that
can accommodate the 1000 entries without rehashing.
b.
Write statements that add four nickname-name pairs to your dictionary. Then write statements that retrieve
and display the name that corresponds to a nickname of your choice.
6.
Can you use a hash table to implement a priority queue? Explain.
P
ROJECTS
1.
Implement the ADT dictionary by using hashing and separate chaining. Use a chain of linked nodes as each
bucket. The dictionary's entries should have distinct search keys.
2.
Repeat Project 1, but use the ADT list for each bucket instead of a chain of linked nodes. What implementation of
the list would be reasonable?
3.
Implement the class
PatientDataBase
, that you designed in Project 3 of the previous chapter. Use a hash table to
store the patient records. Write a main program that demonstrates and tests this class.
4.
Even though two implementations of a hash table may require the same average number of comparisons, their
distributions may be different. The following experiment will examine this possibility for linear probing and
double hashing. You will need two disjoint lists of names: one with at least 1000 names and the other with at least
10,000 names.
a.
For both of the collision resolution schemes linear probing and double hashing, determine the load
factor that results in an average of 1.5 comparisons for an unsuccessful search of a hash table holding
100 objects. From the load factor, determine the size of the table required.
b.
Create two hash tables of the appropriate size and two corresponding empty lists, which will hold counts.
Use linear probing for one table and double hashing for the other. Inside a loop that iterates 1000 times, do
the following:
●
Clear the hash tables.
●
Randomly choose 100 names from the list of 1000 and insert them into the tables.
●
Randomly choose 100 names from the list of 10,000 and search the tables for each name. (Each
search will be unsuccessful because the two lists have no names in common.)
●
Count the number of comparisons made in each table for the 100 searches and record the count in
the list corresponding to the table.
After the iteration is complete, each list should contain 1000 values. Each of these values is the total number of
comparisons required to search for 100 names. Compute and display the average and standard deviation of each
list. We expect the average number of comparisons for both hash tables to be equal to 150 (1.5 times 100).
5.
Modify the previous project as follows:
Let the user enter the desired average number of comparisons.
●
Display a histogram of the results. A histogram shows the frequency of data values in given intervals
of the same length. Use the floor of the average number of comparisons as the interval length.
●
6.
Chapter 1 defined a set as a bag that does not permit duplicate entries. Define a class of sets that uses a hash table
to store a set's entries.
