Program 4

Hash Tables Implementing Maps
Skip Lists Implementing Sets
Adapters from Maps to Sets

Fundamental Data Structures
ICS-23

Introduction This programming assignment is designed to ensure that you know how to write code that processes Hash Tables and Skip Lists. Hash tables are a data structure of a faster complexity class than BSTs for most operations (i.e., O(1)). We will reimplement a Map via a hash table. Skip Lists are are a data structure of the same complexity class as BSTs, but they come with a guarantee that there are no pathological skip lists, and the constant for Skip List operations is typically faster than the constant for BSTs. We will implement a Set via a Skip List. Finally, we will implement an adapter (something like a decorator) that allows us to adapt any implementation of a Map to a Set: using the values of the keys in a Map to represent the values in a Set. The code will be trivial; it delegates each Set operation to similar Map operations: e.g., checking whether a value is in a Set will be delegated to checking if that value is a key in a Map.

When writing your classes, you will run each against my JUnit tests to verify (a bit too strong of a word here) that it is correct. You may also find it useful to test your classes with the DriverForMap or DriverForCollection, which you can run from collections.jar once you build a path to this library in the project. With this driver, you can individually test any methods in your classes interactively, and see their results (returned values and state changes, mostly using toString).

Download and unzip the following Eclipse project Start and use it to start working on this program. For each part of this assignmnment you will update and turn in a single .java file in the project (see the Checkmate submission for this assignment for more details).

Only one student should submit the assignment, but both student's names should appear in the comments at the top of each submitted program. Please turn in each program as you finish it, so that I can accurately assess the progress of the class as a whole during this assignment.

Print this document and carefully read it, marking any parts that contain important detailed information that you find (for review while you work on this assignment and before you turn in the files).

Problem #1: Map via Hash Table In this problem you will write a more efficient version of a map, by implementing it as a hash table. Most hash table operations are O(1), so this improves on the complexity class for most operations in a BST. We will use a trailer list in each bin to store the overflows from all the collisions: we use a trailer list because there is a simple algorithm for removing a node given a reference to it (and not having to determine what comes before that node in the list).

You can test this program with TestMap, a JUnit test (how we will ultimately grade it), and with an updated version of the WordGenerator program (included in the download) from Program #1 part 6, on the file huck.txt (also included in the download). With the DriverForMap program, you can individually test any methods in your classes interactively, and see their results (returned values and state changes, mostly using toString). I will supply a toString method that returns a String that prints showing the structure of the hash table, and reports an error message if it doesn't appear that a bin stores a trailer list.

The HashMap class must implement the Map interface using standard map semantics. You should look at my ArrayMap class, which contains code that implements the same Map interface, some of which (or code like it) will belong in the hash table implementation. Here, the underlying data structure is a hash table, whose node class is complete within the implementation, which also includes some helper methods like hashCompression, locate, and doubleLength; these are either completley written or just their header is specified. Of course, you can also look at the BSTMap class that you write in Programming Assignment #3.

Here are some issues to think about when writing your class.

  1. The constructors specify the maximum load factor; if adding a value to the hash table increases its load factor beyond this maximum (check this after the value is added), double the length of the hash table, rehashing all its values into the new hash table; the compression function should be based on its new length. To ensure that there is some chaining in the bins, the default constructor used by the MapDriver and the JUnit test specifies a load factor of 2.

  2. Create the hash table as an LN[] and cast it to LN<K,V>[]. Store references to new LN<K,V> objects in the hash table.

    In the doubleLength method, first put new trailer nodes in all the bins. Then, unlike my solution in Quiz #5, do add the NODE from the original table into the double-length table: do not construct new LN<K,V> objects in the double-length hash table; reuse the old LN<K,V> objects from the original hash table.

  3. Use trailer lists in each bin in the hash table: this makes some simple operations a bit harder, but it makes some complicated operations (removal) much simpler. Remember, whenever you allocate a hash table (new LN[]) you must store a reference to a trailer node in each bucket: no bin should ever store null. Each trailer should store null in the entry and next instance variable in its LN<K,V> object.

  4. Note that I have written a toString method that can be used to nicely print a hash table: it shows the bins and the linked list of associations/mappings in teach bin; use the t command in the driver program to help debug your methods for adding/deleting from a hash table. Also note, this toString method includes an error if any bin is null (does not contain a trailer node) or if any bucket with a linked list does not end with a trailer (a node whose entry and next instance variables store null). This instrumented version of toString can supply you with valuable debugging information.

  5. The iterator for this method does not need to (and should not) use extra arrays or hash tables. You can iterate through the hash table directly using two variables: one stores which bucket the iterator is in (in case it has to advance to other buckets) and one stores what LN's key/value it will return next (and it will traverse all the values in its chain, but not the trailer node). In HashMap, which uses trailer nodes, remove in the Iterator is fairly straightforward. Ensure that you know the special way to use trailer nodes to simplifiy removal of a value, both in the main remove and the remove in the iterator.

