cs230 Lecture Notes
Spring 2002
Week 12, Thursday

Today's topics
--------------

1) Quiz 9

2) Homework 10 solutions

3) Hashtable implementation

4) Hashtable performance analysis


How to turn in Homework 10:

  1) Please create a file named hw10.java and put your
     solution to the first two problems in it (checking
     for loops in a list and generating random words
     from a Hashtable)

  2) Put your Hashtable implementation in a file named
     Hashtable.java (and make the class name Hashtable).
     If you need to fix other files to accomodate the name
     change, that's ok.

  3) Run turnin again.  I have changed turnin so that it
     asks which files you want to turn in.  Please turn in
     only hw10.java and Hashtable.java.

How to turn in Homework 11:

You should have classes named FreqTab, CodeTab, HuffTree
and Huffman, each in a separate file.  Also, your testing
code should be in a file called Test.java.

Please turn in only those files, with those names.

Quiz 9 Solutions
----------------























Homework 10 Solutions
---------------------

Checking for a loop (true if there is one, false otherwise).

If there's a loop, we will eventually see a node we have seen
before.

public static boolean checkList (LinkedList list) {
    Hashtable ht = new Hashtable ();
    for (Node node = list.head; node != null; node = node.next) {
        if (ht.hasKey (node)) return true;
	ht.add (node, "narf");
    }
    return false;    // no loops
}

What kind of equality do we want to use to compare nodes?


Pick a random word from a WordCount:

public class WordCount {
    Hashtable ht;
    int count;

    public WordCount () {
	ht = new Hashtable ();
	count = 0;
    }

    public String randomWord () {
	int x = randInt (0, count-1);
	Enumeration keys = ht.keys ();
	int total = 0;
	while (keys.hasMoreElements ()) {
	    Object key = keys.nextElement ();
            Integer value = (Integer) ht.get (key);
	    total += value.intValue ();
	    if (total > x) return (String) key;
	}
	// we should never get here
	return null;
    }

    // randInt: returns a random number between low and high,
    // including both endpoints
    public static int randInt (int low, int high) {
        while (true) {
            int x = (int)(Math.random() * (high-low+1) + low);
            if (x >= low && x <= high) return x;
        } 
    }
}


Hashtable implementation (Vector of LinkedLists)
------------------------

java.util.Vector and java.util.LinkedList both implement
the interface List.

My Hashtable is a Vector of LinkedLists, but we could
generate the three other permutations (V of V, L of L and L of V)
by doing search and replace.

Then we could test to see which one has the best performance.

Notice that every method in this file contains exactly
one loop that uses one of the standard idioms for traversing
various things.

The code is visually a little dense, but it is simple, readable,
and demonstrably correct.

As an exercise, write resize.  It should be an object method
in the Hashtable class that doubles the number of Vectors in
the Hashtable.


























Performance analysis of Hashtable
---------------------------------

Again, if the lengths of the LinkedLists are bounded,
then put and get are constant time.

What is the performance of keys?





What is the performance of resize?





Assume there are n elements in the Hashtable.
Assume there are l lists.

The number of elements per list is (on average) n/l.

Assume that we want the lists to contain (on average) 1 element.

Then whenever n = l, we double l.

The total cost of add, then, is

    t(n) = c + p kn

Where t(n) is the cost of adding the nth element.

c  is an unknown constant
p  is the probability (loosely speaking) that we will have
   to resize the Hashtable
kn is the cost of the resize

Fortunately, the chance of having to resize is only 1/n.

So the total cost is

    t(n) = c + 1/n kn =  c + k

Most of the time, add is constant.  Occasionally, it's linear.

Averaging over a number of adds, it's constant time.