Python

Linear Probing, Quadratic Probing, Double Hashing Probing. Collisions

Write program that insert(put) and retrieve(get) numbers from input file and output number of collisions for linear probing, quadratic probing, double hashing probing and collect number of collisions for each probing for 3 types of random files: increased random, decreased random, not ordered random(100 numbers in each file).

Hash Table size is 191, so 100 random numbers are to be inserted to the table to collect number of collisions.

R=181, prime that less than table size( 191), you shall use it for hash2() function in Double Hashing Probing.

Create classes LinearProbingHash QuadraticProbingHash and DoubleHashingProbingHash andDriver.cpp file to test your classes and collect data about collisions.

Example input file:

100 28 61 90 125 168 200 201 240 249 277 301 319 333 377 379 392 440 473 493 528 570 615 659 678 727 748 760 764 808 809 851 900 903 903 927 970 1003 1044 1079 1099 1132 1172 1213 1228 1252 1263 1310 1341 1386 1392 1416 1443 1446 1486 1492 1503 1527 1569 1611 1633 1654 1663 1702 1710 1732 1769 1794 1842 1882 1905 1937 1979 2004 2018 2031 2050 2091 2108 2158 2169 2195 2211 2230 2262 2307 2347 2357 2381 2427 2441 2486 2507 2555 2589 2633 2641 2683 2727 2771 2809

Output file should read:

Before linear key = 100 got value=1 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 100 got value(*p)=1

Before quadratic key = 100 got value=1 1.before put QuadraticProbingHash.collision = 0

2.after put QuadraticProbingHash.collision = 0

3.after get QuadraticProbingHash.collision = 0

After quadratic key = 100 got value(*pq)=1 Before double hashing key = 100 value=1 1.before put DoubleHashingProbingHash.collision = 0

2.after put DoubleHashingProbingHash.collision = 0

3.after get DoubleHashingProbingHash.collision = 0

After double hashing key = 100 value*pdh=1 Before linear key = 28 got value=2 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 28 got value(*p)=2 ETC for numbers in file

until all numbers in file exhausted.