Реализация изменения размера таблицы ha sh в C ++ - PullRequest
Новая
       93

Реализация изменения размера таблицы ha sh в C ++

0 голосов
/ 23 апреля 2020

У меня проблемы с реализацией функции изменения размера или расширения емкости в c ++. Вот моя функция изменения размера (expandCapacity): 

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

, а вот моя функция вставки: 

    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();
    }
   }

Шаблон K предназначен для ключа, а V - для значения. Таблица ha sh реализована в виде указателя на массив линейных словарей (класс, который я реализовал сам, по сути, представляет собой список пар ключ-значение, в котором есть некоторые дополнительные полезные функции для словарей). Но это не похоже на расширение возможностей. Вместо этого я продолжаю получать сообщение об ошибке «ключ уже существует» - это ошибка времени выполнения, реализованная моим профессором.

1 Ответ

1 голос
/ 23 апреля 2020

Ваш i l oop выполняет слишком много итераций. Цикл основан на новой емкости, когда к данным temp, к которым он обращается, применяются только старые элементы емкости.

...