You should also run the updated WordGenerator program, with the large text file (huck.txt) The update allows you to "comment" out code to select either the ArrayMap, BSTMap (and its appropriate comparator), or the HashMap. It also tracks and prints the amount of time needed to build the map: on my machine it took 18 minutes using ArrayMap and 1 second using BSTMap (a speed-up of a factor of over 1,000), when I used an order statistic of 3. Using a HashMap the time reduce to about .5 seconds. All ultimately producing a map that contains 90,705 keys with each key mapping to a list of between 1 and 46 words.

Problem #2: An Adapter for Maps to Set The class SetFromMap is an adapter (similar to a decorator): it has constructors that take any class implementing a Map whose keys are the generic type E and its methods adapt the Map to be used like a Set<E>. Inside SetFromMap the map instance variable, which refers to the Map to which most operations are delegated, is of type Map<E,Object>, which uses E as the key type and Object as the value type (more on using values later). So, if you use SetFromMap it is natural to declared the value type for the Map to be Object (but the adapter will work with other types for values).

Every method call contains one statement, that delegates the Set operations to some similar Map operation on keys. For example, here is the add method. 

  public boolean add(E e) {
    return map.put(e,new Object()) == null;
  }
Which says, to add e to the set, put e in the map as a key with an associated value new Object() (this object is just a necessary placeholder: the value for the key in the map; all keys map to new objects, whose values are almost never used: see below about why we don't just map every key to null).

If the put method returns null it means that e was not already in the map (so it is added to the set); if it returns a non-null value (the Object from a previous put with this key, then that value is already in the set and therefore it is NOT added to the set. Of course add must return whether or not e was added to the set. If we mapped each key to null we couldn't distinguish whether or not the key was already in the map (meaning the value was already in the set).

Likewise, all the other set methods are implemented by delgating to similar map methods. The body of each method is one statement.

You can test your code via the TestSetAdapter JUnit test. It is like the standard Set JUnit test, but it prompts for a Map and then adapts it using SetFromMap. Select which Map implementation you want to adapt: either ArrayMap from the collections.jar library, BSTMap (my solution from Programming Assignment #3), or the HashMap you are writing for this assignment.

Problem #3: Set via Skip List In this problem you will write a Skip List implementation of a set.

You can test this program with TestSet, a JUnit test (how we will ultimately grade it) With the DriverForCollection program (the Set interface inherits all the methods from Collection interface, but unlike the List interface adds no others), you can individually test any methods in your classes interactively, and see their results (returned values and state changes, mostly using toString, which is especially important in this problem). I will supply a toString method that returns a String that prints showing the structure of the Skip List, which reports an error indicate if the Skip List has too few or extra nodes at each level.

The SkipListSet class must implement the Set interface using standard set semantics. You should look at my ArraySet class, which contains code that implements the same Set interface, some of which (or code like it) will belong in the skip list implementation. Here, the underlying data structure is a skip list, whose node class is complete within the implementation (and has an interesting exciseLeftRight method), which also includes some helper methods that I have written: addNewTop, build2x2, linkLeftRight, linkUpDown; and some helper methods you will write: skipSearch, skipInsert, and skipDelete.

We will use Skip List nodes that store a value (the value in the set) and four references: to the Skip List node up, down, left, and right of this one. Skip List nodes will store a value of null for the -inf and +inf nodes, which act as header/trailer nodes in a Skip List. Ensure that you store the correct references in all these instance variables.

Here are some issues to think about when writing your class.

  1. The hasNext and next methods in the iterator traverse the s0 level of the skip list.

  2. The remove method in the iterator can call skipDelete similarly to how the standard remove method calls it.
See the Goodrich and Tamassia book and the comments in my code for more information.