Create a program which utilizes cuckoo hashing to store data values, which will
ID: 3859697 • Letter: C
Question
Create a 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.
Explanation / Answer
// C++ program to demonstrate working of Cuckoo
// hashing.
#include<bits/stdc++.h>
// upper bound on number of elements in our set
#define MAXN 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 (key/MAXN)%MAXN;
}
}
/* 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 keys_1[] = {20, 50, 53, 75, 100, 67, 105,
3, 36, 39};
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 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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.