Иван Кисляков ХЕШ-ТАБЛИЦЫ
Предисловие
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто не терпелось написать пост на данную, столь интересную, тему. Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.Мотивация использовать хеш-таблицы
Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.Контейнер \ операция insert remove find Array O(N) O(N) O(N) List O(1) O(1) O(N) Sorted array O(N) O(N) O(logN) Бинарное дерево поиска O(logN) O(logN) O(logN) Хеш-таблица O(1) O(1) O(1) Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях
Из этой таблицы очень хорошо понятно, почему же стоит использовать хеш-таблицы. Но тогда возникает противоположный вопрос: почему же тогда ими не пользуются постоянно? Ответ очень прост: как и всегда, невозможно получить все сразу, а именно: и скорость, и память. Хеш-таблицы тяжеловесные, и, хоть они и быстро отвечают на вопросы основных операций, пользоваться ими все время очень затратно.
Понятие хеш-таблицы
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unordered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица. Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены. Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент. Теперь стало понятно, почему же это именно хеш-таблица.Проблема коллизии
Естественно, возникает вопрос, почему невозможно такое, что мы попадем дважды в одну ячейку массива, ведь представить функцию, которая ставит в сравнение каждому элементу совершенно различные натуральные числа просто невозможно. Именно так возникает проблема коллизии, или проблемы, когда хеш-функция выдает одинаковое натуральное число для разных элементов. Существует несколько решений данной проблемы: метод цепочек и метод двойного хеширования. В данной статье я постараюсь рассказать о втором методе, как о более красивом и, возможно, более сложном.Решения проблемы коллизии методом двойного хеширования
Мы будем (как несложно догадаться из названия) использовать две хеш-функции, возвращающие взаимопростые натуральные числа. Одна хеш-функция (при входе g) будет возвращать натуральное число s, которое будет для нас начальным. То есть первое, что мы сделаем, попробуем поставить элемент g на позицию s в нашем массиве. Но что, если это место уже занято? Именно здесь нам пригодится вторая хеш-функция, которая будет возвращать t — шаг, с которым мы будем в дальнейшем искать место, куда бы поставить элемент g. Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива). Наконец мы объяснили все самые важные моменты, можно перейти к непосредственному написанию кода, где уже можно будет рассмотреть все оставшиеся нюансы. Ну а строгое математическое доказательство корректности использования двойного хеширования можно найти тут.Реализация хеш-таблицы
Для наглядности будем реализовывать хеш-таблицу, хранящую строки. Начнем с определения самих хеш-функций, реализуем их методом Горнера. Важным параметром корректности хеш-функции является то, что возвращаемое значение должно быть взаимопросто с размером таблицы. Для уменьшения дублирования кода, будем использовать две структуры, ссылающиеся на реализацию самой хеш-функции.int HashFunctionHorner(const std::string& s, int table_size, const int key) { int hash_result = 0; for (int i = 0; s[i] != s.size(); ++i) hash_result = (key * hash_result + s[i]) % table_size; hash_result = (hash_result * 2 + 1) % table_size; return hash_result; } struct HashFunction1 { int operator()(const std::string& s, int table_size) const { return HashFunctionHorner(s, table_size, table_size - 1); // ключи должны быть взаимопросты, используем числа // <размер таблицы> плюс и минус один. } }; 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] =