Хеш-таблица
Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [math]H[/math] , элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код [math]i = h(key)[/math] играет роль индекса в массиве [math]H[/math] , а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.
Вероятность коллизий при вставке в хеш-таблицу превышает 50%
Пусть хеш-таблица имеет размер [math]len[/math] и в нее добавляют [math]n[/math] элементов. Рассмотрим [math]
‘(n)[/math] — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна [math]1 — \dfrac[/math] . Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна [math]1 — \dfrac[/math] . Рассуждая аналогичным образом, получим формулу: [math]
‘(n) = \left( 1 — \dfrac\right )\cdot \left( 1 — \dfrac\right )\dots\left( 1 — \dfrac\right ) = \dfrac> = \dfrac \cdot \left (len — n \right)!>[/math]
Тогда [math]
(n)[/math] — вероятность возникновения коллизии равна: [math]p(n) = 1 —
‘(n)[/math] ,
Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с прямой адресацией; в них все операции, такие как: поиск, вставка и удаление работают за [math]O(1)[/math] .
Если мы поделим число хранимых элементов на размер массива [math]H[/math] (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. load factor). От этого параметра зависит среднее время выполнения операций.
Хеширование
Хеширование (англ. hashing) — класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за [math]O(1)[/math] ). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицей существуют методы для борьбы с ними.
Определение: |
[math]U [/math] — множество объектов (универсум). [math]h : U \rightarrow S = \mathcal 0 \dots m — 1 \mathcal [/math] — называется хеш-функцией, где множество [math]S[/math] хранит ключи из множества [math]U[/math] . Если [math]x \in U[/math] значит [math]h(x) \in S[/math] Коллизия (англ. collision): [math]\exists x \neq y : h(x) = h(y)[/math] |
Виды хеширования
- По способу хранения:
Статическое — фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов,
Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.
- По виду хеш-функции:
Свойства хеш-таблицы
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно [math]\Theta(n)[/math] , но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет [math]O(1)[/math] . А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время [math]O(1)[/math] . При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо перехешировать таблицу: увеличить размер массива [math]H[/math] и заново добавить в новую хеш-таблицу все пары.
Хеширование в современных языках программирования
Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.
- Java
- HashMap [1] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
- HashSet [2] — реализация интерфейса множества с использованием хеш-таблицы,
- LinkedHashMap [3] — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
- unordered_map [4] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
- unordered_set [5] — реализация интерфейса множества с использованием хеш-таблицы.
- dict [6] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
- set [7] — реализация интерфейса множества с использованием хеш-таблицы.
Примечания
- ↑HashMap — Java Platform SE 7
- ↑HashSet — Java Platform SE 7
- ↑LinkedHashMap — Java Platform SE 7
- ↑unordered_map — cplusplus.com
- ↑unordered_set — cplusplus.com
- ↑dictobject.c — https://github.com/python/cpython
- ↑setobject.c — https://hg.python.org
Источники информации
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
- Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г. — 824 стр. — ISBN 0-201-89685-0
- Википедия — Хеш-таблица
- Дискретная математика и алгоритмы
- Хеширование
- Структуры данных
Хеш-таблицы
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто нетерпелось написать пост на данную, столь интересную, тему.
Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.
Мотивация использовать хеш-таблицы
Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.
Контейнер \ операция 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++ хеш-таблицы скрываются под флагом unoredered_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 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()
Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод 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
Немаловажным является поддержание асимптотики 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
Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (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, иначе мы могли бы зациклиться. > return false; >
Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.
bool Remove(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) < arr[h1]->state = false; --size; return true; > h1 = (h1 + h2) % buffer_size; ++i; > return false; >
Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.
Помимо этого в данном методе есть еще одна часть, поддерживающая правильную асимптотику. Это запоминание первого подходящего для вставки элемента (даже если он deleted). Именно туда мы вставим элемент, если в нашей хеш-таблицы нет такого же. Если ни одного deleted-элемента на нашем пути нет, мы создаем новый Node с нашим вставляемым значением.
bool Add(const T& value, const THash1& hash1 = THash1(),const THash2& hash2 = THash2()) < if (size + 1 >int(rehash_size * buffer_size)) Resize(); else if (size_all_non_nullptr > 2 * size) Rehash(); // происходит рехеш, так как слишком много deleted-элементов int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; int first_deleted = -1; // запоминаем первый подходящий (удаленный) элемент while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) return false; // такой элемент уже есть, а значит его нельзя вставлять повторно if (!arr[h1]->state && first_deleted == -1) // находим место для нового элемента first_deleted = h1; h1 = (h1 + h2) % buffer_size; ++i; > if (first_deleted == -1) // если не нашлось подходящего места, создаем новый Node < arr[h1] = new Node(value); ++size_all_non_nullptr; // так как мы заполнили один пробел, не забываем записать, что это место теперь занято >else < arr[first_deleted]->value = value; arr[first_deleted]->state = true; > ++size; // и в любом случае мы увеличили количество элементов return true; >
В заключение приведу полную реализацию хеш-таблицы.
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); >>; template class HashTable < static const int default_size = 8; constexpr static const double rehash_size = 0.75; struct Node < T value; bool state; Node(const T& value_) : value(value_), state(true) <>>; Node** arr; int size; int buffer_size; int size_all_non_nullptr; 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; >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; >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; >~HashTable() < for (int i = 0; i < buffer_size; ++i) if (arr[i]) delete arr[i]; delete[] arr; >bool Add(const T& value, const THash1& hash1 = THash1(),const THash2& hash2 = THash2()) < if (size + 1 >int(rehash_size * buffer_size)) Resize(); else if (size_all_non_nullptr > 2 * size) Rehash(); int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; int first_deleted = -1; while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) return false; if (!arr[h1]->state && first_deleted == -1) first_deleted = h1; h1 = (h1 + h2) % buffer_size; ++i; > if (first_deleted == -1) < arr[h1] = new Node(value); ++size_all_non_nullptr; >else < arr[first_deleted]->value = value; arr[first_deleted]->state = true; > ++size; return true; > bool Remove(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) < arr[h1]->state = false; --size; return true; > h1 = (h1 + h2) % buffer_size; ++i; > return false; > 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; > return false; > >;
Хэш-таблицы. Что это такое и как работают
Мы продолжаем курс по структурам данных, и на этом занятии речь пойдет о новой структуре под названием хэш-таблица. Она обладает поистине впечатляющими характеристиками. Для стандартных операций вставки, чтения и удаления данных она, в среднем, выполняется за константное время O(1), то есть, быстро и не зависимо от размера таблицы (объема данных):
И в этом она превосходит подобные ей структуры: динамические массивы и связные списки. Получается, что хэш-таблица может их полностью заменить? Но не спешите и давайте во всем подробно разберемся. Первым делом рассмотрим принцип работы хэш-таблиц.
Предположим, в продуктовом магазине необходимо хранить товары и выдавать цену по их названиям.
Как это сделать? Из того, что мы знаем на данный момент, вполне подошел бы связный список, т.к. в него достаточно быстро можно добавлять новые товары и удалять ненужные. Правда, поиск будет выполняться линейное время O(n). И это нас не очень устраивает, т.к. товаров в магазине может быть очень много и нам бы хотелось иметь более быстрый доступ к цене товара по его названию. Поэтому сделаем несколько иначе. Единственная из всех рассмотренных структур, которая предоставляет быстрый доступ к элементу за время O(1) – это массивы (и динамические массивы).
Но здесь нас ожидают сразу две проблемы: во-первых, мы знаем названия, но не индексы элементов, а значит, поиск нужного товара займет O(n) времени, и, во-вторых, операции добавления и удаления товара также потребуют O(n) времени. Получается довольно неудачный выбор структуры для данных. Но не спешите с выводами. Давайте пойдем на небольшую хитрость. Придумаем алгоритм, который бы переводил названия товаров в индексы, и тогда, мы получим возможность сразу обращаться к нужной ячейке таблицы (массива), чтобы записать его туда, прочитать оттуда, или удалить, когда это потребуется:
Так вот, алгоритм преобразования некоторой строки в индекс массива получил название хэш-функция, а процесс его работы – хэширование. Отсюда пошло название хэш-таблица.
- для одного и того же ключа (названия товара) должна выдавать одно и то же значение (свойство последовательности);
- для разных ключей (названий товаров) выдавать разные значения (индексы);
- формируемые значения должны находиться в диапазоне от 0 до N-1, где N – размер массива, т.е. индексы должны быть действительными для используемой таблицы;
- возможные ключи (названия) должны равномерно записываться в ячейки таблицы.
Добавление элементов в хэш-таблицу
Давайте предположим, что мы бы хотели по английским буквам получать соответствующие аналоги русских букв. Например:
Ключ Значение a а b б c с d д f ф … … Причем нам наперед неизвестно, сколько именно букв будет храниться в хэш-таблице. Поэтому, чтобы зря не расходовать память, начальный размер таблицы будет иметь m=5 элементов. Сами ячейки таблицы будут хранить адреса на объекты с данными. Если данных нет, то указатели принимают значение NULL. Далее, у нас имеется хэш-функция, которая для каждой буквы латинского алфавита вычисляет индекс в массиве T. Предположим, мы хотим по ключу b записать значение б. На вход хэш-функции подается символ b. На выходе получаем индекс массива, по которому этот ключ должен располагаться в таблице. Пусть это будет индекс 1: Затем, в памяти создается новый объект с ключом b и значенем б, и адрес этого объекта сохраняется во втором элементе таблицы. То есть, массив хранит не сами данные, а ссылки на объекты с данными. Это наиболее частая реализация хэш-таблиц. В результате мы добавили новый ключ b и его значение б в хэш-таблицу. На уровне языков программирования эта операция часто записывается в виде:
T["b"] = "б"
Разумеется, если T – это хэш-таблица. По аналогии можно добавить еще несколько ключей и значений. Например, ключи f, d, u:
И наш массив почти заполнен! В теории хэш-таблиц степень их заполненности определяется коэффициентом: α = n / m где n – количество хранимых ключей (в нашем примере 4); m – размер массива (в нашем примере 5). Получаем, значение степени заполнения таблицы: α = 4 / 5 = 0,8 То есть, пока этот коэффициент меньше единицы, в массиве есть свободные элементы, куда теоретически еще можно добавить новые ключи. Если α = 1, то массив заполнен полностью. Если же α > 1, то число ключей превышает размер хэш-таблицы. (Как такое может быть, мы еще будем говорить.) Итак, на данный момент коэффициент α = 0,8, значит, массив почти заполнен. Что делать дальше? Выход только один: увеличить размер таблицы, то есть, рассматривать массив как динамический и, например, при α близкой к 1 увеличивать его размер в 2 раза. Давайте так и сделаем. Сначала мы должны в памяти создать новый массив длиной в 2 раза больше предыдущего. После этого хэш-функция будет уже выдавать новый диапазон индексов [0; 9]. Поэтому элементы должны не просто копироваться в новый массив, а заново прогоняться через новую хэш-функцию. Получим (как пример):
Только после этого мы сюда можем добавлять новые ключи. Вот общий принцип работы алгоритма добавления ключей и значений в хэш-таблицы. В среднем, эта операция выполняется за фиксированное время O(1).
Разрешение коллизий в хэш-таблицах
Однако, такая идеализированная картина, когда в одной ячейке хранится одно значение, бывает только в простых случаях, когда число ключей невелико и все их можно разнести по разным индексам. На практике же общее возможное число ключей K стремится к бесконечности, их вариации могут быть самыми разными и рано или поздно возникает ситуация, когда разным ключам хэш-функция назначает один и тот же индекс: И избежать этого невозможно, так как алгоритмически мы должны обеспечивать не только различие в индексах, но и равномерность заполнения таблицы. Кроме того, число ячеек M в таблице много меньше возможного числа ключей. Поэтому вполне вероятны ситуации, когда разным ключам назначается один и тот же индекс. Такая ситуация называется коллизией. Спрашивается, как быть в таком случае? Существует два основных метода разрешения коллизий:
- метод цепочек;
- метод открытой адресации.
Самый простой и очевидный способ обработки коллизий – это метод цепочек. Давайте предположим, что в хэш-таблицу T осуществляется добавление следующих пар ключ-значение:
T["b"] = б T["ba"] = ба T["d"] = д T["f"] = ф T["bb"] = бб T["fa"] = фа
И хэш-функция для ключей с одинаковыми первыми буквами выдает одни и те же индексы таблицы. Тогда, чтобы сохранить несколько разных ключей по одному и тому же индексу, формируется двусвязный список, на начало которого ведет указатель ptr. В элементах этого двусвязного списка сохраняются пары ключ-значение. Это и есть принцип разрешения коллизий по методу цепочек. У такого решения есть положительные и отрицательные стороны. К положительным можно отнести простоту реализации. Сформировать двусвязные списки там, где необходимо хранить несколько ключей, не составляет особого труда. Также относительно быстро происходит вставка новых ключей и удаление существующих в таких списках (цепочках). А основным недостатком является возможность появления длинных цепочек в хэш-таблицах. Тогда поиск нужного ключа может занять продолжительное время и преимущества хэш-таблиц будут сведены к нулю. Очевидно, чтобы избежать такого неблагоприятного случая (образования длинных цепочек), нужно правильно выбирать хэш-функцию, которая бы равномерно распределяла возможные ключи по индексам таблицы. Благо, существуют подходы, позволяющие создавать такие функции, но об этом мы еще будем говорить. А сейчас посмотрим, как в хэш-таблицах со списками выполняется поиск и удаление ключей.
Алгоритм поиска ключей
Давайте предположим, что у нас имеется ранее сформированная хэш-таблица с цепочками и в ней требуется взять значение по определенному ключу. Пусть это будет ключ «ba», то есть, нужно выполнить операцию:
val = T["ba"]
Для этого мы подаем ключ «ba» на вход хэш-функции, получаем значение индекса 1 в таблице и видим здесь двусвязный список. На начало этого списка ведет указатель ptr. Сформируем временный указатель:
p = ptr
который также будет ссылаться на начало этого списка. Далее, мы последовательно проходим по элементам этого списка и сравниваем в них ключи на равенство заданного ключа «ba». Этот ключ мы находим во втором элементе списка. На этом поиск останавливается и возвращается значение «ба» этого ключа. Если мы указываем не существующий ключ, например, «t», то либо попадем в пустую ячейку таблицы, либо не найдем этот ключ в списке. Вот так, достаточно просто реализуется алгоритм поиска ключей в хэш-таблице с цепочками.
Алгоритм удаления ключей
Давайте теперь посмотрим, как можно выполнять удаление существующих ключей из хэш-таблицы с цепочками. У нас по-прежнему будет та же самая таблица и мы хотим удалить из нее ключ «ba»:
del T["ba"]
Вначале также подаем этот ключ на вход хэш-функции и получаем индекс 1 в таблице. По этому индексу хранится несколько ключей в двусвязном списке. С помощью временного указателя p находим элемент с ключом «ba». Это второй элемент. И удаляем его. (Как удалять элементы в двухсвязных списках мы с вами уже говорили на предыдущих занятиях). Все, ключ удален из хэш-таблицы. Если происходит удаление единственного ключа в ячейке, например, ключа «d», то проверяется, что в единственном элементе действительно хранится ключ «d», если так, то объект удаляется и ячейка принимает значение NULL. Наконец, если пытаемся удалить не существующий в таблице ключ, например, «s», то либо сразу попадаем в ячейку со значением NULL, либо на цепочку из ключей, в которой ключ «s» будет отсутствовать. В любом случае, при отсутствии ключа никаких действий с таблицей не выполняется и она остается в неизменном виде.
Хеш-таблицы — Python: Cловари и множества
Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары «ключ-значение». В разных языках ему соответствуют разные типы данных. В Python — это Dictionary, в других языках:
- Ruby — Hash
- Lua — Table
- JavaScript — Object
- Elixir/Java — Map
Ассоциативные массивы популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров.
В обычном индексированном массиве значения расположены по индексам, а значит его можно положить в память «как есть». С ассоциативными массивами все работает по-другому. У них нет индексов, которые бы могли определить порядок — значит, и нет простого способа добраться до значений.
Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу.
Хеш-таблица позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует индексированный массив и функцию для хеширования ключей. При этом хеш-таблица — это не просто способ размещать данные в памяти, она включает в себя логику.
В этом уроке мы подробнее поговорим о хеш-таблицах и узнаем, как ассоциативные массивы устроены внутри. Вы поймете, сколько разных процессов происходит в программе, когда мы выполняем подобный простой код:
data = <> data['key'] = 'value'
Что такое хеширование
Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия:
- Найти хеш, то есть хешировать ключ
- Привести ключ к индексу — например, через остаток от деления
Хеширование — операция, которая преобразует любые входные данные в строку или число фиксированной длины. Функция, реализующая алгоритм преобразования, называется «хеш-функцией». При этом результат хеширования называют «хешем» или «хеш-суммой».
Наиболее известны CRC32, MD5, SHA и много других типов хеширования:
# В Python есть библиотека zlib, содержащая алгоритм хеширования crc32 # Этот алгоритм удобен для наглядности import zlib # Любые данные, которые мы хотим хешировать, представляются в виде байтовой строки data = b'Hello, world!' hash = zlib.crc32(data) # Хеш всегда одинаковый для одних и тех же данных print(hash) # => 3957769958
С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 — это хеш, полученный в результате хеширования данных коммита.
При записи в хеш-таблицу сначала нужно получить хеш. Затем его можно преобразовать в индекс массива — например, вычислить остаток от деления:
# Это делается для того, чтобы индексы не были слишком большими # Чем больше размер массива, тем больше памяти он занимает index = abs(hash) % 1000 # по модулю print(index) # => 958
Как хеширование работает изнутри
Рассмотрим, как работает добавление нового значения в ассоциативный массив. Напомним, в Python он представлен типом данных Dictionary. Напишем такой код:
data = <> data['key'] = 'value'
Такой простой код запускает целый сложный процесс. Для простоты рассмотрим его на Python, хотя в реальности все это происходит на более низком уровне. Опишем процесс хеширования без деталей и с упрощениями.
-
Мы создаем ассоциативный массив. Внутри интерпретатора происходит инициализация индексированного массива:
internal = []
data['key'] = 'value'
hash = zlib.crc32(b'key')
index = abs(hash) % 1000
internal[index] = ['key', 'value']
Теперь посмотрим, как работает чтение данных:
data = <> data['key'] = 'value' print(data['key']) # => "value"
Разберем, как этот код работает изнутри.
-
Интерпретатор хеширует ключ. Результатом хеширования становится число:
hash = zlib.crc32(b'key')
index = abs(hash % 1000)
return internal[index] # ['key', 'value']
Коллизии
Ключом в ассоциативном массиве может быть абсолютно любая строка, любой длины и содержания. Но здесь есть одно противоречие:
- Все возможные ключи — это бесконечное множество
- В качестве результата хеш-функция выдает строку фиксированной длины, то есть все выходные значения — это конечное множество
Из этого факта следует, что не для всех входных данных найдется уникальный хеш. На каком-то этапе могут появиться дубли: под одним хешем будут лежать несколько разных значений.
Такую ситуацию принято называть коллизией. Есть несколько способов разрешения коллизий . Каждому способу соответствует свой тип хеш-таблицы:
# Пример коллизии # Хеш-функция возвращает одинаковый хеш для разных строчных данных zlib.crc32(b'aaaaa0.462031558722291') # 1938556049 zlib.crc32(b'aaaaa0.0585754039730588') # 1938556049
Простейший способ разрешения коллизий — это открытая адресация. Она предполагает последовательное перемещение по слотам хеш-таблицы в поисках первого свободного слота, куда значение будет записано.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях: