3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.