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

Хеш-таблицы — 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 студентов

Наши выпускники работают в компаниях:

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

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

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

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

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

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

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

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

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

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

int hash_function (char * key)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Естественно, благоприятная асимптотическая сложность привлекает, однако не стоит обольщаться, на практике всё не так радужно. Мы также должны учитывать, что для хранения слова в 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 есть встроенная хеш-функциия.

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

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

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

Хеш-таблица в C/C++: полная реализация

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

Индекс хеш-таблицы позволяет нам сохранить значение в соответствующем месте.

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

Главное преимущество использования хеш-таблицы – очень короткое время доступа. Конфликты иногда могут возникать, но шансы практически равны нулю, если выбрать очень хорошую хэш-функцию.

Итак, в среднем временная сложность представляет собой постоянное время доступа O(1) – это называется амортизационной временной сложностью.

C++ STL (стандартная библиотека шаблонов) использует структуру данных std::unordered_map(), которая реализует все эти функции хэш-таблицы.

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

Давайте разберемся подробнее в деталях реализации таблиц. Любая реализация хеш-таблицы состоит из следующих трех компонентов:

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

Выбор хэш-функции

Первый шаг — выбрать достаточно хорошую хеш-функцию с низкой вероятностью возникновения коллизии.

Но для иллюстрации в этом мануале мы сделаем все наоборот – выберем плохую функцию и посмотрим, что получится.

В этой статье мы будем работать только со строками (или массивами символов).

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

#define CAPACITY 50000 // Size of the Hash Table unsigned long hash_function(char* str)

Вы можете проверить эту функцию для разных строк и увидеть, возникают коллизии или нет. Например, строки «Hel» и «Cau» будут конфликтовать, так как они имеют одинаковое значение ASCII.

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

Определение структуры данных хеш-таблицы

Хеш-таблица — это массив элементов, которые сами по себе являются парой .

Давайте теперь определим структуру нашего элемента.

typedef struct Ht_item Ht_item; // Define the Hash Table Item here struct Ht_item < char* key; char* value; >;

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

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

typedef struct HashTable HashTable; // Define the Hash Table here struct HashTable < // Contains an array of pointers // to items Ht_item** items; int size; int count; >;

Создание хеш-таблицы и ее элементов

Чтобы создать в памяти новую хеш-таблицу и ее элементы, нам нужны функции.

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

Ht_item* create_item(char* key, char* value) < // Creates a pointer to a new hash table item Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; >

Теперь давайте напишем код для создания таблицы. Этот код выделяет память для структуры-оболочки HashTable и устанавливает для всех ее элементов значение NULL (поскольку они не используются).

HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; return table; >

Мы почти закончили с этой частью. Как программист C/C++, вы обязаны освобождать выделенную память с помощью malloc(), calloc().

Давайте же напишем функции, которые освобождают элемент и всю таблицу.

void free_item(Ht_item* item) < // Frees an item free(item->key); free(item->value); free(item); > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item != NULL) free_item(item); > free(table->items); free(table); >

Итак, мы завершили работу над нашей функциональной хеш-таблицей. Давайте теперь начнем писать методы insert(), search() и delete().

Вставка в хеш-таблицу

Сейчас мы создадим функцию ht_insert(), которая выполнит задачу вставки за нас.

Она принимает в качестве параметров указатель HashTable, ключ и значение.

void ht_insert(HashTable* table, char* key, char* value);

Далее нужно выполнить определенные шаги, связанные с функцией вставки.

Создать элемент на основе пары .

1. Вычислить индекс на основе хеш-функции
2. Путем сравнения ключа проверить, занят ли данный индекс или еще нет.
3. Если он не занят, мы можем напрямую вставить его в index
4. В противном случае возникает коллизия, и нам нужно ее обработать

О том, как обрабатывать коллизии, мы поговорим немного позже, после того, как создадим исходную модель.

Первый шаг прост. Мы напрямую вызываем create_item(key, value).

int index = hash_function(key);

