Implementing resize of a hash table in C++

Question

I'm having trouble implementing the resize or expand capacity function in c++. Here's my resize(expandCapacity) function:

    template <typename K, typename V> void HashTable<K, V>::expandCapacity() {
    LinearDictionary<K,V>* temp = this->hashTable;
    this->capacity *= 2;
    this->hashTable = new LinearDictionary<K,V>[this->capacity];
    for(int i = 0; i < capacity; i++){
      vector<pair<K,V>> items = temp[i].getItems();
      for(int j = 0;j < temp[i].getSize(); i++){
        K key = items[j].first;
        V value = items[j].second;
        int bucket = hash(key, capacity);
        this->hashTable[bucket].insert(key, value);
      }
    }
    delete temp;
}

and here's my insert function:

    template <typename K, typename V> void HashTable<K, V>::insert(K key, V value) {
    int bucket = hash(key, capacity);
    if(this->hashTable[bucket].contains(key)){
        throw runtime_error("This key already exists");
      }
    this->hashTable[bucket].insert(key,value);
    size+=1;
    float loadFactor = (float)(size)/(float)(capacity);
    if(loadFactor >= maxLoadFactor){
      this->expandCapacity();
    }
   }

The template K is for key and V is for value. The hash table is implemented as a pointer to an array of linear dictionaries (a class I implemented myself that is essentially a list of key value pairs, that has some additional useful functions for dictionaries). But this doesn't seem to expand the capacity. Instead I keep getting an error "key already exists" - which is a runtime error implemented by my professor.

As an aside, a relatively easy way to implement the expand operation is to first implement a swap_contents(HashTable & rhs) method, that just swaps the member variables of (this) and (rhs). Once you have that implemented, you can implement expandCapacity() simply by declaring a temporary second HashTable object with a larger array size, calling temp=*this; and then calling swap_contents(temp) — Jeremy Friesner

1201ProgramAlarm 1201ProgramAlarm · Accepted Answer · 2020-04-23T01:42:59

Your i loop is doing too many iterations. It is looping based on the new capacity, when the temp data it is accessing only has old capacity elements.

Implementing resize of a hash table in C++

1 Answers