Hashtable with Quadratic Probing. Implement a simple hashtable using quadratic p

Question

Hashtable with Quadratic Probing.

Implement a simple hashtable using quadratic probing for collision resolution. Both the keys and values are integers, assuming greater than 0. The initial table size m should be 11 (it is too small for a real hashtable, we just use it for the purpose of this homework). Let n be the number of items in the table. When n m/2, use the technique of dynamic arrays to enlarge the table. You want to approximately double the table size but keep to the primes. The next table size m will be 23. You should use key%m as the hash function. Let b be the hash value modulo m. If bucket b is occupied, you probe (b + 12 ) % m,(b + 2 2 ) % m,(b + 32 ) % m, · · · ,(b + (m/2)2 ) % m, and stop as soon as you find an empty bucket. As long as n is kept less than m/2, you will find an empty bucket by the end of the probing.

You should at least implement the following functions:

(a) void put(int key, int value): insert key-value pair to the hashtable. Insert key to the key array, value to the value array based on the hash function.

(b) int get(int key): get the value of the key

(c) boolean contains(int key): return true if the hashtable contains the key

(d) void remove(int key): remove the key-value pair

(e) void rehashing(): this method is called automatically when n m/2. You should enlarge the table and use findPrime(2 m) to get the new table size. You need to compute new hash index for every key stored in the existing hash table.

(f) int findPrime(int x): find the next (the smallest) prime bigger than x. For example, findPrime(8) = 11, findPrime(22) = 23

Explanation / Answer

hash_quadratic.cpp

#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;
enum EntryType {Legitimate, Empty, Deleted};
struct HashNode
{
int element;
enum EntryType info;
};
struct HashTable
{
int size;
HashNode *table;
};
HashTable *initializeTable(int size);
int nextPrime(int n);
void put(int key, HashTable *htable);
void Retrieve(HashTable *htable);
HashTable *Rehash(HashTable *htable);
int main()
{
int value, size, pos,i=1;
int choice;
HashTable *htable;
while(1)
{
cout<<" ----------------------"<<endl;
cout<<"******* MENU *************"<<endl;
cout<<"1.Initialize size of the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Display Hash Table"<<endl;
cout<<"4.Rehash The Table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Select your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter size of the Hash Table: ";
cin>>size;
htable = initializeTable(size);
cout<<"Size of Hash Table: "<<nextPrime(size);
break;
case 2:
if (i>htable->size)
{
cout<<"Table is Full, Rehash the table"<<endl;
continue;
}
   cout<<"Enter element to be inserted: ";
   cin>>value;
put(value, htable);
i++;
break;
case 3:
Retrieve(htable);
break;
case 4:
htable = Rehash(htable);
break;
case 5:
exit(1);
default:
cout<<" Wrong Option! Please Enter correct option ";
}
}
return 0;
}
bool isPrime (int n)
{
if (n==2||n==3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
int nextPrime(int n)
{
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
int HashFunc(int key, int size)
{
return key % size;
}
HashTable *initializeTable(int size)
{
HashTable *htable;
if (size < MIN_TABLE_SIZE)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
htable = new HashTable;
if (htable == NULL)
{
cout<<"Out of Space"<<endl;
return NULL;
}
htable->size = nextPrime(size);
htable->table = new HashNode [htable->size];
if (htable->table == NULL)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
for (int i = 0; i < htable->size; i++)
{
htable->table[i].info = Empty;
htable->table[i].element = NULL;
}
return htable;
}
int get(int key, HashTable *htable)
{
int pos = HashFunc(key, htable->size);
int collisions = 0;
while (htable->table[pos].info != Empty &&
htable->table[pos].element != key)
{
pos = pos + 2 * ++collisions -1;
if (pos >= htable->size)
pos = pos - htable->size;
}
return pos;
}
void put(int key, HashTable *htable)
{
int pos = get(key, htable);
if (htable->table[pos].info != Legitimate)
{
htable->table[pos].info = Legitimate;
htable->table[pos].element = key;
}
}
HashTable *Rehash(HashTable *htable)
{
int size = htable->size;
HashNode *table = htable->table;
htable = initializeTable(2 * size);
for (int i = 0; i < size; i++)
{
if (table[i].info == Legitimate)
put(table[i].element, htable);
}
free(table);
return htable;
}
void Retrieve(HashTable *htable)
{
for (int i = 0; i < htable->size; i++)
{
int value = htable->table[i].element;
if (!value)
cout<<"Key Position"<<i + 1<<" Element: Null"<<endl;
else
cout<<"Key Position: "<<i + 1<<" Element: "<<value<<endl;
}

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.