Как сделать хеш таблицу c

Добавил пользователь Morpheus
Обновлено: 18.09.2024

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

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

Простое представление хеш-таблиц

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

Первое, что приходит в голову — разместить все книги в алфавитном порядке и записать все в некий справочник. В этом случае не придется искать нужную книгу по всей библиотеке, а только по справочнику.

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

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

Учтите, что хеш-функция должна иметь следующие свойства:

Всегда возвращать один и тот же адрес для одного и того же ключа;
Не обязательно возвращает разные адреса для разных ключей;
Использует все адресное пространство с одинаковой вероятностью;
Быстро вычислять адрес.

Борьба с коллизиями (они же столкновения)

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

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

Метод цепочек

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

Если выбран метод цепочек, то вставка нового элемента происходит за O(1), а время поиска зависит от длины списка и в худшем случае равно O(n). Если количество ключей n , а распределяем по m -ячейкам, то соотношение n/m будет коэффициентом заполнения.

В C++ метод цепочек реализуется так:

Проверка ячейки и создание списка

Открытая индексация (или закрытое хеширование)

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

Самая простая в реализации последовательность проб — линейное пробирование (или линейное исследование). Здесь все просто — в случае коллизии, следующие ячейки проверяются линейно, пока не будет найдена пустая ячейка.

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

Метод линейного пробирования для открытой индексации на C++:

Проверка ячеек и вставка значения

Самое главное

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

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

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

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

Условие задачи

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

Решение

Предположим, вы реализуете хэш-таблицу Hash , которая связывает объекты типа К (ключи) с объектами типа V (значениями). На первый взгляд структура данных могла бы выглядеть примерно так:

items — массив связных списков, а items[i] — связный список всех объектов с ключами, которым сопоставляется индекс i (все коллизии для индекса i ). Вроде бы все работает… пока мы не задумаемся о коллизиях. Допустим, у нас очень простая хэш-функция, которая использует длину строки:

Ключи jim и bob будут соответствовать одному индексу массива, хотя это разные ключи (с одинаковой длиной строки). Нам нужно произвести поиск по связному списку, чтобы найти правильные объекты, соответствующие ключам. Но как это сделать? Ведь в связном списке хранится значение, а не исходный ключ. Одно из возможных решений — создание другого объекта (Cell), связывающего ключи со значениями. В этой реализации наш связный список будет иметь тип Cell. Следующий код использует эту реализацию:

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

Если вас заинтересовала данная тема, то вы можете прочитать интересный материал о сопоставлении хэш-таблиц и map в С++.

Изучаю теорию, подскажите, какое практическое применение Hashtable.

2 ответа 2

По сути Hashtable — это нетипизированная версия словаря ( Dictionary ) и ее можно использовать в тех же ситуациях, когда вы использовали бы словарь.

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

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

Тут, в первую очередь, надо понимать, что при использовании нетипизированной коллекции все ValueType будут подвергаться упаковке (boxing), поэтому Hashtable с их использованием будет отставать в производительности. Но сами алгоритмы и способы хранения внутри Dictionary и Hashtable должны быть аналогичными (в исходники не ходил — можете сделать это сами, если интересно), поэтому, с точки зрения асимптотики операций на них, они одинаковы.

А. Хэш. Структуры данных хэш-таблицы построены вокруг массивов. Хотя размер массива может быть увеличен позже при необходимости, массив состоит из элемента с номером 0 до некоторых элементов предварительно определенного размера. Каждый элемент данных, хранящийся в массиве, основан на некоторых блоках данных, которые называются ключевыми словами. Чтобы сохранить элемент в хеш-таблице, используется так называемая хеш-функция для сопоставления ключа с числом в диапазоне от 0 до размера хеш-таблицы. Идеальная цель хеш-функции - хранить каждый ключ в отдельном модуле в массиве. Однако, поскольку количество возможных ключевых слов не ограничено, а размер массива ограничен, более реалистичная цель хэш-функции состоит в том, чтобы как можно более равномерно распределить ключевые слова по ячейкам массива.

1. Выберите хеш-функцию. Выбор хеш-функции зависит от типа данных используемых ключевых слов. Если используемый ключ является целым числом, то самая простая функция - вернуть результат ключа по модулю размера массива. Однако не рекомендуется использовать этот метод в некоторых случаях, например, ключевое слово заканчивается на 0, а размер массива равен 10. Это одна из причин, по которой размер массива всегда должен быть простым. Кроме того, если ключевые слова являются случайными целыми числами, хеш-функция должна распределять ключевые слова более равномерно. Следующая программа иллюстрирует принцип работы этой хеш-функции:

2. Найдите данные в хеш-таблице. Чтобы найти данные в хеш-таблице, вам нужно вычислить хеш-значение ключа, а затем получить доступ к соответствующему элементу в массиве. Это так просто. Вот функция:

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

(1). Метод хеширования ведра. Bucket - это простая структура данных, которая хранится в элементе хэш-таблицы и может хранить несколько элементов данных. В большинстве реализаций эта структура данных является массивом, но в этой реализации будет использоваться массив списков, который позволит вам выделять больше места без учета выхода за пределы диапазона. Наконец, эта квадратная структура данных сделает реализацию более эффективной. Чтобы вставить элемент данных, сначала используйте хеш-функцию, чтобы определить, какой массив данных используется для хранения элемента данных. Затем проверьте, есть ли этот элемент данных уже в массиве. Если он существует, ничего не делать. Если он не существует, вызовите метод Add, чтобы добавить этот элемент данных в массив. Чтобы удалить элемент данных из хеш-таблицы, сначала определите значение хеш-функции удаляемого элемента данных и перейдите к соответствующему массиву списков. Затем убедитесь, что элемент данных находится в массиве . Если он существует, удалите его. следующее:

При использовании хэширования блоков самое важное, что вы можете сделать, - это сохранить как можно меньше используемых элементов массива. При добавлении или удалении элементов данных из хеш-таблицы это сводит к минимуму требуемую дополнительную работу. В предыдущем коде размер массива можно минимизировать, установив начальную емкость каждого массива в вызове конструктора. Как только возникает конфликт, емкость массива становится равной 2, а затем емкость будет удваиваться при каждом заполнении массива. Хотя используется хорошая хеш-функция, массив не должен быть слишком большим. Отношение количества элементов в хеш-таблице к размеру таблицы называется коэффициентом загрузки. Исследования показали, что, когда коэффициент загрузки равен 1,0 или когда размер таблицы точно равен количеству элементов, хеш-таблица работает лучше всего.
(2). Открыть метод адресации. Функция открытой адресации находит пустые ячейки в массиве хеш-таблиц для размещения элементов данных. Если первая пробная ячейка заполнена, попробуйте следующую пустую ячейку и так далее, пока, наконец, не найдете пустую ячейку. В этом разделе вы увидите две разные стратегии открытой адресации: линейное зондирование и квадратное зондирование. Метод линейного зондирования использует линейную функцию для определения элемента массива, который вы пытаетесь вставить. Это означает, что юниты будут проверяться в последовательности, пока они не будут найдены
до пустой единицы. Проблема с линейным зондированием состоит в том, что элементы данных в соседних ячейках в массиве будут стремиться к кластеризации, что делает последующее исследование пустых ячеек более продолжительным и менее эффективным. Метод квадратного зондирования решает проблему кластеризации. Функция квадрата используется, чтобы определить, какую единицу попробовать.
(3). Метод двойного хеширования. Двойное хеширование является интересной стратегией разрешения конфликтов, но на самом деле было показано, что метод квадратного зондирования обычно обеспечивает лучшую производительность.

Б. Класс HashTable. Класс Hashtable - это особый тип объекта Dictionary, который хранит пары ключ-значение, где значения хранятся на основе хеш-кода, полученного из ключевого слова. Здесь вы можете указать хеш-функцию для типа данных ключевого слова или использовать встроенную функцию (это будет обсуждаться позже). Класс Hashtable очень эффективен, и его следует использовать, где это возможно, для пользовательской реализации.

