Espresso: A Concentrated Introduction to Java

Laboratory: Hash Tables

Summary: In this laboratory, you will have an opportunity to enhance your understanding of hash tables.


Required Code Files:


Exercise 0: Preparation

a. If you haven't done so already, create a package named username.dict.

b. Put all of the files linked above in that package.

c. Make sure to change the package name in each file.

Exercise 1: Testing, Phase I

Write a main class, TestHT that conducts a test using NewDictTester.

If the hash table fails to work, note how and be prepared to discuss it with your classmates.

Exercise 2: Printing

You may have noted that the dump method is not fully implemented in HashTable. Implement it. Your output should provide the key/value pairs in each bucket.

Exercise 3: Testing, Revisited

As you learned in a previous lab, it is often more useful to test by entering the test values on the command line. Write a new test main class, TestHashTable, that uses strings entered on the command line as the key and the corresponding position as the value. For example, given command-line arguments of alpha, beta, delta, alpha should map to 0, beta to 1, and delta to 2.

Try building and dumping a hash table with approximately 20 elements.

Exercise 4: Order of Insertion

In binary search trees, the order in which we insert values has a significant effect on the efficiency of the tree. What effect, if any, does order of inseration have in hash tables?

Exercise 5: Another Hashfunction

Design a class, MyString that includes one field, contents, a string, and three methods, hashCode, toString, and equals.

As you might gueess, toString should return the contents filed and equals should use the String equals method on the contents field. You will write different versions of hashCode. For each version, hash about twenty different strings. Use the same strings in each test and describe the effect on the distribution of values in the hash table.

a. Use the length of the string as the hash code.

b. Use the sum of the ASCII values of the characters in the string as the hash code.

c. Use the sum of the ASCII values of the first five characters in the string as the hash code.

d. Design your own hash code function.

Exercise 6: Deletion

Sketch an algorithm that one could use to delete an element from the hashtable. (You can assume that we provide only the key as a parameter to this method.)

Implement and test that method if you have time and inclination.


Monday, 18 April 2005 [Samuel A. Rebelsky]

This page was generated by Siteweaver on Thu Mar 30 15:24:36 2006.
The source to the page was last modified on Mon Apr 18 10:58:11 2005.
This page may be found at

You may wish to validate this page's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky