C++

Hashing

Problem Description

Create a program that accepts keys (you can have an array of keys in the program to use) and hashes them. It should implement chaining in the case of collisions. Then it should print out the results.

Use a remainder method and see the results, then use a folding method and see the results.

Then try something more in a sequential style, but increment by 10s for the keys and see if the distribution changes.

Sample input for random numbers: {15, 17, 266, 999, 33, 88888, 777, 99, 112, 28, 29};

Sample input for sequential: {115, 125, 135, 145, 155, 165, 175, 185, 195, 205, 215};

For my folding method I took the remainder of the key divided by 13 and then the results of the key divided by 100, added those together and then took the mask of the lower four bits.

I tried it with 11 buckets and 16 buckets.

Sample runs with 16 buckets below

Create a document with several sample runs and evaluate what happened as you varied conditions (bucket size, method, input)

Sample Output

Folding

0 points NULL

1 points 777 NULL

2 points 15 28 NULL

3 points 29 NULL

4 points 17 999 NULL

5 points NULL

6 points NULL

7 points 33 NULL

8 points 266 99 NULL

9 points 112 NULL

10 points NULL

11 points NULL

12 points NULL

13 points NULL

14 points NULL

15 points 88888 NULL

Press any key to continue

Remainder

0 points 112 NULL

1 points 17 33 NULL

2 points NULL

3 points 99 NULL

4 points NULL

5 points NULL

6 points NULL

7 points 999 NULL

8 points 88888 NULL

9 points 777 NULL

10 points 266 NULL

11 points NULL

12 points 28 NULL

13 points 29 NULL

14 points NULL

15 points 15 NULL

Press any key to continue