Второй и третий шаги для получения индекса используют hash_function(key). Если мы вставляем ключ в первый раз, элемент должен быть NULL. В противном случае либо точная пара «ключ: значение» уже существует, либо это коллизия.

В этом случае мы определяем другую функцию handle_collision(), которая, как следует из названия, обработает эту потенциальную коллизию.

// Create the item Ht_item* item = create_item(key, value); // Compute the index int index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) < // Key does not exist. if (table->count == table->size) < // Hash Table Full printf("Insert Error: Hash Table is full\n"); free_item(item); return; >// Insert directly table->items[index] = item; table->count++; >

Давайте рассмотрим первый сценарий, где пара «ключ: значение» уже существует (то есть такой же элемент уже был вставлен в таблицу ранее). В этом случае мы всего лишь должны обновить значение элемента, просто присвоить ему новое значение.

if (current_item == NULL) < . . >else < // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) < strcpy(table->items[index]->value, value); return; > else < // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, item); return; >>

Итак, функция вставки (без коллизий) теперь выглядит примерно так:

void handle_collision(HashTable* table, Ht_item* item) < >void ht_insert(HashTable* table, char* key, char* value) < // Create the item Ht_item* item = create_item(key, value); Ht_item* current_item = table->items[index]; if (current_item == NULL) < // Key does not exist. if (table->count == table->size) < // Hash Table Full printf("Insert Error: Hash Table is full\n"); return; >// Insert directly table->items[index] = item; table->count++; > else < // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) < strcpy(table->items[index]->value, value); return; > else < // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, item); return; >> >

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

Если мы хотим проверить правильность вставки, мы должны определить функцию поиска, которая проверяет, существует ключ или нет, и возвращает соответствующее значение, если он существует.

char* ht_search(HastTable* table, char* key);

Логика очень проста. Функция просто переходит к элементам, котороые не являются NULL, и сравнивает ключ. В противном случае она вернет NULL.

char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); Ht_item* item = table->items[index]; // Ensure that we move to a non NULL item if (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; > return NULL; >

Тестирование базовой модели

Давайте проверим, правильно ли работает то, что мы муже написали. Для этого мы используем программу-драйвер main().

Чтобы проиллюстрировать, как все работает, добавим еще одну функцию print_table(), которая выводит хеш-таблицу.

#include #include #include #define CAPACITY 50000 // Size of the Hash Table unsigned long hash_function(char* str) < unsigned long i = 0; for (int j=0; str[j]; j++) i += str[j]; return i % CAPACITY; >typedef struct Ht_item Ht_item; // Define the Hash Table Item here struct Ht_item < char* key; char* value; >; typedef struct HashTable HashTable; // Define the Hash Table here struct HashTable < // Contains an array of pointers // to items Ht_item** items; int size; int count; >; Ht_item* create_item(char* key, char* value) < // Creates a pointer to a new hash table item Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; > HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; return table; > void free_item(Ht_item* item) < // Frees an item free(item->key); free(item->value); free(item); > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item != NULL) free_item(item); > free(table->items); free(table); > void handle_collision(HashTable* table, unsigned long index, Ht_item* item) < >void ht_insert(HashTable* table, char* key, char* value) < // Create the item Ht_item* item = create_item(key, value); // Compute the index unsigned long index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) < // Key does not exist. if (table->count == table->size) < // Hash Table Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; >// Insert directly table->items[index] = item; table->count++; > else < // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) < strcpy(table->items[index]->value, value); return; > else < // Scenario 2: Collision // We will handle case this a bit later handle_collision(table, index, item); return; >> > char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); Ht_item* item = table->items[index]; // Ensure that we move to a non NULL item if (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; > return NULL; > void print_search(HashTable* table, char* key) < char* val; if ((val = ht_search(table, key)) == NULL) < printf("Key:%s does not exist\n", key); return; >else < printf("Key:%s, Value:%s\n", key, val); >> void print_table(HashTable* table) < printf("\nHash Table\n-------------------\n"); for (int i=0; isize; i++) < if (table->items[i]) < printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i]->key, table->items[i]->value); > > printf(«——————-\n\n»); > int main()

