Rehashing a hash table in c++ with quadratic probing

Question

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

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.

Answer 1

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.