CS141 Lab 3

In-Lab Instruction

Hashing: Implement a hashing mechanism

Explain briefly hasing and what we use it for

Use a simple function and show them how to rescale numbers

           x in Min - Max
       to an interval {0,K-1} : (K-1) (x-Min)/(Max-Min) and take round of this.

Implement hashing:

           Count time when hashing is good (ie large hashing
           space hashing table = 1/10 of the number of items)
           versus ridiculously small hashing table.

            ie: 4 entries for N=100, 1000, 10000, 100000 items.
            (the items could be the numbers 1...N, but it would be more interesting to
            have them create random numbers in a *larger* arbitrary space Min ... Max)

           Implement the simple hashing, where you have an array of K entries
           that point to a list of items, and overloading creates an adjacency list

           Link for creating random numbers. (Please right-click, choose "save target as...")

	 ie: call  random_range(1,6);

Some Common Hash Functions:

The mod function: h(k) = k mod m
The multiplication function: f = kA - (int)(kA), h(k) = (int)(fm)

Plot the difference between the good and bad hashing

           * in creating the hash table
           * in retrieving a sample 100 items (bonus)
           * count min, max and average lenght of the lists of items
              hanging from the hash table (the array)

           Ideally, they should be able to see that the good hashing stays
           proportional to O(N) for creating, and constant O(1) in retrieving
           while the bad one is close to O(N^2) in creating and O(N)
           in retrieving.