Storage and Retrieval: An Introduction to Hash Tables and Inheritance

Goals

This laboratory exercise provides practice with two new concepts: hash tables and inheritance.

Hash Tables

The Scheme-based lab on Abstract Data Types created a directory class for names and telephone numbers and utilized methods show, lookup, and add. Program ~walker/java/examples/directory/DirectoryMain1.java achieves the similar operations using some of Java's Hashtable class. In this program, add operation translates directly to put, and lookup translates to get. lookup is related to keys, but is somewhat more complicated.

1. Review program DirectoryMain1.java, specifically focusing on the put and get operations. Also, copy the program to your account, compile it, and run it. Be sure you understand how Hashtable can be used for storage and retrieval of data.

Enumerations

Program ~walker/java/examples/directory/DirectoryMain1.java also illustrates the concept of enumerations −− an idea common to many object-oriented programming languages. The most common use of enumerations involves using an enumeration in a loop to cycle through all elements in a collection.

2. The enumeration of key values typically depends upon the internal ordering of data within the hash table, which in turn depends upon an underlying hash function. Review the listing of names printed. Is there an obvious pattern or ordering? Explain briefly.

3. Modify DirectoryMain1.java, so that it prints all values in the table.

4. Since the enumerations of keys and values are separate, there is no guarantee that the order given by one of these corresponds to the other. Do the enumerations give the same order here? If so, consider this a matter of luck. If not, note it is unsafe to count on such common orderings.

A Simple Directory Class

Now that we have seen how Java's Hashtable might be helpful for a directory, we use it to build a simple directory class SimpleDirectory. A shell for such a class is found at ~walker/java/examples/directory/SimpleDirectory.java . Program ~walker/java/examples/directory/DirectoryMain2.java uses this SimpleDirectory, following the same test cases seen previously for Hashtable.

5. Copy SimpleDirectory.java and DirectoryMain2.java to your account, and compile and run them. Review the code to be sure you understand how both pieces of code work.

6. Within SimpleDirectory, the variable myOut is declared as static, so that only one output object will be created −− regardless of how many SimpleDirectory objects are created.

   Modify DirectoryMain2.java, so that two directories are created (dir and dir1). Add lines to insert names into dir1, to retrieve some numbers, and to print all names.

   What do you think will happen if SimpleDirectory is changed, so that table is static? Run the revised program, and examine the results. Did the program print what you expected? Why or why not?

A More Sophisticated Directory Class

The class ~walker/java/examples/directory/BetterDirectory extends the SimpleDirectory class adding three methods, printNumbers, size, and remove. Program ~walker/java/examples/directory/DirectoryMain3.java provides some test cases for BetterDirectory.

7. Copy, compile, and run BetterDirectory and DirectoryMain3.java. Review the code to check what happens.

8. Modify BetterDirectory.java further to define method isIn which checks whether a given name is in the directory.

9. In defining a derived class, not only can we define new methods, but we can redefine old ones. Write a revised printNames method in BetterDirectory.java, which prints three names to a line. (You will need to add a counter which prints a new line whenever the counter reaches 3 or a multiple.)

An Alternative Directory

The SimpleDirectory and BetterDirectory classes contained a Hashtable as an internal variable. Specific public methods then were defined to provide desired operations: a constructor, add, lookup, printNames, remove, size, and PrintNumbers. Another approach derives a class AltDirectory directly from Hashtable. Since remove and size are already defined in Hashtable, these need not be redefined in AltDirectory.

10. Write your own AltDirectory class, extending Hashtable and containing a constructor and methods add, lookup, printNames, and PrintNumbers.

11. Test your AltDirectory class by modifying DirectoryMain3.java to reference AltDirectory rather than BetterDirectory. (This reference occurs three times −− you should make no other changes to DirectoryMain3.java.) Call your revised testing program DirectoryMain4.java.

Since AltDirectory is a subclass of Hashtable, all operations of Hashtable are available in AltDirectory. In contrast, BetterDirectory contains a Hashtable variable. While this variable can utilize methods of Hashtable, such methods cannot be applied directory to BetterDirectory.

12. The Hashtable class contains an isEmpty() method, which returns true or false according to whether any name-number pairs are stored in the table. Thus, isEmpty() should be already defined in the subclass AltDirectory but not in BetterDirectory. Confirm that this is the case by adding the following lines to both DirectoryMain3.java and DirectoryMain4.java.

    
    // lines to test the isEmpty method for directory dir
    out.println ("Check if the directory is empty: "
                 + dir.isEmpty());
    
    

    Compile and run DirectoryMain3.java and DirectoryMain4.java, and be sure you can explain the results.

Inheritance from a super class provides a collection of methods to a derived class. Suppose some of these methods are not desired in the subclass. Since the methods are already defined in the super class, methods by those names must be present in the subclass. One (inelegant) approach would be redefine the method in the subclass to do nothing. Alternatively, one might try to make the method in the derived class private, so it could not be used by applications.

13. Try each of these approaches to "hide" a previously defined method.

    1. Write method isEmpty() in AltDirectory, so that isEmpty always returns true. Recompile and rerun the program. Describe briefly what happens.

    2. Write method isEmpty() in AltDirectory as a private method which always returns true. Again, recompile and rerun, and describe the result.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-hashtables-inheritance.shtml

created April 16, 2000 last revised March 24, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.