OOP paradigm implementation of a Dictionary data model

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
*/
public class DblyLinkList implements Iterable {

/*
* 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 {

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)

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 key;
    V value;
    DictionaryNode previous;
    DictionaryNode 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.

StackExchange Code Review Q#104193, answer score: 2