11
\$\begingroup\$

Here is the implementation of interface Dictionary using chained hash table class HashTableChained.

Despite item 22* saying

Favour static member classes over non static

in Effective Java, I used non static member class DListNode in class DblyLinkList, because any instance of the DListNode class MUST be associated with an instance of the DblyLinkList class. class DListNode is not for the users of class DblyLinkList.

class Entry could have been top level class, without any code change in class HashTableChained. The reason is that class Entry is introduced as a static member class because it avoids breaking encapsulation.

DblyLinkList.java

package JavaCollections.list;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Dlist using sentinel node
 * 
 * @author mohet01
 *
 * @param <T>
 */
public class DblyLinkList<T> implements Iterable<T> {

    /*
     * Representation - starts
     */
    /**
     * DListNode is a node in a DblyLinkList
     * 
     * @author mohet01
     *
     */
    private class DListNode {

        /**
         * item references the item stored in the current node. prev references
         * the previous node in the DList. next references the next node in the
         * DList.
         *
         * Compiler transformation adds access code for private members
         *
         */

        private T item; 
        private DListNode prev;
        private DListNode next;

        DListNode(T item, DListNode p, DListNode n) {
            this.item = item;
            this.prev = p;
            this.next = n;
        }

    }

    private class Itr implements Iterator<T> {

        private DListNode currentPosition = sentinel;

        private int lastRet = -1;

        @Override
        public boolean hasNext() {
            return currentPosition.next != sentinel;
        }

        @Override
        public T next() throws NoSuchElementException {
            if (currentPosition.next == sentinel) {
                throw new NoSuchElementException();
            }
            T nextItem = currentPosition.next.item;
            lastRet = +1;
            currentPosition = currentPosition.next; // points to the node that
                                                    // is already read
            return nextItem;
        }

        @Override
        public void remove() throws NoSuchElementException {
            if (lastRet < 0) {
                throw new IllegalStateException();
            } else {
                // this item is already read using next()
                currentPosition.item = null;
                currentPosition.prev.next = currentPosition.next;
                currentPosition.next.prev = currentPosition.prev;
                currentPosition = currentPosition.prev;
                lastRet = -1;
            }
        }
    }

    /**
     * sentinel references the sentinel node.
     *
     * Being sentinel as part of implementation detail, will avoid null checks,
     * while performing mutable operations on list.
     * 
     * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
     * 
     */
    protected DListNode sentinel;
    protected int size;

    /**
     * newNode() calls the DListNode constructor. Use this class to allocate new
     * DListNodes rather than calling the DListNode constructor directly. That
     * way, only this method needs to be overridden if a subclass of DList wants
     * to use a different kind of node.
     * 
     * @param item
     *            the item to store in the node.
     * @param prev
     *            the node previous to this node.
     * @param next
     *            the node following this node.
     */
    DListNode newNode(T item, DListNode prev, DListNode next) {
        return new DListNode(item, prev, next);
    }

    /*
     * Representation - ends
     * 
     * DblyLinkList invariants: 1) sentinel != null. 2) For any DListNode x in a
     * DblyLinkList, x.next != null. 3) For any DListNode x in a DblyLinkList,
     * x.prev != null. 4) For any DListNode x in a DblyLinkList, if x.next == y,
     * then y.prev == x. 5) For any DListNode x in a DblyLinkList, if x.prev ==
     * y, then y.next == x. 6) size is the number of DListNode's, NOT COUNTING
     * the sentinel (referenced by "sentinel"), that can be accessed from the
     * sentinel by a sequence of "next" references.
     */

    /*
     * User Interface - starts
     */
    /**
     * DblyLinkList() constructor for an empty DblyLinkList.
     */
    public DblyLinkList() {
        this.sentinel = this.newNode(null, this.sentinel, this.sentinel);
    }

    /**
     * Return the size of the linked list
     * 
     * @return
     */
    public int size() {
        return size;
    }

    public void remove(int index) throws NoSuchElementException {
        if (index > size()) {
            throw new NoSuchElementException();
        }
        DListNode node;
        for (node = sentinel; index-- > 0; node = node.next)
            ;
        node.item = null;
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * Inserts a non-sentinel node at front of the list.
     * 
     * @param item
     */

    public void insertFront(T item) {

        DListNode node = this.newNode(item, this.sentinel, this.sentinel.next);
        node.next.prev = node;
        sentinel.next = node;
        this.size++;
    }

    /**
     * insertBack() inserts an item at the back of this DList.
     * 
     * @param item
     *            is the item to be inserted. Performance: runs in O(1) time.
     */
    public void insertBack(T item) {
        DListNode node = this.newNode(item, this.sentinel.prev, this.sentinel);
        this.sentinel.prev = node;
        node.prev.next = node;
        this.size++;
    }




    /**
     * Remove first non-sentinel node from the list. Do not require size check
     * before remove operation
     * 
     */
    public void removeFront() throws UnsupportedOperationException {
        if (this.size() < 0) {
            throw new UnsupportedOperationException("removeFront");
        } else {
            sentinel.next.next.prev = sentinel;
            sentinel.next = sentinel.next.next;
            this.size--;
        }
    }

    public T get(int index) throws NoSuchElementException {
        if (index > size())
            throw new NoSuchElementException();
        DListNode node;
        for (node = sentinel; index-- > 0; node = node.next)
            ;
        return node.item;
    }

    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

}

Dictionary.java

package cs61b.homework6.dict;

/**
 * An interface for (unordered) dictionary ADTs.
 *
 * DO NOT CHANGE THIS FILE.
 **/

public interface Dictionary<K, V> {

    /**
     * Returns the number of entries stored in the dictionary. Entries with the
     * same key (or even the same key and value) each still count as a separate
     * entry.
     * 
     * @return number of entries in the dictionary.
     **/

    public int size();

    /**
     * Tests if the dictionary is empty.
     *
     * @return true if the dictionary has no entries; false otherwise.
     **/

    public boolean isEmpty();

    /**
     *  A class for dictionary entries.
     *
     *  DO NOT CHANGE THIS FILE.  It is part of the interface of the
     *  Dictionary ADT.
     **/

    class Entry<K, V> { // class within interface is automatically 'public static'.

        protected K key;
        protected V value;

        public K key() {
            return key;
        }

        public V value() {
            return value;
        }

    }

    /**
     * Create a new Entry object referencing the input key and associated value,
     * and insert the entry into the dictionary. Return a reference to the new
     * entry. Multiple entries with the same key (or even the same key and
     * value) can coexist in the dictionary.
     *
     * @param key
     *            the key by which the entry can be retrieved.
     * @param value
     *            an arbitrary object.
     * @return an entry containing the key and value.
     **/

    public Entry<K, V> insert(K key, V value);

    /**
     * Search for an entry with the specified key. If such an entry is found,
     * return it; otherwise return null. If several entries have the specified
     * key, choose one arbitrarily and return it.
     *
     * @param key
     *            the search key.
     * @return an entry containing the key and an associated value, or null if
     *         no entry contains the specified key.
     **/

    public Entry<K, V> find(K key);

    /**
     * Remove an entry with the specified key. If such an entry is found, remove
     * it from the table and return it; otherwise return null. If several
     * entries have the specified key, choose one arbitrarily, then remove and
     * return it.
     *
     * @param key
     *            the search key.
     * @return an entry containing the key and an associated value, or null if
     *         no entry contains the specified key.
     */

    public Entry<K, V> remove(K key);

    /**
     * Remove all entries from the dictionary.
     */

    public void makeEmpty();

}

HashTableChained.java

package cs61b.homework6.dict;

import java.util.ArrayList;
import java.util.Iterator;

import JavaCollections.list.DblyLinkList;

/**
 * HashTableChained implements a Dictionary as a hash table with chaining. All
 * objects used as keys must have a valid hashCode() method, which is used to
 * determine which bucket of the hash table an entry is stored in. Each object's
 * hashCode() is presumed to return an int between Integer.MIN_VALUE and
 * Integer.MAX_VALUE. The HashTableChained class implements only the compression
 * function, which maps the hash code to a bucket in the table's range.
 *
 **/

public class HashTableChained<K, V> implements Dictionary<K, V> {

    /**
     * Place any data fields here.
     **/

    private long tableSize;
    private ArrayList<DblyLinkList<Entry<K, V>>> defTable;

    /**
     * Construct a new empty hash table intended to hold roughly sizeEstimate
     * entries. (The precise number of buckets is up to you, but we recommend
     * you use a prime number, and shoot for a load factor between 0.5 and 1.)
     **/

    public HashTableChained(long sizeEstimate) {

        if (!(isPrime(sizeEstimate) && (sizeEstimate > 0L))) {
            sizeEstimate = nextPrime(sizeEstimate);
        }

        tableSize = sizeEstimate;
        defTable = new ArrayList<DblyLinkList<Entry<K, V>>>((int) sizeEstimate);

        for (int i = 0; i < (int) sizeEstimate; i++) {
            defTable.add(i, new DblyLinkList<Entry<K, V>>());
        }

    }


    /**
     * Construct a new empty hash table with a default size. Say, a prime in the
     * neighborhood of 100.
     **/

    public HashTableChained() {
        tableSize = 101;
        defTable = new ArrayList<DblyLinkList<Entry<K, V>>>((int) tableSize);
        for (int i = 0; i < tableSize; i++) {
            defTable.add(i, new DblyLinkList<Entry<K, V>>());
        }
    }


    /**
     * isPrime() helper function
     * @param n
     * @return
     */
    private static boolean isPrime(long n) {
        if (n < 2)
            return false;
        if (n == 2 || n == 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        long sqrtN = (long) Math.sqrt(n) + 1;
        for (long i = 6L; i <= sqrtN; i += 6) {
            if (n % (i - 1) == 0 || n % (i + 1) == 0)
                return false;
        }
        return true;
    }


    /**
     * nextPrime() helper function
     * @param previous
     * @return
     */
    private static long nextPrime(long previous) {
          if (previous < 2L) { return 2L; }
          if (previous == 2L) { return 3L; }
          long next = 0L;
          int increment = 0;
          switch ((int)(previous % 6L)) {
            case 0: next = previous + 1L; increment = 4; break;
            case 1: next = previous + 4L; increment = 2; break;
            case 2: next = previous + 3L; increment = 2; break;
            case 3: next = previous + 2L; increment = 2; break;
            case 4: next = previous + 1L; increment = 2; break;
            case 5: next = previous + 2L; increment = 4; break;
          }
          while (!isPrime(next)) {
            next += increment;
            increment = 6 - increment;   // 2, 4 alternating
          }
          return next;
        }


    /**
     * Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE
     * to a value in the range 0...(size of hash table) - 1.
     *
     * This function should have package protection (so we can test it), and
     * should be used by insert, find, and remove.
     **/

    int compFunction(int code) {
        return code % (int) tableSize;
    }

    /**
     * Returns the number of entries stored in the dictionary. Entries with the
     * same key (or even the same key and value) each still count as a separate
     * entry.
     * 
     * @return number of entries in the dictionary.
     **/

    public int size() {
        int totalCount = 0;

        for(int index = 0; index < this.tableSize; index++){
            DblyLinkList<Entry<K, V>> keyValueList = defTable.get(index);
            if(keyValueList.size() > 0){
                totalCount += keyValueList.size();
            }
        }

        return totalCount;
    }

    /**
     * Tests if the dictionary is empty.
     *
     * @return true if the dictionary has no entries; false otherwise.
     **/

    public boolean isEmpty() {

        for(int index = 0; index < this.tableSize; index++){
            DblyLinkList<Entry<K, V>> keyValueList = defTable.get(index);
            if(keyValueList.size() > 0){
                return true;
            }
        }
        return false;

    }

    /**
     * Create a new Entry object referencing the input key and associated value,
     * and insert the entry into the dictionary. Return a reference to the new
     * entry. Multiple entries with the same key (or even the same key and
     * value) can coexist in the dictionary.
     *
     * This method should run in O(1) time if the number of collisions is small.
     *
     * @param key
     *            the key by which the entry can be retrieved.
     * @param value
     *            an arbitrary object.
     * @return an entry containing the key and value.
     **/

    public Entry<K, V> insert(K key, V value) {

        Entry<K, V> entry = new Entry<K, V>();
        entry.key = key;
        entry.value = value;

        DblyLinkList<Entry<K, V>> keyValueList = defTable.get(compFunction(key
                .hashCode()));
        keyValueList.insertBack(entry);
        return entry;
    }

    /**
     * Search for an entry with the specified key. If such an entry is found,
     * return it; otherwise return null. If several entries have the specified
     * key, choose one arbitrarily and return it.
     *
     * This method should run in O(1) time if the number of collisions is small.
     *
     * @param key
     *            the search key.
     * @return an entry containing the key and an associated value, or null if
     *         no entry contains the specified key.
     **/

    public Entry<K, V> find(K key) {

        DblyLinkList<Entry<K, V>> keyValueList = defTable.get(compFunction(key
                .hashCode()));

        Iterator<Entry<K, V>> itr = keyValueList.iterator();
        while (itr.hasNext()) {
            Entry<K, V> element = itr.next();
            if (element.key().equals(key)){
                return element;
            }
        }

        return null;
    }

    /**
     * Remove an entry with the specified key. If such an entry is found, remove
     * it from the table and return it; otherwise return null. If several
     * entries have the specified key, choose one arbitrarily, then remove and
     * return it.
     *
     * This method should run in O(1) time if the number of collisions is small.
     *
     * @param key
     *            the search key.
     * @return an entry containing the key and an associated value, or null if
     *         no entry contains the specified key.
     */

    public Entry<K, V> remove(K key) {

        DblyLinkList<Entry<K, V>> keyValueList = defTable.get(compFunction(key
                .hashCode()));

        Iterator<Entry<K, V>> itr = keyValueList.iterator();
        Entry<K, V> element = null;
        while (itr.hasNext()) {
            element = itr.next();
            if (element.key().equals(key)){
                itr.remove();
            }
        }

        return element;
    }

    /**
     * Remove all entries from the dictionary.
     */
    public void makeEmpty() {
        for(int index = 0; index < this.tableSize; index++){

            DblyLinkList<Entry<K, V>> keyValueList = defTable.get(index);
            if(keyValueList.size() > 0){
                Iterator<Entry<K, V>> itr = keyValueList.iterator();
                while (itr.hasNext()) {
                    itr.next();
                    itr.remove();
                }
            }

        }
    }

}

My understanding is that this is called a dictionary because every DListNode is key-value pair unlike normal chained hash-table where every DListNode is value(only).

Before using generics:

Dictionary dict = new HashTableChained();
dict.insert("word", new Integer(42));
Object count = dict.find("word"); // gives an Object, not an Integer
// need to cast - annoying, not safe
Integer countAsInteger = (Integer)count;

After using generics:

Dictionary<String, Integer> dict = new HashTableChained<>();
dict.insert("word", new Integer(42));
Integer count = dict.find("word"); // gives an Integer

The generic typing also protects you from creating a heterogeneous map. These are the reasons for introducing generic typing.

Are these classes following proper abstraction and encapsulation?

\$\endgroup\$
2
+50
\$\begingroup\$

Dictionary:

In Java, there is java.util.Map interface that is a key/value dictionary; use it.

defTable:

Let \$n\$ be the initial capacity of the table. Then you spend \$\Theta(n)\$ time initialising all first \$n\$ collision chains to empty linked lists. I understand that this is necessary due to the fact you use an ArrayList, but perhaps more idiomatic approach would be to implement a static inner class for entries:

private static class DictionaryNode<K, V> {
    K key;
    V value;
    DictionaryNode<K, V> previous;
    DictionaryNode<K, V> next;
    int keyHashCode; // You could also cache the hash code of the key.
                     // This way, when searching a collision chain in
                     // order to find whether it contains a given key,
                     // all entries with different hash codes cannot be
                     // the target key.
}

And then manipulate them in your actual HashTableChained.

size:

I suggest you add a field size to your HashTableChained and increment it whenever adding a new key/value-pair, and decrementing whenever removing a key/value-pair. After all, updating size takes only constant time, yet allows size() and isEmpty() run in \$O(1)\$ as well.

makeEmpty: It makes sense to add operation clear() to DblyLinkList, which can be made to run in constant time (however, not counting garbage collection overhead). That way, makeEmpty() will run faster, as everything that is needed at each table component is calling that very \$O(1)\$ clear at each of them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.