Что такое хэш таблица
Перейти к содержимому

Что такое хэш таблица

  • автор:

Хеш-таблицы

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

Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.

image

Мотивация использовать хеш-таблицы

Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.

Контейнер \ операция 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; > >;

Хеш-таблица

Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [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] — реализация интерфейса множества с использованием хеш-таблицы.

    Примечания

    1. ↑HashMap — Java Platform SE 7
    2. ↑HashSet — Java Platform SE 7
    3. ↑LinkedHashMap — Java Platform SE 7
    4. ↑unordered_map — cplusplus.com
    5. ↑unordered_set — cplusplus.com
    6. ↑dictobject.c — https://github.com/python/cpython
    7. ↑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
    • Википедия — Хеш-таблица
    • Дискретная математика и алгоритмы
    • Хеширование
    • Структуры данных

    Хеш-таблицы, деревья и префиксные деревья

    Хеш-таблица — это структура данных для хранения пар ключей и их значений. По сути она представляет собой массив, где местоположение элемента зависит от значения самого элемента. Связь между значением элемента и его позицией в хеш-таблице задает хеш-функция. Важное свойство хеш-таблицы: поиск, вставка и удаление элементов из таблицы выполняются за фиксированное время, то есть О(1), то есть они нужны тогда, когда максимально важна скорость этих операций.

    Хеш-таблицы, деревья и префиксные деревья - 1

    В примере на картинке позиция каждого слова в хеш-таблице зависит от порядкового номера первой буквы этого слова в английском алфавите.

    Хеш-функция — это функция, которая принимает в качестве аргумента какой-то элемент (который нужно вставить в хеш-таблицу), а в результате выдает позицию заданного элемента в хеш-таблицы.

    Хеш-таблицы, деревья и префиксные деревья - 2

    По сути она сопоставляет ключи индексам массива. Например, на картинке выше мы видим, что хеш-функция сопоставила ключ ‘banana’ с индексом 1.

    Но что происходит под капотом?

    Хеш-функция принимает ключ на вход и вычисляет индекс массива, исходя из внутренних свойств этого ключа.

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

    Примеры хеш-функций: порядковый номер первой буквы слова в алфавите, остаток от деления на 13 и тому подобное.

    Java-университет

    Ниже приведены код хеш-функции на основе первой буквы в строке

    int hash_function (char * key)

    Коллизии (столкновения)

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

    Хеш-таблицы, деревья и префиксные деревья - 3

    Индекс Berry ссылается на 1, как и банан. Это пример столкновения, результат хеширования двух ключей к одному индексу. Даже если ваш хеш-табличка больше, чем ваш набор данных, и вы выбрали хорошую хеш-функцию, вам нужен план борьбы со столкновениями, если и когда они возникнут.
    Полученное новое значение также нужно куда-то записать, и для этого нужно определить, куда именно оно будет записано. Это называется решением коллизии.

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

    Линейное зондирование заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция.

    Хеш-таблицы, деревья и префиксные деревья - 4

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

    Хеш-таблицы, деревья и префиксные деревья - 5

    Префиксное дерево

    Префиксное дерево (trie) — структура данных, в которой путь от корня дерева к листу (последнему элементу) дерева определяет строку.
    Слово «trie» происходит от слова «retrieval» (извлечение), но обычно произносится как «try». Для наших целей узлы в trie являются массивами. Мы можем использовать trie для хранения словаря слов, как показано на этой диаграмме.

    Хеш-таблицы, деревья и префиксные деревья - 6

    В этом trie каждый индекс в массиве обозначает букву алфавита. Каждый из этих индексов также указывает на другой массив букв. Сверху мы сохраняем имена известных ученых, например. Менделя, Менделеева, Павлова, Пастера и Тьюринга. Символ Δ обозначает конец имени. Мы должны следить за тем, где заканчиваются слова, так что если одно слово действительно содержит другое слово (например, Менделеев и Мендель), мы знаем, что оба слова существуют. В коде символ Δ может быть логическим флагом в каждом узле.

    Таким образом, при прохождении дерева сверху вниз формируются слова.

    Описание структуры узла префиксного дерева — ниже. Заметьте, мы фактически не сохраняем слова в trie, мы просто сохраняем последовательность указателей и логическое значение.

    typedef struct node < // Маркер конца слова bool is_word; // Указатели на другие элементы struct node * children [27]; >Node;

    Пример работы с префиксным деревом

    Есть следующего вида префиксальное дерево, в котором есть слова bat и zoom :

    Хеш-таблицы, деревья и префиксные деревья - 7

    Давайте рассмотрим пример поиска ключа «bat» в этом trie. Переходя по последовательным ссылкам сверху вниз, пока не встретим маркер конца слова, получим слово bat:

    Хеш-таблицы, деревья и префиксные деревья - 8

    Мы начнем поиск в корневом узле. Берём первую букву нашего ключа «b» и ищем соответствующее место в нашем дочернем массиве. Мы рассмотрим второй индекс — индекс 1 — для «b». В общем случае, если у нас есть алфавитный символ c, мы можем определить соответствие в дочернем массиве, используя такую формулу:

    int index = tolower (c) - 'a';

    В этом случае указатель в нашем дочернем массиве с индексом 1 не является NULL, поэтому мы продолжим поиск ключа «bat». Если мы однажды наткнёмся на указатель NULL в правильном месте дочернего массива, тогда, смотря на ключ, мы должны были бы сказать, что мы ничего не смогли найти для этого ключа.

    Хеш-таблицы, деревья и префиксные деревья - 9

    Теперь мы возьмем вторую букву нашего ключа «a» и продолжим следовать по указателям, пока не дойдем до конца нашего ключа.

    Хеш-таблицы, деревья и префиксные деревья - 10

    Теперь (сюрприз!) мы возьмем третью букву нашего ключа, «t», и продолжим идти по указателям, пока не дойдем до конца нашего ключа.

    Хеш-таблицы, деревья и префиксные деревья - 11

    Если мы дойдем до конца ключа, и не попадём в «тупик» (NULL-указатель), как здесь, то нам остается только проверить еще одну вещь: был ли этот ключ фактически сохранен в trie? На нашей диаграмме это обозначается галочкой, означающей, что bool is_word = true .

    Хеш-таблицы, деревья и префиксные деревья - 12

    Обратите внимание, на то, что ключ «zoo» отсутствует в словаре, хотя мы смогли дойти до конца этого ключа, не попав в тупик.

    Хеш-таблицы, деревья и префиксные деревья - 13

    Точно так же, если бы мы попытались найти ключ «bath», индекс массива массива от второго до последнего узла, соответствующий букве Н, содержал бы указатель NULL, поэтому «bath» отсутствует в словаре.

    Давайте рассмотрим, как можно вставить элемент в префиксное дерево. В некотором смысле процесс вставки похож на процесс поиска.

    Для того чтобы вставить слово zoo в массив, необходимо начать с корневого узла, следуя по указателям, соответствующим буквам нашего ключа, проходим по списку и устанавливаем маркер:

    Хеш-таблицы, деревья и префиксные деревья - 14

    К счастью, мы можем следить за указателями до конца ключа.

    Хеш-таблицы, деревья и префиксные деревья - 15

    Хеш-таблицы, деревья и префиксные деревья - 16

    Поскольку «zoo» является префиксом слова «zoom», которое хранится в нашем словаре, нам не нужно выделять новые узлы. Мы можем просто установить is_word в true на соответствующем узле.

    Хеш-таблицы, деревья и префиксные деревья - 17

    А если бы мы захотели добавить в дерево слово bath, то, пройдя по всем указателям, мы бы зашли в тупик прежде, чем добрались до конца ключа.

    Хеш-таблицы, деревья и префиксные деревья - 18

    Поэтому нам нужно определить один новый узел для каждой оставшейся буквы нашего ключа.

    Хеш-таблицы, деревья и префиксные деревья - 19

    Затем нам нужно будет сделать индекс h предыдущего узла ссылкой на этот новый узел. То есть в последнем элементе слова bat создаем ссылку, указывающую на букву h:

    Хеш-таблицы, деревья и префиксные деревья - 20

    Наконец, мы устанавливаем значение true для is_word bool нового узла. Если предположить, что длина ключа ограничена фиксированной константой, ясно, что и поиск, и вставка выполняются за фиксированное время. Обратите внимание, что количество элементов, хранящихся в trie, не влияет на время поиска или вставки, влияние оказывает только длина ключа. В отличие от этого добавление записей в хеш-таблицу имеет тенденцию замедления поиска в будущем.

    Хеш-таблицы, деревья и префиксные деревья - 21

    Естественно, благоприятная асимптотическая сложность привлекает, однако не стоит обольщаться, на практике всё не так радужно. Мы также должны учитывать, что для хранения слова в trie нам нужно, в худшем случае, несколько узлов, пропорциональных длине самого слова. Попытки, как правило, требуют много места, и в этом отличие этой структуры данных от, скажем, хеш-таблиц, где нам нужен только один новый узел для хранения пары ключ-значение.

    Хеш-таблица, хеш-функция в Swift

    Материал из Википедии — свободной энциклопедии

    Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

    Сегодня мы рассмотрим, что такое хеш-таблица, как она работает и что делает ее полезной. Допустим, вам нужно найти чей-то номер телефона в телефонной книге. Как вы это сделаете? Вы берете фамилию этого человека, ищете номер телефона по заглавной букве .

    Хеш-таблицы делают то же самое, только вместо списка имен, отсортирванных по алфавиту, они используют нечто называемое функцией хеширования, для хранения и поиска людей. Это лучше, чем алфавит, потому что вам не нужно реорганизовывать список каждый раз, когда вы добавляете новую запись. И пока у вас есть хороший алгоритм хеширования, он работает молниеносно, вот почему хеш-таблицы являются наиболее популярной структурой для быстрого поиска информации. Давайте рассмотрим, как они работают.

    Как работает хеш-функция?

    Итак, построение хеш-таблицы состоит из трех частей: хеш-функция, преобразование хеша в индекс и обработка коллизий. Сначала давайте рассмотрим, что такое «хорошая» хеш-функция.

    Хеш-функция (англ. hash function от hash — «превращать в фарш», «мешанина»), или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

    Простыми словами: Хеш-функция — это метод, который берет любой объект и вычисляет почти уникальное числовое представление объекта, которое может быть использовано в качестве ключа для последующего поиска. Хорошая хеш-функция работает быстро. Она дает хорошее равномерное распределение чисел и минимизирует коллизии. Подробнее об этом позже. Каждый объект, который мы храним в хеш-таблице, должен иметь хеш-функцию, которая отвечает за генерацию собственного хеш-кода. Все базовые конструкции в Swift такие как String, Int, Float…и тд. уже имеют встроенную хеш-функцию, которой мы можем воспользоваться чтобы вычислить хеш-код . Например, если нам нужно хеш-значение строки “abc”, мы можем просто вызвать встроенную хеш-функцию и получить ключ для этой строки.

    let stringsAreHashable = "abc".hashValue

    Мы можем сделать то же самое с обычными объектами, взять почти любой объект и создать для него хеш-функцию, просто взяв атрибуты этого объекта, сложив их вместе, а затем умножив на «хорошее» простое число(Int).

    struct GridPoint < var x: Int var y: Int var hashValue: Int < return x.hashValue ^ y.hashValue &* 16777619 >> let mainBase = GridPoint(x: 131, y: 541) let hashCode = mainBase.hashValue

    Именно так вычисляли хеши в былые времена, но на самом деле мы больше этого не делаем. Теперь мы просто реализуем хешируемый протокол , а Swift делает все остальное за нас. Независимо от того, делаем ли мы хеширование или Swift делает его за нас, вот что происходит за кулисами — мы создаем ключ, который мы можем использовать и искать в нашей хеш-таблице. Теперь, когда у нас есть функция хеширования, следующее, что нам нужно сделать, это записать хеш в массив, который мы будем использовать для хранения всех наших поисков. Другими словами, нам нужно преобразовать его в индекс.

    Преобразование в Индекс.

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

    Вместо этого мы берем все эти возможные хеш-коды и преобразуем их в массив гораздо меньшего размера, применяя оператор modulus(%-остаток от деления). Оператор modulus работает следующим образом: берется любое заданное число, делится на оператор modulus и возвращается остаток.

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

    Еще одна особенность Swift — вы заметите, что наш хеш-код меняется каждый раз, когда мы вычисляем или выполняем нашу программу. Это происходит потому, что «под капотом» Swift динамически вычисляет хеш-значение на основе времени выполнения. Поэтому не гарантируется, что ваши хеш-значения будут одинаковыми при разных запусках вашей программы.

    Swift и динамические хеш-значения

    Если вы прочитаете документацию Swift по хешированию, то увидите, что возвращаемые хеш-значения Swift иногда генерируются динамически. То есть, когда вы вызываете hashValue на объекте Swift, вы можете получить другое значение. Не сломает ли это HashMap, который полагается на получение одного и того же хеш-значения каждый раз? Нет. Причина, по которой Swift ввел это динамическое хеширование, заключается в предотвращении некоторых видов атак безопасности на наши Swift-программы. Разработчики сделали так, что пока вы вызываете hashValue в одном и том же времени выполнения вашей программы, вам гарантировано одно и то же hashValue. Поэтому до тех пор, пока мы не храним значения hashValue между запусками наших программ (чего мы обычно никогда не делаем), хеширование в Swift работает отлично и безопасно.

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

    Работа с коллизиями.

    Пример коллизии.

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

    И всякий раз, когда мы получаем два объекта, которые сходятся в одном хеше, мы добавляем их в связанный список. А затем, когда нам нужно найти их, мы приходим к этому индексу, а затем проходим по нашему связанному списку, пока не найдем искомый объект.

    Использование связного списка в хеш-таблицах.

    Время выполнения

    Хеш-таблица, характеристики времени выполнения, как правило, O(1). Предположим для собеседования, что у вас есть хорошая хеш-таблица с хорошей функцией хеширования, хорошим распределением чисел, и вы можете описать характеристики времени выполнения поиска, вставки и удаления как O(1). Иногда, в худшем случае, вы можете получить много коллизий, и в этом случае время выполнения может занять больше времени, и мы бы описали его как O(n).

    Заключение:

    Подведем итоги. Что нужно знать для собеседования?

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

    В Swift есть встроенная хеш-функциия.

    Как обрабатываются коллизии, периодически мы получаем два хеша или два объекта, которые хешируются на один и тот же индекс. Мы просто используем связный список. Мы соединяем их в цепочку. И это самый распространенный способ обработки коллизий в хеш-таблице.

    Тонкая вещь, которую нужно знать, заключается в том, что хеш-таблица не использует свой хеш в качестве индекса хеш-таблицы. Есть шаг, когда мы берем хеш для объекта, применяем оператор модуляции, чтобы он поместился в индекс. Можно ошибится, что хеш используется в качестве индекса, но обычно это не так.

    Вот и все, если вы понимаете эти концепции, вы действительно хорошо подготовлены к той части собеседования, посвященной хеш-таблицам.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *