Question

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. 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 EC330 Applied Algorithms and Data Structures for Engineers, Fall 2020 CuckooHashTable.h file as is, without any edits. Note that the hash tables are implemented as a 2x13 matrix (vector of vectors), and that a print method declaration is provided, for you to implement. Inserting an element that already exists in the table should have no effect. Your program should be able to detect if an insert results in an infinite loop in the hash, and exit with the following error message: “Error: Insert causes infinite loop”. 
Sample input.txt file content: 
1 
4 
6 
27 
123 
14 
17 
195 
Sample output for the above input: 
Table 1: 
195 
14 
- 
- 
17 
- 
123 
- 
- 
- 
- 
- 
- 
Table 2: 
- 
- 
- 
- 
- 
6 
27 
4 
- 
- 
1 
Submit your solution, which should be contained in a single CuckooHashTable.cpp file, and should be compiled with the provided CuckooHashTable.h and main.cpp files. Make sure to include an explanation of your approach in a comment at the top of the program.

CuckooHashTable.h:
#ifndef CuckooHashTable_h
#define CuckooHashTable_h

#include<string>
#include<vector>
#include<cmath>

#include<iostream>
#include<cstdlib>

using namespace std;
const int LOGICAL_SIZE = 13;

class CuckooHashTable
{
private:
  vector<vector<string>> contents; // the two hash tables are implemented as a 2D vector
    int currentSize;
public:
    CuckooHashTable(); // Constructor
    int hashCode(string value, int which); // compute hash function for input 'value', table 'which'
    void add(string value); // insert 'value' to hash table
    void print(); // print the content of the hash table in the specified format
};


#endif /* CuckooHashTable_h */

main.cpp:

#include "CuckooHashTable.h"
#include <iostream>
#include <fstream>
#include <string>
#include <cctype>

using namespace std;

int main(int argc, char** argv){

        ifstream input("input.txt");
        CuckooHashTable cht;
        string number = "";

  string line;
  while (getline(input, line)) {

    cht.add(line);
  }
        cht.print();

        return 0;
}

input.txt:

1
4
6
27
123
14
17
195

Answer 1

PROGRAM :

#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\n", key);
printf("Cycle present. REHASH.\n");
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:\n");

for (int i=0; i<ver; i++, printf("\n"))
for (int j=0; j<MAXN; j++)
(hashtable[i][j]==INT_MIN)? printf("- "):
printf("%d ", hashtable[i][j]);

printf("\n");
}

/* 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;
}