// ChainingHash is a hash table with separate chaining.  Each array
// slot holds a linked list of items hashing to that slot.  We did not
// implement "move-to-front" within these lists.

class ChainingHash implements Set
{
    // Might play with this, max load before doubling:
    final double alpha = 2;

    // Our linked lists are built of these nodes.
    protected static class Node {
        Object item;
        Node next;
        Node(Object x, Node link) { item=x; next=link; }
    }

    // Our data:
    protected Node[] array;     // array[i] is list head, or null
    protected int size = 0;     // number of items stored overall

    // Constructor: initial table size is set here.
    public ChainingHash() { array = new Node[8]; }

    // Utilities:

    // Our hash function, just the hashCode mod the array length.
    protected int hash1(Object x) {
        int len = array.length, rem = x.hashCode() % len;
        return (rem<0) ? rem+len : rem; // in case rem is negative
    }

    // Return the node containing x (or an equal key) in array[h],
    // or else return null.
    protected Node findNode(Object x, int h) {
        for (Node n=array[h]; n!=null; n=n.next)
            if (x.equals(n.item)) return n;
        return null;
    }

    protected void rebuild(int newLen) {
        System.err.printf("Rebuild to %d (size=%d)\n", newLen, size);
        Node[] oldArray = array;
        array = new Node[newLen];
        for (Node n: oldArray) {
            while (n != null) {
                int h = hash1(n.item);
                Node nxt = n.next;
                n.next = array[h];
                array[h] = n;
                n = nxt;
            }
        }
    }

    // Now we implement the Set interface.

    public int size() { return size; }

    public Object find(Object x) {
        Node n = findNode(x, hash1(x));
        return n==null? null : n.item;
    }

    public boolean add(Object x) {
        int h = hash1(x);
        if (findNode(x,h)!=null) return false; // no duplicates
        array[h] = new Node(x, array[h]); // insert x at head
        ++size;
        if (size > alpha*array.length) rebuild(2*array.length);
        return true;
    }

    public boolean remove(Object x) {
        int h = hash1(x);
        // Loop like in findNode, but also tracking previous node p.
        for (Node n=array[h], p=null; n!=null; p=n, n=n.next)
            if (x.equals(n.item)) {
                if (p==null) array[h]=n.next; else p.next=n.next;
                --size;
                return true;
            }
        return false;
    }
}