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 &lt;= 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 &gt;= a
    int NextPrime(int a){
        while (!IsPrime(++a)){ }
        return a;
    }

    int hashing(const string &amp;s) const{
        int h = 0;
        for (int i = 0; i &lt; 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 &lt; oldCap; i++){
            if (oldArr[i] != nullptr){
                for (int j = 0; j &lt; cap; j++){
                    int index = (hashing(oldArr[i]-&gt;value) + j*j) % cap;
                    if (arr[index] == nullptr){
                        arr[index] = new HashNode {oldArr[i]-&gt;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 &lt; cap; i++)
        {
            arr[i] = nullptr;
        }

    }

    //Destructor
    ~Hashtable(){
        for (int i = 0; i &lt; 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&amp; s){
        //Initialize a new node for the new input
        HashNode* temp = new HashNode{s};

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

        if (load_factor() &gt; 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.
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 &lt; oldCap; ++i) {
    if (oldArr[i] != nullptr) {
      put(oldArr[i]-&gt;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.