В результате мы получим:

Key:1, Value:First address Key:2, Value:Second address Key:3 does not exist Hash Table ------------------- Index:49, Key:1, Value:First address Index:50, Key:2, Value:Second address -------------------

Замечательно! Кажется, все работает так, как мы и ожидали. Теперь давайте перейдем к обработке коллизий.

Разрешение коллизий

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

Мы создадим эти цепочки с помощью связных списков.

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

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

Давайте же приступим к реализации связанного списка.

typedef struct LinkedList LinkedList; // Define the Linkedlist here struct LinkedList < Ht_item* item; LinkedList* next; >; LinkedList* allocate_list () < // Allocates memory for a Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; >LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) < // Inserts the item onto the Linked List if (!list) < LinkedList* head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; > else if (list->next == NULL) < LinkedList* node = allocate_list(); node->item = item; node->next = NULL; list->next = node; return list; > LinkedList* temp = list; while (temp->next->next) < temp = temp->next; > LinkedList* node = allocate_list(); node->item = item; node->next = NULL; temp->next = node; return list; Ht_item* linkedlist_remove(LinkedList* list) < // Removes the head from the linked list // and returns the item of the popped element if (!list) return NULL; if (!list->next) return NULL; LinkedList* node = list->next; LinkedList* temp = list; temp->next = NULL; list = node; Ht_item* it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; > void free_linkedlist(LinkedList* list) < LinkedList* temp = list; while (list) < temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); > >

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

typedef struct HashTable HashTable; // Define the Hash Table here struct HashTable < // Contains an array of pointers // to items Ht_item** items; LinkedList** overflow_buckets; int size; int count; >;

Теперь, когда мы определили overflow_buckets, давайте добавим функции для их создания и удаления. Их также необходимо учитывать в старых функциях create_table() и free_table().

LinkedList** create_overflow_buckets(HashTable* table) < // Create the overflow buckets; an array of linkedlists LinkedList** buckets = (LinkedList**) calloc (table->size, sizeof(LinkedList*)); for (int i=0; isize; i++) buckets[i] = NULL; return buckets; > void free_overflow_buckets(HashTable* table) < // Free all the overflow bucket lists LinkedList** buckets = table->overflow_buckets; for (int i=0; isize; i++) free_linkedlist(buckets[i]); free(buckets); > HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item != NULL) free_item(item); > // Free the overflow bucket linked linkedlist and it's items free_overflow_buckets(table); free(table->items); free(table); >

Теперь перейдем к функции handle_collision().

Здесь есть два сценария. Если список элемента не существует, нам нужно создать такой список и добавить в него элемент.

В противном случае мы можем просто вставить элемент в список.

void handle_collision(HashTable* table, unsigned long index, Ht_item* item) < LinkedList* head = table->overflow_buckets[index]; if (head == NULL) < // We need to create the list head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; > else < // Insert to the list table->overflow_buckets[index] = linkedlist_insert(head, item); return; > >

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

char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; // Ensure that we move to items which are not NULL while (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; if (head == NULL) return NULL; item = head->item; head = head->next; > return NULL;

Итак, мы учли коллизии в функциях insert() и search(). На данный момент наш код выглядит так:

#include #include #include #define CAPACITY 50000 // Size of the Hash Table unsigned long hash_function(char* str) < unsigned long i = 0; for (int j=0; str[j]; j++) i += str[j]; return i % CAPACITY; >typedef struct Ht_item Ht_item; // Define the Hash Table Item here struct Ht_item < char* key; char* value; >; typedef struct LinkedList LinkedList; // Define the Linkedlist here struct LinkedList < Ht_item* item; LinkedList* next; >; typedef struct HashTable HashTable; // Define the Hash Table here struct HashTable < // Contains an array of pointers // to items Ht_item** items; LinkedList** overflow_buckets; int size; int count; >; static LinkedList* allocate_list () < // Allocates memory for a Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; >static LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) < // Inserts the item onto the Linked List if (!list) < LinkedList* head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; > else if (list->next == NULL) < LinkedList* node = allocate_list(); node->item = item; node->next = NULL; list->next = node; return list; > LinkedList* temp = list; while (temp->next->next) < temp = temp->next; > LinkedList* node = allocate_list(); node->item = item; node->next = NULL; temp->next = node; return list; > static Ht_item* linkedlist_remove(LinkedList* list) < // Removes the head from the linked list // and returns the item of the popped element if (!list) return NULL; if (!list->next) return NULL; LinkedList* node = list->next; LinkedList* temp = list; temp->next = NULL; list = node; Ht_item* it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; > static void free_linkedlist(LinkedList* list) < LinkedList* temp = list; while (list) < temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); > > static LinkedList** create_overflow_buckets(HashTable* table) < // Create the overflow buckets; an array of linkedlists LinkedList** buckets = (LinkedList**) calloc (table->size, sizeof(LinkedList*)); for (int i=0; isize; i++) buckets[i] = NULL; return buckets; > static void free_overflow_buckets(HashTable* table) < // Free all the overflow bucket lists LinkedList** buckets = table->overflow_buckets; for (int i=0; isize; i++) free_linkedlist(buckets[i]); free(buckets); > Ht_item* create_item(char* key, char* value) < // Creates a pointer to a new hash table item Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; > HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; > void free_item(Ht_item* item) < // Frees an item free(item->key); free(item->value); free(item); > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item != NULL) free_item(item); > free_overflow_buckets(table); free(table->items); free(table); > void handle_collision(HashTable* table, unsigned long index, Ht_item* item) < LinkedList* head = table->overflow_buckets[index]; if (head == NULL) < // We need to create the list head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; > else < // Insert to the list table->overflow_buckets[index] = linkedlist_insert(head, item); return; > > void ht_insert(HashTable* table, char* key, char* value) < // Create the item Ht_item* item = create_item(key, value); // Compute the index unsigned long index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) < // Key does not exist. if (table->count == table->size) < // Hash Table Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; >// Insert directly table->items[index] = item; table->count++; > else < // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) < strcpy(table->items[index]->value, value); return; > else < // Scenario 2: Collision handle_collision(table, index, item); return; >> > char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; // Ensure that we move to items which are not NULL while (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; if (head == NULL) return NULL; item = head->item; head = head->next; > return NULL; > void print_search(HashTable* table, char* key) < char* val; if ((val = ht_search(table, key)) == NULL) < printf("%s does not exist\n", key); return; >else < printf("Key:%s, Value:%s\n", key, val); >> void print_table(HashTable* table) < printf("\n-------------------\n"); for (int i=0; isize; i++) < if (table->items[i]) < printf("Index:%d, Key:%s, Value:%s", i, table->items[i]->key, table->items[i]->value); if (table->overflow_buckets[i]) < printf(" =>Overflow Bucket => «); LinkedList* head = table->overflow_buckets[i]; while (head) < printf("Key:%s, Value:%s ", head->item->key, head->item->value); head = head->next; > > printf(«\n»); > > printf(«——————-\n»); > int main()

Удаление из хеш-таблицы
Давайте взглянем на функцию удаления данных из таблицы:

void ht_delete(HashTable* table, char* key);

Эта функция работает аналогично вставке. Нам нужно:

1. Вычислить хеш-индекс и получить элемент.
2. Если это NULL, нам ничего не нужно делать
3. В противном случае, если для этого индекса нет цепочки коллизий, после сравнения ключей нужно просто удалить элемент из таблицы.
4. Если цепочка коллизий существует, мы должны удалить этот элемент и соответствующим образом сдвинуть данные.

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

Предоставляем вам рабочую версию для сравнения.

void ht_delete(HashTable* table, char* key) < // Deletes an item from the table int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; if (item == NULL) < // Does not exist. Return return; >else < if (head == NULL && strcmp(item->key, key) == 0) < // No collision chain. Remove the item // and set table index to NULL table->items[index] = NULL; free_item(item); table->count--; return; > else if (head != NULL) < // Collision Chain exists if (strcmp(item->key, key) == 0) < // Remove this item and set the head of the list // as the new item free_item(item); LinkedList* node = head; head = head->next; node->next = NULL; table->items[index] = create_item(node->item->key, node->item->value); free_linkedlist(node); table->overflow_buckets[index] = head; return; > LinkedList* curr = head; LinkedList* prev = NULL; while (curr) < if (strcmp(curr->item->key, key) == 0) < if (prev == NULL) < // First element of the chain. Remove the chain free_linkedlist(head); table->overflow_buckets[index] = NULL; return; > else < // This is somewhere in the chain prev->next = curr->next; curr->next = NULL; free_linkedlist(curr); table->overflow_buckets[index] = head; return; > > curr = curr->next; prev = curr; > > > >

Полный код
Наконец, мы можем посмотреть на полный код программы хеш-таблицы.

#include #include #include #define CAPACITY 50000 // Size of the Hash Table unsigned long hash_function(char* str) < unsigned long i = 0; for (int j=0; str[j]; j++) i += str[j]; return i % CAPACITY; >typedef struct Ht_item Ht_item; // Define the Hash Table Item here struct Ht_item < char* key; char* value; >; typedef struct LinkedList LinkedList; // Define the Linkedlist here struct LinkedList < Ht_item* item; LinkedList* next; >; typedef struct HashTable HashTable; // Define the Hash Table here struct HashTable < // Contains an array of pointers // to items Ht_item** items; LinkedList** overflow_buckets; int size; int count; >; static LinkedList* allocate_list () < // Allocates memory for a Linkedlist pointer LinkedList* list = (LinkedList*) malloc (sizeof(LinkedList)); return list; >static LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) < // Inserts the item onto the Linked List if (!list) < LinkedList* head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; > else if (list->next == NULL) < LinkedList* node = allocate_list(); node->item = item; node->next = NULL; list->next = node; return list; > LinkedList* temp = list; while (temp->next->next) < temp = temp->next; > LinkedList* node = allocate_list(); node->item = item; node->next = NULL; temp->next = node; return list; > static Ht_item* linkedlist_remove(LinkedList* list) < // Removes the head from the linked list // and returns the item of the popped element if (!list) return NULL; if (!list->next) return NULL; LinkedList* node = list->next; LinkedList* temp = list; temp->next = NULL; list = node; Ht_item* it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; > static void free_linkedlist(LinkedList* list) < LinkedList* temp = list; while (list) < temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); > > static LinkedList** create_overflow_buckets(HashTable* table) < // Create the overflow buckets; an array of linkedlists LinkedList** buckets = (LinkedList**) calloc (table->size, sizeof(LinkedList*)); for (int i=0; isize; i++) buckets[i] = NULL; return buckets; > static void free_overflow_buckets(HashTable* table) < // Free all the overflow bucket lists LinkedList** buckets = table->overflow_buckets; for (int i=0; isize; i++) free_linkedlist(buckets[i]); free(buckets); > Ht_item* create_item(char* key, char* value) < // Creates a pointer to a new hash table item Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; > HashTable* create_table(int size) < // Creates a new HashTable HashTable* table = (HashTable*) malloc (sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*)); for (int i=0; isize; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; > void free_item(Ht_item* item) < // Frees an item free(item->key); free(item->value); free(item); > void free_table(HashTable* table) < // Frees the table for (int i=0; isize; i++) < Ht_item* item = table->items[i]; if (item != NULL) free_item(item); > free_overflow_buckets(table); free(table->items); free(table); > void handle_collision(HashTable* table, unsigned long index, Ht_item* item) < LinkedList* head = table->overflow_buckets[index]; if (head == NULL) < // We need to create the list head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; > else < // Insert to the list table->overflow_buckets[index] = linkedlist_insert(head, item); return; > > void ht_insert(HashTable* table, char* key, char* value) < // Create the item Ht_item* item = create_item(key, value); // Compute the index unsigned long index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) < // Key does not exist. if (table->count == table->size) < // Hash Table Full printf("Insert Error: Hash Table is full\n"); // Remove the create item free_item(item); return; >// Insert directly table->items[index] = item; table->count++; > else < // Scenario 1: We only need to update value if (strcmp(current_item->key, key) == 0) < strcpy(table->items[index]->value, value); return; > else < // Scenario 2: Collision handle_collision(table, index, item); return; >> > char* ht_search(HashTable* table, char* key) < // Searches the key in the hashtable // and returns NULL if it doesn't exist int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; // Ensure that we move to items which are not NULL while (item != NULL) < if (strcmp(item->key, key) == 0) return item->value; if (head == NULL) return NULL; item = head->item; head = head->next; > return NULL; > void ht_delete(HashTable* table, char* key) < // Deletes an item from the table int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; if (item == NULL) < // Does not exist. Return return; >else < if (head == NULL && strcmp(item->key, key) == 0) < // No collision chain. Remove the item // and set table index to NULL table->items[index] = NULL; free_item(item); table->count--; return; > else if (head != NULL) < // Collision Chain exists if (strcmp(item->key, key) == 0) < // Remove this item and set the head of the list // as the new item free_item(item); LinkedList* node = head; head = head->next; node->next = NULL; table->items[index] = create_item(node->item->key, node->item->value); free_linkedlist(node); table->overflow_buckets[index] = head; return; > LinkedList* curr = head; LinkedList* prev = NULL; while (curr) < if (strcmp(curr->item->key, key) == 0) < if (prev == NULL) < // First element of the chain. Remove the chain free_linkedlist(head); table->overflow_buckets[index] = NULL; return; > else < // This is somewhere in the chain prev->next = curr->next; curr->next = NULL; free_linkedlist(curr); table->overflow_buckets[index] = head; return; > > curr = curr->next; prev = curr; > > > > void print_search(HashTable* table, char* key) < char* val; if ((val = ht_search(table, key)) == NULL) < printf("%s does not exist\n", key); return; >else < printf("Key:%s, Value:%s\n", key, val); >> void print_table(HashTable* table) < printf("\n-------------------\n"); for (int i=0; isize; i++) < if (table->items[i]) < printf("Index:%d, Key:%s, Value:%s", i, table->items[i]->key, table->items[i]->value); if (table->overflow_buckets[i]) < printf(" =>Overflow Bucket => "); LinkedList* head = table->overflow_buckets[i]; while (head) < printf("Key:%s, Value:%s ", head->item->key, head->item->value); head = head->next; > > printf("\n"); > > printf("-------------------\n"); > int main() < HashTable* ht = create_table(CAPACITY); ht_insert(ht, "1", "First address"); ht_insert(ht, "2", "Second address"); ht_insert(ht, "Hel", "Third address"); ht_insert(ht, "Cau", "Fourth address"); print_search(ht, "1"); print_search(ht, "2"); print_search(ht, "3"); print_search(ht, "Hel"); print_search(ht, "Cau"); // Collision! print_table(ht); ht_delete(ht, "1"); ht_delete(ht, "Cau"); print_table(ht); free_table(ht); return 0; >Результат выглядит так: Key:1, Value:First address Key:2, Value:Second address 3 does not exist Key:Hel, Value:Third address Key:Cau, Value:Fourth address ------------------- Index:49, Key:1, Value:First address Index:50, Key:2, Value:Second address Index:281, Key:Hel, Value:Third address => Overflow Bucket => Key:Cau, Value:Fourth address ------------------- ------------------- Index:50, Key:2, Value:Second address Index:281, Key:Hel, Value:Third address -------------------

Заключение

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

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

Скачать код, который мы рассмотрели в этом руководстве, можно на Github Gist.