Espresso: A Concentrated Introduction to Java
Summary: In this laboratory, you will explore hash tables, which can be used to implement the Dictionary ADT.
Contents
a. Copy the following files into your directory
/home/username/CSC152/Eclipse/Code/username/dict:
b. Start Eclipse.
c. In Eclipse, in the Package Explorer, highlight the package
username.dict in your Code project, and
then select Refresh from the File menu. The two new classes
should appear in the package.
a. Read through the the file LinearProbeHashTable.java.
Do you understand how the methods work?
b. Read through TestHash.java, and use it to
test the hash table.
You may have noticed that the method
LinearProbeHashTable.rehash is not currently used. As it
stands, there is no mechanism in place to ensure that the hash table has
enough room to add new elements.
Modify the method put such that it calls rehash
whenever the load factor of the hash table (i.e., the
fraction of table elements that are used) becomes greater than 0.5.
As it stands, there is also no way to remove elements from the table. In this exercise, you will fix that problem. You might want to try this on your own, but look at the following list of modifications if you are not sure how to proceed. Several methods will need to be modified.
a. Write a method public void remove(K key) that implements
"lazy deletion". In other words, instead of actually removing an element
from the table, it sets the corresponding element in the
array deleted to true. Should the value of the
variable n be decremented?
b. Modify the method dump such that it prints "<deleted>"
next to table elements that have been "deleted" by the remove
method.
c. Modify the method put to handle the case in which
probeForKey returns the position where key was
found, but key has been "deleted" from the table. In this
case, put should update the value field and
clear the "deleted" flag.
d. Modify the method get to handle the same case. Here,
get should throw an exception if probeForKey
returns the position where key was
found, but key has been "deleted" from the table.
e. Modify the method rehash. Any elements that have been
"deleted" from the table should not be inserted into the new hash
table. Given that, you may need to adjust the count of the number of
elements in the table. You will also want to consider how the array
deleted should be handled.
f. Write a new test class. It should generate a
LinearProbeHashTable, insert some elements, remove at least
one element, and then insert enough elements to cause the table to be
rehashed. It should also dump the values to the screen at
various points so you can ensure that the table is working correctly.
As it stands, the method rehash always doubles the size of the
hash table. This is not a good practice since it is preferable for the size
of a hash table to be a prime number.
Write a method int nextPrime(int n) that returns the next
prime number that is greater than or equal to n. Use this
method in rehash to ensure that the size of the hash table is
always prime.