CIT 594 Assignment 4: Bucket Hash
Spring 2014, David Matuszek

Purposes of this assignment

• To give you experience with generics and casting
• To familiarize you with hash tables and other Maps
• To give you experience implementing linked lists

General idea of the assignment

Implement your own version of a hash map, using your own implementation of a linked list.

A bucket hash consists of an array of lists. Since we are using this as a map, each entry will consist of a key and a value. To insert or look up an entry, a hash code is applied to the key, and this specifies which array location contains the appropriate list; then that list is searched to find an entry with the given key.

In more detail

Overall structure

public class BucketHash<K, V> implements Map<K, V> {
    private int numBuckets = 101;
    private Object[] buckets = new Object[numBuckets];

    // The two standard constructors for any Map implementation
    // All the methods required to implement the Map interface

    // Plus all the following...
    public boolean equals(Object o)
    public int hashCode()
    Bucket getBucket(K key)
    private int getIndex(Object o) // optional

    class Bucket
        ListNode header = null;
        private class ListNode 
            ListNode(K key, V value, ListNode next) // Constructor
        }
        public Bucket() // Constructor
        public int size()
        public V get(K key)
        private ListNode find(K key) // optional
        public V put(K key, V value)
        public V remove(K key)
        public Set<K> keySet()
        public Collection<V> values()
        public String toString() // optional
    }
}

The BucketHash class

Your BucketHash class implements the Map interface and all the methods that it requires, plus an equals method and a hashCode method (inherited from Object, not from Map), along with a getBucket method used for testing. getBucket(key) returns the bucket associated with the given key; this allows the methods in the Bucket class to be tested.

All classes and methods, even the private ones, should have good Javadoc comments. If you start with the BucketHash class and allow Eclipse to "Add unimplemented methods," the Javadoc comments that it supplies for these methods (all of which have the form @see something) can be left as is, except for the imperfectly implemented methods (see below). If a method is not fully implemented, its actual behavior should be documented in its Javadoc.

The Java Platform API documentation for the Map interface specifies the constructors and methods you should implement. There are three exceptions: The keySet method should return a Set<K> rather than a set view; the values method should return a Collection<V> rather than a collection view; and the entrySet method should throw an UnsupportedOperationException. For an explanation of "views" (and an understanding of why I've made these changes), see Caution: entrySet() is tricky.

As described in class, Java does not permit an array of generics. Thus, the array buckets is an array of Object, and array elements must be cast to type Bucket (list) in order to be used.

The Bucket class

A "bucket," in this implementation, is a list. The Bucket class contains a single field, header, which is a reference to the first ListNode in the list, or null if the list is empty. All the methods in the Bucket class start from this header. Many of the methods are very similar to the methods in BucketClass; for example, the size() method in Bucket returns the number of entries in this particular list, while the size() method in BucketClass returns the total number of entries in all the lists.

Here is a brief summary of the methods in Bucket:

• public Bucket() Constructor, sets header to null.
• public int size() returns the number of key/value pairs in this list.
• public V get(K key) returns the value associated with this key, or null if the key is not present.
• private ListNode find(K key) (optional) returns the ListNode containing the key, or null. Useful as a helper method for some of the other methods.
• public V put(K key, V value)
  • If the key is already in this list, replaces its value with the new value, and returns the value previously associated with the key.
  • If the key is not present in this list, adds the key/value pair to this list and returns null.
  • Null keys and values are not permitted, so throw an exception if either is null.
• public V remove(K key)
  • If the key is in this list, deletes the key/value entry, and returns the value that was associated with the key.
  • If the key is not present in this list, returns null.
  • Note: This is the most logically complex operation. Keep in mind that removing the first node in a list is different than removing any other node.
• public Set<K> keySet() returns some kind of Set (not a view) of the keys in this list.
• public Collection <V> values() returns some kind of Collection (not a view) of the values in this list.
• public String toString() (optional) returns a human-readable string representation of this list, helpful when debugging.

The Bucket class is an inner class of BucketHash, thus the type variables K and V (for key and value) are already defined, and can be used freely in method definitions. Bucket is used only inside BucketHash, and ideally should also be private, but instead has package visibility so that the methods within it can be tested.

The ListNode class

ListNode is a private inner class of Bucket, and consists entirely of three fields and a constructor to set them, so testing it isn't really necessary.

General requirements

• Use good programming style--proper Java formatting, good variable names, DRY, etc.
• JUnit test all accessible (non-private) methods.
• Write proper Javadoc comments for all classes, interfaces, constructors, and methods, even the private ones.
  • Exception: You don't need to add Javadoc comments to self-explanatory JUnit test methods.
  • Generate the Javadoc, review it, and include it in your assignment submission.
• Before you begin programming, read over then assignment, then estimate how long it will take you. Turn in a readme.txt file containing both your estimate and the time it actually took you.
  • Note: The purpose of this requirement is to give you practice estimating how long your assignments will take. The actual numbers are not used in grading.
• Except by special arrangement in very unusual circumstances, all projects are to be turned in via Canvas.
  • Zip the entire project to turn it in.
  • Assignments submitted by email will be ignored.

Due date