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.

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.