Could someone help with this: Implement a Cuckoo hash table in which two separat
ID: 3730441 • Letter: C
Question
Could someone help with this: Implement a Cuckoo hash table in which two separate tables are maintained. Each table should have a fixed size of 13. Use the hash function h1(x) = x mod 13 for the first table, and h2(x)= 11 – (x mod 11) for the second table.
4. [Cuckoo Hashing, 50 points] Implement a Cuckoo hash table in which two separate tables are maintained. Each table should have a fixed size of 13. Use the hash function hi(x) -x mod 13 for the first table, and h2(x)- 11 -(x mod 11) for the second table. Your program should read an input file, input.txt, consisting of one input per line, insert the input to the table in order, and print out the final content of the hash table in the provided format. Your implementation should utilize the provided CuckooHashTable.h file as is, without any edits. Note that the hash tables are is provided, for you to implement. Your program should be able to detect if an insert results in an infinite loop in the hash, and exit with an error message. Sample input.txt file content: 4 27 123 EC330 Applied Algorithms and Data Structures for Engineers, Spring 2018 14 17 195Explanation / Answer
#include<bits/stdc++.h>
#include<iostream>
#include<fstream>
// upper bound on number of elements in our set
#define MAXN 13
#define hashN 11
// choices for position
#define ver 2
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
int hashtable[ver][MAXN];
// Array to store possible positions for a key
int pos[ver];
/* function to fill hash table with dummy value
* dummy value: INT_MIN
* number of hashtables: ver */
void initTable()
{
for (int j=0; j<MAXN; j++)
for (int i=0; i<ver; i++)
hashtable[i][j] = INT_MIN;
}
/* return hashed value for a key
* function: ID of hash function according to which
key has to hashed
* key: item to be hashed */
int hash(int function, int key)
{
switch (function)
{
case 1: return key%MAXN;
case 2: return hashN -(key%hashN);
}
}
/* function to place a key in one of its possible positions
* tableID: table in which key has to be placed, also equal
to function according to which key must be hashed
* cnt: number of times function has already been called
in order to place the first input key
* n: maximum number of times function can be recursively
called before stopping and declaring presence of cycle */
void place(int key, int tableID, int cnt, int n)
{
/* if function has been recursively called max number
of times, stop and declare cycle. Rehash. */
if (cnt==n)
{
printf("%d unpositioned ", key);
printf("Cycle present. REHASH. ");
return;
}
/* calculate and store possible positions for the key.
* check if key already present at any of the positions.
If YES, return. */
for (int i=0; i<ver; i++)
{
pos[i] = hash(i+1, key);
if (hashtable[i][pos[i]] == key)
return;
}
/* check if another key is already present at the
position for the new key in the table
* If YES: place the new key in its position
* and place the older key in an alternate position
for it in the next table */
if (hashtable[tableID][pos[tableID]]!=INT_MIN)
{
int dis = hashtable[tableID][pos[tableID]];
hashtable[tableID][pos[tableID]] = key;
place(dis, (tableID+1)%ver, cnt+1, n);
}
else //else: place the new key in its position
hashtable[tableID][pos[tableID]] = key;
}
/* function to print hash table contents */
void printTable()
{
printf("Final hash tables: ");
for (int i=0; i<ver; i++, printf(" "))
for (int j=0; j<MAXN; j++)
(hashtable[i][j]==INT_MIN)? printf("- "):
printf("%d ", hashtable[i][j]);
printf(" ");
}
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
void cuckoo(int keys[], int n)
{
// initialize hash tables to a dummy value (INT-MIN)
// indicating empty position
initTable();
// start with placing every key at its position in
// the first hash table according to first hash
// function
for (int i=0, cnt=0; i<n; i++, cnt=0)
place(keys[i], 0, cnt, n);
//print the final hash tables
printTable();
}
/* driver function */
int main()
{
/* following array doesn't have any cycles and
hence all keys will be inserted without any
rehashing */
int index=0;
ifstream myReadFile;
myReadFile.open("input.txt");
int keys_1[13];
if (myReadFile.is_open()) {
while (!myReadFile.eof()) {
myReadFile >> keys_1[index];
index++;
}
}
myReadFile.close();
int n = sizeof(keys_1)/sizeof(int);
cuckoo(keys_1, n);
/* following array has a cycle and hence we will
have to rehash to position every key */
int length = keys_1.size();
keys_1[length+1]=6;
int keys_2[14];
std::copy(std::begin(keys_1), std::end(keys_1), std::begin(keys_2));
int keys_2[] = {20, 50, 53, 75, 100, 67, 105,
3, 36, 39, 6};
int m = sizeof(keys_2)/sizeof(int);
cuckoo(keys_2, m);
return 0;
}