Create a C++ program which utilizes cuckoo hashing to store data values, which w

Question

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

Explanation / Answer

#include #include #include struct hash *hashTable = NULL; int eleCount = 0; struct node { int key, age; char name[100]; struct node *next; }; struct hash { struct node *head; int count; }; struct node * createNode(int key, char *name, int age) { struct node *newnode; newnode = (struct node *) malloc(sizeof(struct node)); newnode->key = key; newnode->age = age; strcpy(newnode->name, name); newnode->next = NULL; return newnode; } void insertToHash(int key, char *name, int age) { int hashIndex = key % eleCount; struct node *newnode = createNode(key, name, age); /* head of list for the bucket with index "hashIndex" */ if (!hashTable[hashIndex].head) { hashTable[hashIndex].head = newnode; hashTable[hashIndex].count = 1; return; } /* adding new node to the list */ newnode->next = (hashTable[hashIndex].head); /* * update the head of the list and no of * nodes in the current bucket */ hashTable[hashIndex].head = newnode; hashTable[hashIndex].count++; return; } void deleteFromHash(int key) { /* find the bucket using hash index */ int hashIndex = key % eleCount, flag = 0; struct node *temp, *myNode; /* get the list head from current bucket */ myNode = hashTable[hashIndex].head; if (!myNode) { printf("Given data is not present in hash Table!! "); return; } temp = myNode; while (myNode != NULL) { /* delete the node with given key */ if (myNode->key == key) { flag = 1; if (myNode == hashTable[hashIndex].head) hashTable[hashIndex].head = myNode->next; else temp->next = myNode->next; hashTable[hashIndex].count--; free(myNode); break; } temp = myNode; myNode = myNode->next; } if (flag) printf("Data deleted successfully from Hash Table "); else printf("Given data is not present in hash Table!!!! "); return; } void searchInHash(int key) { int hashIndex = key % eleCount, flag = 0; struct node *myNode; myNode = hashTable[hashIndex].head; if (!myNode) { printf("Search element unavailable in hash table "); return; } while (myNode != NULL) { if (myNode->key == key) { printf("VoterID : %d ", myNode->key); printf("Name : %s ", myNode->name); printf("Age : %d ", myNode->age); flag = 1; break; } myNode = myNode->next; } if (!flag) printf("Search element unavailable in hash table "); return; } void display() { struct node *myNode; int i; for (i = 0; i key); printf("%-15s", myNode->name); printf("%d ", myNode->age); myNode = myNode->next; } } return; } int main() { int n, ch, key, age; char name[100]; printf("Enter the number of elements:"); scanf("%d", &n); eleCount = n; /* create hash table with "n" no of buckets */ hashTable = (struct hash *) calloc(n, sizeof(struct hash)); while (1) { printf(" 1. Insertion 2. Deletion "); printf("3. Searching 4. Display 5. Exit "); printf("Enter your choice:"); scanf("%d", &ch); switch (ch) { case 1: printf("Enter the key value:"); scanf("%d", &key); getchar(); printf("Name:"); fgets(name, 100, stdin); name[strlen(name) - 1] = ''; printf("Age:"); scanf("%d", &age); /*inserting new node to hash table */ insertToHash(key, name, age); break; case 2: printf("Enter the key to perform deletion:"); scanf("%d", &key); /* delete node with "key" from hash table */ deleteFromHash(key); break; case 3: printf("Enter the key to search:"); scanf("%d", &key); searchInHash(key); break; case 4: display(); break; case 5: exit(0); default: printf("U have entered wrong option!! "); break; } } return 0; }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---