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

Автор: Сара Чен Сара Чен
Hours обновлено

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

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

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

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

A ХЕШ-ТАБЛИЦА — это структура данных, которая хранит значения с использованием пары ключей и значений. Каждому значению присваивается уникальный ключ, который генерируется с помощью хэш-функции.

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

Хэш-функции

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

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

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

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

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

h(k) = k1 % m

ВОТ,

  • h(k) — хеш-функция, принимающая параметр k. Параметр k — это значение, для которого мы хотим вычислить ключ.
  • k1 % 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, и мы воспользуемся формулой (k1 % m), где m — размер хеш-таблицы.

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

Основные Алгоритм хеширования (k1% 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).
  • Нет необходимости изменять размер хеш-таблицы, в которой используется связанный список.
  • Он может легко вместить большое количество значений, если доступно свободное место.

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

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

Существуют следующие методы зондирования:

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

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

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

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

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

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

Вставка операции с данными

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

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

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

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

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

Реализация хэш-таблицы с помощью Python Пример

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

def hash_key( key, m):
    return key % m


m = 7

print(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 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The 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)

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

ВОТ,

  1. Определяет словарную переменную сотрудника. Имя ключа используется для хранения значения «Джон Доу», возраст — 36, а позиция — значение «Бизнес-менеджер».
  2. Получает значение имени ключа и печатает его в терминале.
  3. Обновляет значение ключевой позиции до значения «Инженер-программист».
  4. Печатает значения имени и положения клавиш.
  5. Удаляет все значения, хранящиеся в нашей словарной переменной сотрудника.
  6. Печатает стоимость сотрудника

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

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

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

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

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

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

  • Databases
  • Ассоциативные массивы
  • Наборы пигментов
  • Кеш памяти

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

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

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

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

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

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

Резюме

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