1. Использование Hashtable. Класс Hashtable является частью пространства имен System.Collections, поэтому System.Collections необходимо импортировать в начале программы. Объекты Hashtable могут быть созданы следующим образом:

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

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

Класс Hashtable имеет два очень полезных метода для извлечения ключевых слов и значений из хеш-таблицы: ключи и значения. Эти методы создают объект Enumerator, который позволяет использовать циклы For Each или другие методы для проверки ключевых слов и числовых значений.

2. Практические методы класса Hashtable.
(1). Свойство Count хранит количество элементов в хеш-таблице и возвращает целое число.

(2). Метод Clear может немедленно удалить все элементы из хеш-таблицы.

(3). Метод Remove удалит ключевое слово, а метод удалит указанное ключевое слово и соответствующее значение.

(4) .ContainsKey метод для проверки наличия элемента или значения в хеш-таблице.

3. Hashtable приложение. Программа сначала читает серию терминов и определений из текстового файла. Этот процесс закодирован в подпрограмме BuildGlossary. Структура текстового файла: слова, определения, разделенные запятыми между словами и их определениями. Каждое слово в этом глоссарии является отдельным словом, но глоссарий также может легко заменить фразу обработки. Вот почему запятые используются в качестве разделителей вместо пробелов. Кроме того, эта структура позволяет использовать слова в качестве ключевых слов, что является правильным способом построения этой хэш-таблицы. Другая подпрограмма, DisplayWords, отображает слова в списке, поэтому пользователи могут выбрать слово, чтобы получить его определение. Поскольку слово является ключевым словом, вы можете использовать метод Keys для точного возврата слова из хеш-таблицы. Затем пользователь может увидеть определенные слова. Пользователь может просто нажать на слово в списке, чтобы получить его определение. Используйте метод Item, чтобы получить определение и отобразить его в текстовом поле.

Один из наиболее эффективных способов реализации словаря - хеш-таблица. Среднее время поиска элемента в ней есть O(1), время для наихудшего случая - O(n). Прекрасное изложение хеширования можно найти в работах Кормена[1990] и Кнута[1998]. Чтобы читать статьи на эту тему, вам понадобится владеть соответствующей терминологией. Здесь описан метод, известный как связывание или открытое хеширование[3]. Другой метод, известный как замкнутое хеширование[3] или закрытая адресация[1], здесь не обсуждаются. Ну, как?

Теория

Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией. Например, на hashTable рис. 3.1 - это массив из 8 элементов. Каждый элемент представляет собой указатель на линейный список, хранящий числа. Хеш-функция в этом примере просто делит ключ на 8 и использует остаток как индекс в таблице. Это дает нам числа от 0 до 7 Поскольку для адресации в hashTable нам и нужны числа от 0 до 7, алгоритм гарантирует допустимые значения индексов.

Рис. 3.1: Хеш-таблица

Чтобы вставить в таблицу новый элемент, мы хешируем ключ, чтобы определить список, в который его нужно добавить, затем вставляем элемент в начало этого списка. Например, чтобы добавить 11, мы делим 11 на 8 и получаем остаток 3. Таким образом, 11 следует разместить в списке, на начало которого указывает hashTable[3]. Чтобы найти число, мы его хешируем и проходим по соответствующему списку. Чтобы удалить число, мы находим его и удаляем элемент списка, его содержащий.

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

Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай - когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция. Здесь мы рассмотрим лишь несколько из возможных подходов. При иллюстрации методов предполагается, что unsigned char располагается в 8 битах, unsigned short int - в 16, unsigned long int - в 32.

Деление

размер таблицы

простое число

Пусть, например, размер таблицы hashTableSize равен 1024 (2 10 ). Тогда нам достаточен 16-битный индекс и S будет присвоено значение 16 - 10 = 6. В итоге получаем:

Реализация

В реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. Для работы программы следует также определить hashTableSize и отвести место под hashTable. В хеш-функции hash использован метод деления. Функция insertNode отводит память под новый узел и вставляет его в таблицу. Функция deleteNode удаляет узел и освобождает память, где он располагался. Функция findNode ищет в таблице заданный ключ.

Читайте также: