Problem 64

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Hash table simulation

Due: April 5
Points: 5

Write a Java, C++, or Python program that demonstrates how big the buckets might get in a hash table that has a perfect hash function.

Your program should read two integers, $$s$$ and $$n$$, from command line arguments. $$s$$ is the size of the hash table, and $$n$$ is the number of things that are going to be inserted.

But you're not actually going to insert anything! Your "hash function" will be a random number generator that produces values from 0 up to $$s-1$$ with equal probability. You should know how to write that by now; you can use any built-in random number generators in the language of your choosing.

Your program should "insert" (i.e. compute random hash table locations for) the n elements, keeping track in a table of how many elements hash to each location. So essentially you will be picking random numbers from 0 up to $$s-1$$, and incrementing an array at that position, repeating this a total of $$n$$ times.

At the end, print out a single line for each entry in your table, along with a number of X's equal to the size. On the last line, print out what is the maximum bucket size.

So for example, if $$s=7$$ and $$n=10$$, you might end up with something like:

0:
1: XXXX
2: X
3:
4: X
5: X
6: XXX

Maximum size: 4

Submit your program according to the instructions on the submit page.