Хэш-функция
В этом разделе мы обсудим хэш-функцию, которая помогает выполнить хэш-код соответствующего ключа элемента данных в структуре данных, как указано ниже:
Целочисленный хеш-элемент ( интервал ключ ){
возвращаться ключ % размер стола ;
}
Процесс выполнения индекса массива называется хешированием. Иногда один и тот же тип кода выполняется для создания одного и того же индекса с использованием одних и тех же ключей, называемых коллизиями, которые обрабатываются с помощью различных цепочек (создание связанного списка) и реализации стратегий открытой адресации.
Работа хеш-таблицы в C++
Указатели на реальные значения хранятся в хеш-таблице. Он использует ключ для поиска индекса массива, в котором значения ключей должны быть сохранены в нужном месте массива. Мы взяли хеш-таблицу размером 10, как указано ниже:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Давайте случайным образом возьмем любые данные по разным ключам и сохраним эти ключи в хеш-таблице, просто рассчитав индекс. Итак, данные хранятся по ключам в вычисляемом индексе с помощью хеш-функции. Предположим, мы берем данные = {14,25,42,55,63,84} и ключи =[ 15,9,5,25,66,75 ].
Рассчитайте индекс этих данных, используя хэш-функцию. Значение индекса упоминается в следующем:
| Ключ | пятнадцать | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Рассчитать индекс | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Данные | 14 | 25 | 42 | 55 | 63 | 84 |
После создания индекса массива поместите данные по ключу точного индекса данного массива, как описано ранее.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
После этого мы видим, что коллизия возникает, если два или более ключей имеют одинаковый хеш-код, что приводит к одинаковому индексу элементов массива. У нас есть одно решение, позволяющее избежать коллизий: выбор хорошего метода хеширования и реализация точных стратегий.
Теперь давайте обсудим различные методы реализации на соответствующих примерах.
Пример. Добавление данных в хеш-таблицу с использованием метода открытого хеширования
В этом примере мы используем такой метод реализации, как открытое хеширование, чтобы избежать коллизий в хеш-таблице. При открытом хешировании или цепочке мы создаем связанный список для связывания значений хеш-таблицы. Ниже прилагается фрагмент кода этого примера, описывающий метод открытого хеширования:
#include#include <список>
сорт Хеш-таблица {
частный :
статический константа интервал размер таблицы '=' 10 ;
стандартный :: список < интервал > таблицаИмеет [ размер таблицы ] ;
интервал hashFunc ( интервал ключ ) {
возвращаться ключ % размер таблицы ;
}
общественный :
пустота вставлять ( интервал ключ ) {
интервал индекс '=' hashFunc ( ключ ) ;
таблицаИмеет [ индекс ] . отталкивать ( ключ ) ;
}
пустота просмотртаблицы ( ) {
для ( интервал я '=' 0 ; я < размер таблицы ; ++ я ) {
стандартный :: расчет << '[' << я << ']' ;
для ( авто это '=' таблицаИмеет [ я ] . начинать ( ) ; это ! '=' таблицаИмеет [ я ] . конец ( ) ; ++ это ) {
стандартный :: расчет << ' -> ' << * это ;
}
стандартный :: расчет << стандартный :: конец ;
}
}
} ;
интервал основной ( ) {
Хэштаблица ;
имееттаблицу. вставлять ( пятнадцать ) ;
имееттаблицу. вставлять ( 33 ) ;
имееттаблицу. вставлять ( 23 ) ;
имееттаблицу. вставлять ( 65 ) ;
имееттаблицу. вставлять ( 3 ) ;
имееттаблицу. просмотртаблицы ( ) ;
возвращаться 0 ;
}
Это очень интересный пример: мы строим связанный список и вставляем данные в хеш-таблицу. Прежде всего, мы определяем библиотеки в начале программы. < список > библиотека используется для реализации связанного списка. После этого мы создаем класс с именем «HashTable» и создаем частные атрибуты класса, такие как размер таблицы и массив таблицы, используя ключевое слово «private:». Помните, что частные атрибуты нельзя использовать вне класса. Здесь мы принимаем размер таблицы равным «10». Используя это, мы инициализируем хеш-метод и вычисляем индекс хеш-таблицы. В хеш-функцию мы передаем ключ и размер хеш-таблицы.
Мы создаем несколько необходимых функций и делаем эти функции общедоступными в классе. Помните, что публичные функции можно использовать вне класса где угодно. Мы используем ключевое слово «public:», чтобы начать публичную часть класса. . Поскольку мы хотим добавить новые элементы в хеш-таблицу, мы создаем функцию с именем «InsertHash» с ключом в качестве аргумента функции. В функции «insert» мы инициализируем индексную переменную. Мы передаем хеш-функцию индексной переменной. После этого передайте индексную переменную в связанный список tableHas[], используя метод «push», чтобы вставить элемент в таблицу.
После этого мы создаем функцию viewHashTab для отображения хэш-таблицы и просмотра вновь вставленных данных. В этой функции мы используем цикл «for», который ищет значения до конца хеш-таблицы. Убедитесь, что значения хранятся по тому же индексу, который разработан с использованием хэш-функции. В цикле мы передаем значения по соответствующему индексу и завершаем здесь класс. В функции «main» мы берем объект класса с именем hasTable. С помощью этого объекта класса мы можем получить доступ к методу вставки, передав ключ в методе. Ключ, который мы передали в функцию «main», вычисляется в функции «insert», которая возвращает позицию индекса в хеш-таблице. Мы отобразили хеш-таблицу, вызвав функцию «представление» с помощью объекта «Класс».
Вывод этого кода прилагается следующим образом:
Как мы видим, хеш-таблица успешно создается с использованием связанного списка в C++. Открытая цепочка используется, чтобы избежать конфликта одного и того же индекса.
Заключение
В конечном итоге мы пришли к выводу, что хеш-таблица — это наиболее новый метод хранения и получения ключей с парами значений для эффективной обработки огромных объемов данных. Вероятность коллизий в хеш-таблице очень высока, что приводит к уничтожению данных и их хранилища. Мы можем преодолеть это столкновение, используя различные методы управления хеш-таблицей. Разработав хеш-таблицу на C++, разработчики могут повысить производительность, используя наиболее подходящий метод хранения данных в хеш-таблице. Мы надеемся, что эта статья поможет вам понять хеш-таблицу.