Изменение размера массива строк в хэш-таблице

Question

Я учусь хэшированию прямо сейчас.Я пытаюсь изменить размер моей хэш-таблицы, когда она заполнена на 80%.Но каждый раз, когда я пытаюсь изменить его размер, я получаю неопределенное поведение или происходит сбой.

Я пытался создать новый массив String с большим количеством полей, а затем я удалял старый, но он не работал.

hashtable.h

class hashtable
{
    public:
        hashtable();
        void insert(string);
        void resize_array();
        int hashfunction(string str);
        string* getArray();

    private:
         int elemts_in_array;
         int table_size;
         string* T;
};

hashtable.cpp

hashtable::hashtable()
{
    // your code (start with a capacity of 10)
    table_size = 10;
    elemts_in_array = 0;
    string *array = new string[table_size];
    T = array;
}


void hashtable::insert(string key)
{
    string* array = getArray();
    int hkey=hashfunction(key);

    float filled = float(elemts_in_array)/float(table_size);
// When the array is more than 80% filled resize it and double the table_size
    if(filled >= 0.8)
    {
        cout << "Resizing Array.." << endl;
        resize_array();
    }
    for(int i=0; i<table_size;i++)
    {
// if the field is empty insert it, else go +1
        if(array[(hkey+i)%table_size] == "")
        {
            array[(hkey+i)%table_size] = key;
            elemts_in_array++;
            break;
        }
        if(array[(hkey+i)%table_size] == key)
        {
          // it is the same element
            break;
        }
    }
}


void hashtable::resize_array()
{
    int old_table_size =table_size;
    table_size*=2; // double the size of the hashtable
    string* old_array= new string[table_size]; // save the old array entries
    old_array = T;

// Apply the old entries in old_array
    for(int i=0; i<table_size;i++)
    {
        old_array[i]= T[i];
    }

//create a new array with double size
    string *new_array = new string[table_size];
//delete the old T
    delete[] T;
    T = new_array;

//re-hash the old entries into the new array with double size (HERE I GOT THE ISSUES)
    for(int i=0; i<table_size/2; i++)
    {
        insert(old_array[i]);
    }
}

иногда моя программа зацикливалась или зависала.Я действительно не знаю, почему это не работает.

Answer 1

Расширение хэш-таблицы - это увеличение количества доступных слотов.Но хеш-функция использует размер таблицы для вычисления хеш-индекса.Если вы расширяете размер таблицы, это означает, что расчеты изменяются, а не только для будущих записей таблицы;для прошлых записей.

Таким образом, алгоритм для расширения должен

1. Определить новый размер и создать эту таблицу (пустую)
2. Перефразируйте все записи, используя новый размер, и переместите их из старой таблицы в новую таблицу.
3. Удалите старую таблицу (которая теперь (концептуально) пуста.
4. Новая таблица становится таблица .

Вот и все. Тем не менее, ваш алгоритм расширения разбит на все виды.

int old_table_size =table_size;
table_size*=2; // double the size of the hashtable
string* old_array = new string[table_size]; // ???? This isn't needed
old_array = T; // ???? the memory allocated above was just leaked. 

Тогда позже ...

//create a new array with double size
string *new_array = new string[table_size];

//delete the old T
delete[] T;       // ??? old table destroyed, now old_array is pointing to ether
T = new_array;    // Finally some sanity returns, but old_array is still broken

И наконец ...

for(int i=0; i<table_size/2; i++)
{
    insert(old_array[i]); // ???? old_array isn't valid anymore. BAD
}

Это чревато проблемами.

Правильное изменение размера

в соответствии с нашим списком задачИсходя из выше, давайте попробуем это:

void hashtable::resize_array()
{
    // remember the old table
    int old_table_size = table_size;
    std::string *old_array = T;

    // build the new table and reset counter
    table_size *= 2;
    T = new std::string[table_size];
    elemts_in_array = 0;

    // now bring the elements over
    for (int i=0; i<old_table_size; ++i)
    {
        if (old_array[i].empty())
            insert(old_array[i]);
    }

    // finally, throw out old array
    delete[] old_array;
}

Вот и все. Вы могли бы сделать это значительно более эффективным, если бы метод insert, который принимает ссылку на rvalue, и использование std::move для пересылки строк без копированияпрямо из старого массива, но основы алгоритма были то, что мы снимали здесь, и я надеюсь, что мУч сделал это через.

Answer 2

Если вы выполните пошаговое выполнение вашей программы с помощью отладчика, вы, вероятно, обнаружите проблему с вашей resize_array функцией.

Когда она копирует записи старой таблицы обратно во вновь выделенный массив, она используетinsert функция.Это имеет некоторые проблемы:

1. вы можете не получить тот же порядок исходных значений из-за разрешения коллизий;
2. функция insert увеличивает размер таблицы, таким образомв конечном итоге он подумает, что в нем вдвое больше записей, чем вы изначально вставили.

Теперь может произойти сбой, поскольку insert снова достигнет предела увеличения таблицы.Цикл повторяется до тех пор, пока вы не получите переполнение стека или не исчерпаете память.

Правильный способ копирования обратно в строки:

for(int i = 0; i < table_size / 2; i++)
{
    T[i] = old_array[i];
}

Но есть еще одна проблема, котораяможет произойти сбой, прежде чем это произойдет.Сначала вы сохранили свои значения следующим образом:

for(int i=0; i<table_size;i++)
{
    old_array[i]= T[i];
}

Обратите внимание, что table_size уже удвоено, и поэтому вы получите доступ после конца T.Вместо этого вы должны были зациклить old_table_size.

У вас также есть некоторое ненужное копирование.Если вы собираетесь перераспределить T, просто сделайте это:

void hashtable::resize_array()
{
    int old_table_size = table_size;
    table_size *= 2;

    string* old_T = T;
    T = new string[table_size];
    for (int i = 0; i < old_table_size; i++)
    {
        std::swap(T[i], old_T[i]);   // or in C++11 assign with std::move
    }
    delete[] old_T;
}