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.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Testing, Phase I
  • Exercise 2: Printing
  • Exercise 3: Testing, Revisited
  • Exercise 4: Order of Insertion
  • Exercise 5: Another Hashfunction
  • Exercise 6: Deletion

Required Code Files:

• NewDict.java (the interface)
• NewDictTester.java (a generic tester for NewDict)
• HashTable.java (a simple implementation of hash tables)
• Node.java (nodes that fill the buckets in the hash table)

Exercises

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.

History

Monday, 18 April 2005 [Samuel A. Rebelsky]

• Wrote code and lab.