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:

2: X
4: X
5: X
6: XXX

Maximum size: 4

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