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

Purposes of this assignment

Changes

Your project should be named BucketHash, and should include a package bucketHash. All classes, including test classes, should be in this package.

The method getList in the BucketHash class has been renamed to getBucket.

Comments

This assignment requires quite a bit of both generics and casting. Your first task, of course, is to get the program working (that is, pass all your tests, which should be thorough). After that, try to eliminate as many warning messages as you can. A good way to sort through the warning messages (in Eclipse) is Windows → Show view... → Problems.

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:

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

Due date

Turn your assignment in to Canvas before 6 a.m. Friday, February 21. Late programs, even if only a minute late, will be penalized 10 points for the first week. Programs later than a week may or may not be accepted for grading.