Create a C++ program which utilizes cuckoo hashing to store data values, which will be provided from the text file raw int.txt. Have each hash table start at size 11, and rehash BOTH of your hashtables when either hashtable has a load factor greater than 0.5 [recall that load factor is (number of entries) / table size], or if you detect a cycle of insertion and displacement. What is the final size of your hash tables? Can you reduce the final table size with more efficient hashing algorithms? Hash functions:

h1(x) = x mod m

h2(x) = (x/m) mod m

For rehashing:

update m using:

m = smallest prime number greater then 2m

m = m

Program Output requirements: 1. Output each individual move [i.e. 5 goes in table 1 slot 4. 6 goes in table 1 slot 4, 5 goes in table 2 slot 12. 14 goes in table 1 slot 9 . . . ]

2. When rehashing becomes necessary, display which table necessitated the rehashing [print out which table has a load factor greater than 0.5]. If rehashing became necessary due to a cycle of insertion and deletion, inform the user of which elements are involved in the cycle. Print out the new table size and the load factor of each new table once rehashing is complete.

raw_int.txt example (use to test code or your own set of numbers in a txt file):

9065 1363 5310 1451 3426 37 2708 4931 3681 732 8338 1946 6000 3631 9984 1479 6039 3488 3211 1939 5933 6553 5125 7252 4377 1759 1792 1755 5832 4222 8825 6571 5917 3017 2357 5775 6346 819 8617 5451 1858 7275 5388 5637 5292 139 9505 9329 1829 298 9760 4105 5051 9637 1424 5729 3829 3200 7145 4106 269 7053 7419 415 2891 9137 6164 497 5155 1484 1 3364 2290 9850 7146 9596 5045 2531 7514 4872 7340 175 5003 5794 5066 9765 2655 393 6670 8217 4618 7699 3226 1541 4476 6565 5666 4507 5647 3903 2786 9413 1672 4110 1818 87 7692 2077 4761 3930 6542 7756 302 4683 818 3018 8855 7518 3840 4212 2481 6869 9884 8680 5973 4970 6952 5026 6913 3006 9130 4424 2013 5557 4439 81 5595 2333 6517 5155 9409 415 8 8669 8438 6014 4141 3036 8631 8656 2160 5046 4670 3208 9273 5588 19 5715 7771 6397 3083 4115 2709 5687 9437 5886 7439 7747 1238 3118 3328 8004 6781 437 7923 4411 493 7763 8207 8597 504 3788 5225 9788 4694 4971 5397 4155 2465 4823 4756 3654 3541 7332 6609 3419 9107 4766 8487 3347 4195 7364 4696 9925 6367 3741 8455 6014 7465 9069 5031 5544 1453 4819 4445 8698 5958 5733 7995 2688 2530 327 877 8942 5084 3736 6685 4837 6022 783 1361 8238 1940 8228 8601 5635 1306 1716 6772 1602 9394 736 753 1846 5683 3941 2511 4423 5246 9115 2086 3188 4644 4758 7471 8422 791 3026 9626 8261 504 2037 6806 4514 4378 3609 8827 602 2935 3941 9696 9626 1727 1075 8097 8754 2583 7305 316 111 2385 4067 587 3905 8488 9055 8529 7791 8406 9083 8241 5820 7906 959 6984 2165 2069 9830 5480 2152 4676 6207 181 412 9239 2964 3060 9184 8510 1933 2576 9625 1715 2782 8680 6450 7391 7736 1410 2902 4279 8010 8779 8288 2512 2799 6260 1773 9223 6835 6134 7139 2940 6934 9477 188 1095 3538 2330 4288 318 7832 3173 1866 5558 3365 8109 3012 4062 3823 6389 4450 834 2912 5515 7313 9590 4820 4805 5697 9475 3825 9759 8849 59 9895 1594 5969 873 3730 9577 7613 4704 5705 8927 5820 7519 646 437 5906 8427 4417 1795 7594 5972 1905 7706 7614 4761 6164 2154 7186 8767 8432 9777 4899 3849 8551 9277 5009 9368 7074 1997 9195 7735 2566 8678 4780 4890 4500 4586 8243 6888 2578 9199 2272 4587 5661 517 1258 6487 8242 4779 7651 288 9881 3987 4910 6639 2050 2739 4887 665 7547 390 5487 8183 7069 5852 8272 502 3877 8104 7602 5493 259 7123 2608 3668 6886 1262 9174 9571 861 6475 662 6355 1262 2797 5240 8335 5167 1333 3422 8794 6425 8464 8331 2488 412 496 9173 9623 9951 9905 8774 3644 545 9359 6203 5797 2657 2715 9593 4887 974 7218 8098 2328 2072 1995 95 5416 4684 9931 5942 9449 369 1868 9954