Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 22, 2001 04:52 PM

CPSC 461 File Structures
Assignment 3 - Spiral Hashing

Write a program that will search for and insert a set of keys into a hash table using Spiral Dynamic Hashing.
- Each address (bucket) is to hold 100 keys
- Start with 5 buckets
- Grow by a factor of 2
- keys are numeric, positive, in the range 0-1,000,000,000 (0-1 billion)
- if you are given a duplicate key, assume the request to go with this key was a search
- if you are given a unique key, assume the request that went with it was an insertion.

Keep track of key distributions as follows:
- keep counts of the number of keys in each bucket
- when a bucket becomes full,
print out the current distribution (before re-distribution) of keys as %
print out the number of keys inserted since the last re-distribution
- once the keys have been moved to the new buckets, print out the key distribution again (as %)
Questions and Analysis:
1. Do your numbers come out the same as predicted in the notes?
- How close are they?
- Why do they differ?
2. "Analyse" each data set to get a measure of the "randomness" of the keys.
- What are reasonable measures for this?
- Why?
- Why might this kind of analysis be useful?
- What conclusions can you draw about the data you were given?
3. Demonstrate that your hash function is random (or at least good enough).

4. Comment on the relative efficiency of the calculations used to find bucket addresses and what could be done to speed up processing time.

Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 22, 2001 04:52 PM