Хеш-таблица в структуре данных: пример Python

Содержание:

Anonim

Что такое хеширование?

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

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

В этом руководстве по алгоритму вы узнаете:

  • Что такое хеширование?
  • Что такое хеш-таблица?
  • Хеш-функции
  • Качества хорошей хеш-функции
  • Столкновение
  • Операции с хеш-таблицей
  • Пример хеш-таблицы Python
  • Пояснение кода хеш-таблицы
  • Пример словаря Python
  • Анализ сложности
  • Реальные приложения
  • Преимущества хеш-таблиц
  • Недостатки хеш-таблиц

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

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

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

Хеш-функции

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

Мы можем использовать номер сотрудника в качестве ключа и назначить данные сотрудника в качестве значения.

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

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

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

h(k) = k1 % m

ЗДЕСЬ,

  • h (k) - хэш-функция, которая принимает параметр k. Параметр k - это значение, для которого мы хотим вычислить ключ.
  • k 1 % m - это алгоритм для нашей хэш-функции, где k1 - значение, которое мы хотим сохранить, а m - размер списка. Мы используем оператор модуля для вычисления ключа.

Пример

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

[1,2,3]

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

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

Шаг 1)

Рассчитайте позицию, которую будет занимать первое значение, вот так

ч (1) = 1% 3

= 1

Значение 1 будет занимать место в индексе 1.

Шаг 2)

Вычислить позицию, которую будет занимать второе значение

ч (2) = 2% 3

= 2

Значение 2 будет занимать место в индексе 2.

Шаг 3)

Вычислите позицию, которую займет третье значение.

ч (3) = 3% 3

= 0

Значение 3 будет занимать место в индексе 0.

Конечный результат

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

Качества хорошей хеш-функции

Хорошая хеш-функция должна обладать следующими качествами.

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

Столкновение

Конфликт возникает, когда алгоритм генерирует один и тот же хеш для более чем одного значения.

Давайте посмотрим на пример.

Предположим, у нас есть следующий список значений

[3,2,9,11,7]

Предположим, что размер хеш-таблицы равен 7, и мы будем использовать формулу (k 1 % m), где m - размер хеш-таблицы.

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

Ключ Алгоритм хеширования (k 1 % m) Хеш-значение
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

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

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

Цепочка

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

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

И 2, и 9 занимают один и тот же индекс, но хранятся в виде связанных списков. Каждый список имеет уникальный идентификатор.

Преимущества связанных списков

Ниже перечислены преимущества связанных списков:

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

Зондирование

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

Ниже приведены методы зондирования:

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

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

Операции с хеш-таблицей

Вот операции, поддерживаемые хеш-таблицами:

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

Операция вставки данных

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

Поиск операции с данными

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

Операция удаления данных

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

Реализация хеш-таблицы на примере Python

Давайте посмотрим на простой пример, который вычисляет хеш-значение ключа

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Пояснение кода хеш-таблицы

ЗДЕСЬ,

  1. Определяет функцию hash_key, которая принимает параметры key и m.
  2. Использует простую операцию модуля для определения хеш-значения
  3. Определяет переменную m, которая инициализируется значением 7. Это размер нашей хеш-таблицы.
  4. Вычисляет и печатает хеш-значение 3
  5. Вычисляет и печатает хеш-значение 2
  6. Вычисляет и печатает хеш-значение 9
  7. Вычисляет и печатает хеш-значение 11
  8. Вычисляет и печатает хеш-значение 7

Выполнение приведенного выше кода дает следующие результаты.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Пример словаря Python

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

В следующем примере показано, как можно использовать тип данных словаря в Python 3.

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

ЗДЕСЬ,

  1. Определяет словарную переменную employee. Имя ключа используется для хранения значения John Doe, age хранит 36, а position хранит значение Business Manager.
  2. Получает значение имени ключа и печатает его в терминале
  3. Обновляет значение ключевой позиции до значения Software Engineer
  4. Печатает значения имени и позиции ключей
  5. Удаляет все значения, которые хранятся в нашей словарной переменной employee
  6. Печатает стоимость сотрудника

Выполнение приведенного выше кода дает следующие результаты.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Анализ сложности

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

Реальные приложения

В реальном мире хеш-таблицы используются для хранения данных для

  • Базы данных
  • Ассоциативные массивы
  • Наборы
  • Кэш памяти

Преимущества хеш-таблиц

Вот плюсы / преимущества использования хеш-таблиц:

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

Недостатки хеш-таблиц

Вот минусы использования хеш-таблиц:

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

Резюме:

  • Хеш-таблицы используются для хранения данных с использованием пары ключей и значений.
  • Хеш-функция использует математический алгоритм для вычисления хеш-значения.
  • Конфликт возникает, когда одно и то же значение хеш-функции создается для нескольких значений.
  • Цепочка решает конфликт путем создания связанных списков.
  • Зондирование решает конфликт, находя пустые слоты в хеш-таблице.
  • Линейное зондирование ищет следующий свободный слот, чтобы сохранить значение, начиная со слота, в котором произошла коллизия.
  • Квадратичное зондирование использует полиномиальные выражения для поиска следующего свободного слота при возникновении коллизии.
  • Двойное хеширование использует алгоритм вторичной хеш-функции для поиска следующего свободного слота при возникновении коллизии.
  • Хеш-таблицы имеют лучшую производительность по сравнению с другими структурами данных.
  • Средняя временная сложность хеш-таблиц - O (1).
  • Тип данных словаря в Python является примером хеш-таблицы.
  • Хеш-таблицы поддерживают операции вставки, поиска и удаления.
  • Нулевое значение нельзя использовать в качестве значения индекса.
  • В хэш-функциях нельзя избежать конфликтов. Хорошая хеш-функция сводит к минимуму количество возникающих коллизий для повышения производительности.