# Rehashing a hash table in c++ with quadratic probing

The code below is my attempt at trying to create a hash table. I'm currently stuck with the rehash function as I think it's not efficient enough (I believe it's O(n^2). I'd be grateful if someone could give some comments and suggestions on how I could improve my rehash function.

class Hashtable{
private:
int sze; //size: number of values are currently in the hashtable
int cap; //capacity: the size of the hashtable

struct HashNode{
string value;
};

HashNode** arr;  //bucket

//determine whether the number is prime or not
bool IsPrime(int number){
if (number == 2 || number == 3)
return true;

if (number % 2 == 0 || number % 3 == 0)
return false;

int divisor = 6;
while (divisor * divisor - 2 * divisor + 1 <= number)
{

if (number % (divisor - 1) == 0)
return false;

if (number % (divisor + 1) == 0)
return false;

divisor += 6;

}

return true;

}

//find the next prime number that is >= a
int NextPrime(int a){
while (!IsPrime(++a)){ }
return a;
}

int hashing(const string &s) const{
int h = 0;
for (int i = 0; i < s.size(); i++)
{
h += int(s[i]);
}

return h;
}

void rehashing ()
{
int oldCap = cap;
sze = 0;
//Doubling the capacity
cap = NextPrime(cap*2);

HashNode** oldArr = arr;
arr = new HashNode*[cap]();

//moving the values to the new after rehashing
for (int i = 0; i < oldCap; i++){
if (oldArr[i] != nullptr){
for (int j = 0; j < cap; j++){
int index = (hashing(oldArr[i]->value) + j*j) % cap;
if (arr[index] == nullptr){
arr[index] = new HashNode {oldArr[i]->value};
sze++;
break;
} //if
} //for
delete oldArr[i];
oldArr[i] = nullptr;
} //if
} //for

delete[] oldArr;
}

public:
// Constructor
Hashtable(int ini_cap = 101) : sze(0), cap(ini_cap), arr(new HashNode*[cap]){
for (int i = 0; i < cap; i++)
{
arr[i] = nullptr;
}

}

//Destructor
~Hashtable(){
for (int i = 0; i < cap; i++){
if (arr[i] != nullptr){
delete arr[i];
arr[i] = nullptr;
}
}
delete[] arr;
}

double load_factor() const {return double(sze)/cap;}

void put(const string& s){
//Initialize a new node for the new input
HashNode* temp = new HashNode{s};

//Insert using quadratic probing
for (int i = 0; i < cap; i++){
int index = (hashing(s) + i*i) % cap;
if (arr[index] == nullptr){
arr[index] = temp;
sze++;
break;
}
}

if (load_factor() > 0.5){
rehashing();
} //if

};


Ideally, I think i'd be the best If I could make it O(n). So if anyone have any idea on how I could do that please tell me. Thank you.

Rreplace the inner for loop of rehashing with a call to put. put has an average runtime of $$\\mathcal{O}(1)\$$ . So, rehashing has an average runtime of $$\\mathcal{O}(n)\$$ since it is $$\n\$$ put operations.

It would look something like this:

void rehashing() {
int oldCap = cap;
sze = 0;
cap = NextPrime(cap * 2);

HashNode** oldArr = arr;
arr = new HashNode*[cap]();

for (int i = 0; i < oldCap; ++i) {
if (oldArr[i] != nullptr) {
put(oldArr[i]->value);
delete oldArr[i];
}
}

delete[] oldArr;
}


Also, it might be useful to refactor put to have a private overloaded put member function which accepts a HashNode. The public put would just allocate a HashNode and call the private put. Then, for rehashing, one could use the private put and wouldn't need to delete the previous HashNode. This would save memory allocation and deletions.