Hashing Assignment

Evaluation of Hashing functions for storing Social Security Numbers
In this assignment we will randomly generate SSNs and simulate storing them using hashing, resolving collisions using chaining.

This program is a contest. The object of your program is to create an efficient hash function for SSNs.
You will test your hash function by generating large lists of random SSNs.
Before beginning this assignment you should read this web page on resolving hash collisions using chaining.


    While user wants to continue
	Ask the user for the number, N, of SSNs to store
	
Ask the user for the load factor for the hash table, HT. (0 < load factor <= 1)
	
//load factor is the ratio of the number of items to be stored in a hash table divided by number of slots in the hash table
	
Create an array sized to hold specified number of SSNs
	
Load SSN array with randomly generated SSNs
	
Compute size of hash table based on load factor
	
Create hash table array, HT, and init to all zeros
	
for each SSN in SSN array
		hash SSN into HT index number, i
		
increment HT[i]
	    
	
Compute number of lookups required using chaining (linked lists) for overflow 

		∑(HT[i]×(HT[i]+1)/2) for 0 <= i < N)(see link above)
	
Compute number of collisions = ∑(HT[j]-1) for all HT[j] > 1
	
Compute "good" (goal) number of collisions and compare
	
Display
	    
		number of SSNs processed
		
time required to process
		
load factor
		
number of collisions, goal number of collisions, number of collisions/goal number of collisions
		
average number of lookups required for retrieval.
	    
      
    
Ask user if he/she wants to run simulation again

I will test your program and compare your results with your classmates' results. The smallest average number of lookups using a load factor of .5 wins. This means it is absolutely critical that you count the number of lookups properly.

Top of this page Top of page

Home page