Хеш-таблицы [Иван Кисляков Программист] (fb2) читать постранично, страница - 2

struct HashFunction2

{

    int operator()(const std::string& s, int table_size) const

    {

        return HashFunctionHorner(s, table_size, table_size + 1);

    }

};

Чтобы идти дальше, нам необходимо разобраться с проблемой: что же будет, если мы удалим элемент из таблицы? Так вот, его нужно пометить флагом deleted, но просто удалять его безвозвратно нельзя. Ведь если мы так сделаем, то при попытке найти элемент (значение хеш-функции которого совпадет с ее значением у нашего удаленного элемента) мы сразу наткнемся на пустую ячейку. А это значит, что такого элемента и не было никогда, хотя, он лежит, просто где-то дальше в массиве. Это основная сложность использования данного метода решения коллизий.

Помня о данной проблеме построим наш класс.

template <class T, class THash1 = HashFunction1, class THash2 = HashFunction2>

class HashTable

{

    static const int default_size = 8; // начальный размер нашей таблицы

    constexpr static const double rehash_size = 0.75; // коэффициент, при котором произойдет увеличение таблицы

    struct Node

    {

        T value;

        bool state; // если значение флага state = false, значит элемент массива был удален (deleted)

        Node(const T& value_) : value(value_), state(true) {}

    };

    Node** arr; // соответственно в массиве будут хранится структуры Node*

    int size;   // сколько элементов у нас сейчас в массиве (без учета deleted)

    int buffer_size; // размер самого массива, сколько памяти выделено под хранение нашей таблицы

    int size_all_non_nullptr; // сколько элементов у нас сейчас в массиве (с учетом deleted)

};

На данном этапе мы уже более-менее поняли, что у нас будет храниться в таблице. Переходим к реализации служебных методов.

...

public:

    HashTable()

    {

        buffer_size = default_size;

        size = 0;

        size_all_non_nullptr = 0;

        arr = new Node*[buffer_size];

        for (int i = 0; i < buffer_size; ++i)

            arr[i] = nullptr; // заполняем nullptr - то есть если значение отсутствует, и никто раньше по этому адресу не обращался

    }

    ~HashTable()

    {

        for (int i = 0; i < buffer_size; ++i)

            if (arr[i])

                delete arr[i];

        delete[] arr;

    }

Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

Увеличиваем размер мы стандартно вдвое.

void Resize()

    {

        int past_buffer_size = buffer_size;

        buffer_size *= 2;

        size_all_non_nullptr = 0;

        size = 0;

        Node** arr2 = new Node * [buffer_size];

        for (int i = 0; i < buffer_size; ++i)

            arr2[i] = nullptr;

        std::swap(arr, arr2);

        for (int i = 0; i < past_buffer_size; ++i)

        {

            if (arr2[i] && arr2[i]->state)

                Add(arr2[i]->value); // добавляем элементы в новый массив

        }

        // удаление предыдущего массива

        for (int i = 0; i < past_buffer_size; ++i)

            if (arr2[i])

                delete arr2[i];

        delete[] arr2;

    }

Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешем (как мы помним, мы уже выделяли под это очень странные переменные).

Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.

Но к чему слова, код все разъяснит:

void Rehash()

    {

        size_all_non_nullptr = 0;

        size = 0;

        Node** arr2 = new Node * [buffer_size];

        for (int i = 0; i < buffer_size; ++i)

            arr2[i] = nullptr;

        std::swap(arr, arr2);

        for (int i = 0; i < buffer_size; ++i)

        {

            if (arr2[i] && arr2[i]->state)

                Add(arr2[i]->value);

        }

        // удаление предыдущего массива

        for (int i = 0; i < buffer_size; ++i)

            if (arr2[i])

                delete arr2[i];

        delete[] arr2;

    }

Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

Начнем с самого простого — метод Find элемент по значению.

bool Find(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2())

    {

        int h1 = hash1(value, buffer_size); // значение, отвечающее за начальную позицию

        int h2 = hash2(value, buffer_size); // значение, ответственное за "шаг" по таблице

        int i = 0;

        while (arr[h1] != nullptr && i < buffer_size)

        {

            if (arr[h1]->value == value && arr[h1]->state)

                return true; // такой элемент есть

            h1 = (h1 + h2) % buffer_size;

            ++i; // если у нас i >=  buffer_size, значит мы уже обошли абсолютно все ячейки, именно для этого мы считаем i, иначе мы могли бы