3. Hashtable with Quadratic Probing. Implement a simple hashtable using quadrati
ID: 3902440 • Letter: 3
Question
3. 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
#include<iostream>
using namespace std;
struct item{
int key;
int value;
};
class Hashtable {
private:
item *data;
int num;
int max;
public:
Hashtable(int m){
data = new item[m];
for (int i = 0; i<m; i++){
data[i].key = -1;
data[i].value = -1;
}
max = m;
num = 0;
}
int findPrime(int n){
int prime = 0;
int m = n +1;
while (true){
int found = 1;
for (int i = 0; i<m; i++){
if ( m % i == 0){
found = 0;
break;
}
}
if (found == 1)
break;
m = m+1;
}
return m;
}
void print(){
//cout << "num" << num << endl;
for (int i = 0; i<max; i++){
if (data[i].key != -1)
cout << i << " " << "(" << data[i].key << "," << data[i].value << ")" << endl;
}
}
bool contains(int key){
for (int i = 0; i<max; i++){
if (data[i].key == key)
return true;
}
return false;
}
int get(int key){
for (int i = 0; i<max; i++){
if (data[i].key == key)
return data[i].value;
}
return -1; //error situation
}
void remove(int key){
for (int i = 0; i<max; i++){
if (data[i].key == key){
data[i].key = -1;
data[i].value = -1;
num--;
return;
}
}
}
void put (int key, int value){
int k = key % max;
if (data[k].key == -1){
//cout << key << endl;
data[k].key = key;
data[k].value = value;
num++;
}
else {
int m = k;
int count = 1;
while(data[m].key != -1){
m = m + count * count;
count++;
}
data[m].key = key;
data[m].value = value;
num++;
}
if (num > max/2){
int k = findPrime(2* max);
item *data1 = new item[max];
for (int i = 0; i<max; i++){
data1[i].key = data[i].key;
data[i].value = data[i].value;
}
item *data = new item[k];
for (int i = 0; i<k; i++){
data[i].key = -1;
data[i].value = -1;
}
for (int i = 0; i<max; i++){
if (data1[1].key != -1)
put(data1[i].key, data1[i].value);
}
max = k;
}
}
};
int main(){
Hashtable h(11);
h.put(1,5);
h.put(5,10);
h.put(6,17);
h.print();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.