The TAO of Java


Laboratory: A Simple Dictionary Implementation

Summary: In this laboratory, you will have an opportunity to enhance your understanding of the dictionary by exploring a vector-based implementation of dictionaries.

Contents:

Required Code Files:

Exercises

Exercise 0: Preparation

In this laboratory, you will use a package entitled username.dict.

a. In a terminal window, type

/home/rebelsky/bin/tao dict

You should see messages about files being copied to a temporary directory.

b. Start Eclipse.

c. In Eclipse, build a project named Temp from /home/username/CSC152/Temp.

d. In the Temp project, you should see a package named username.dict. Drag that package to your Code project.

e. Delete the Temp project.

You can now work with the new package.

Exercise 1: A Vector-Based Dictionary Implementation

Look at VectorBasedDict.java, a vector-based implementation of the Dict interface.

a. Describe, in your own words, how this implementation works.

b. What is the purpose of find in this code?

Exercise 2: Preliminary Running Times

Give an approximate but close upper bound on the running time of put and get. You may assume that the add method of the Vector class is a constant time method.

Exercise 3: Testing

Look at DictTester.java, a generic tester for Dict, and TestVBD.java, a tester customized for VectorBasedDict.

a. Explain what the tests do.

b. Compile and run TestVBD and confirm that it produces the results you expect.

Exercise 4: Correcting the Implementation

As you should have observed in the prior problem, the get method works well in most cases, but fails to return the new value when we change the value associated with a key. Why? Because the put method adds a new key/value pair to the end of the vector without first checking to see if vector already contains a key/value pair with the same key and the find method returns the index of the first key/value pair that matches the key.

One way to fix this problem is to change find. Update find so that it correctly finds the most-recently added pair, rather than the least-recently added.

Exercise 5: Re-correcting the Implementation

Of course, another problem with the decision (if it was a decision) to put in multiple key/value pairs is that the get method may have to search through significantly more than n pairs to find a matching key.

A better solution is, of course, to avoid putting two pairs in with the same key. Rewrite put so that it does not put in a second pair.

Exercise 6: Deletion

Update

History

Sunday, 9 April 2006 [Samuel A. Rebelsky]


This page was generated by Siteweaver on Mon Apr 10 11:31:11 2006.
The source to the page was last modified on Mon Apr 10 11:31:09 2006.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/TAO/Labs/dictionaries.html.

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

Samuel A. Rebelsky
rebelsky@grinnell.edu