Java Reference
In-Depth Information
11.
Consider data whose search key consists of three floating-point values (longitude, latitude, and altitude, for
example). Suggest at least two possible hash functions for this data.
12.
You have approximately 1000 thumbnail images that you want to store in a dictionary that uses hashing in its
implementation. Each image is 20 pixels wide by 20 pixels high, and each pixel is one of 256 colors. Suggest
some possible hash functions that you could use.
P
ROJECTS
1.
The note at the end of Segment 21.22 describes a dictionary that does not support a remove operation. Implement
this dictionary by using open addressing with linear probing to resolve collisions.
2.
Consider records for patients at a medical facility. Each record contains an integer identification for a patient and
strings for the date, the reason for the visit, and the treatment prescribed. Design and implement the class
PatientRecord
so that it overrides the method
hashCode
. Write a main program that tests your new class.
3.
Design a class
PatientDataBase
that stores instances of
PatientRecord
, as described in the previous project. The
class should provide at least three query operations, as follows. Given a patient identification and date, the first
operation should return the reason for the visit, and the second operation should return the treatment. The third
query operation should return a list of dates, given a patient identification.
4.
The following experiment compares the performance of linear probing and quadratic probing. You will need a list
of 500 names or user names that can be obtained from your instructor or from a system administrator. Implement
a hash table of size 1000, and use the hash code described in Segment 21.8. Count the number of collisions that
occur for both linear probing and quadratic probing when 500 names are added to the table. Repeat the experiment
for tables of size 950, 900, 850, 800, 750, 700, 650, and 600.
5.
Design an experiment similar to the one in Project 4, but instead of comparing linear probing and quadratic
probing, compare two different hash functions.
Write a program that uses hashing to guess which of two choices a user has made.
1
The following sample output
demonstrates an interaction between computer and user:
Choose either A or B, and I will guess your choice.
Press Return when you are ready.
I guess that you chose A; am I right?
no
Score: 0 correct, 1 incorrect
Choose either A or B, and I will guess your choice.
Press Return when you are ready.
I guess that you chose A; am I right?
yes
Score: 1 correct, 1 incorrect
Choose either A or B, and I will guess your choice.
Press Return when you are ready.
I guess that you chose B; am I right?
yes
Score: 2 correct, 1 incorrect
. . .
6.
Initially, your program will make random guesses. After the user makes five choices, your program should
begin to build a hash table that it can use to predict future choices. The last four user choices form a key to the
hash table. The value stored in the table at the hash address represents how many times the user's next choice was
A and how many times it was B. The program uses these counts to make its guess.
For example, if AAAB hashes to an object containing the counts 5 and 2, where 5 is the number of times the
user has chosen A after having chosen A, A, A, and B, the program would predict A as the user's next choice. The
specifics of how your program makes its prediction based on these counts are up to you.
1.
Based on an assignment idea by Raja Sooriamurthi, as given in SIGCSE's Nifty Assignments at
nifty.standford.edu
.
