Из этого туториала Вы узнаете, как реализовать хеш-таблицу с отдельной цепочкой. Это не самый эффективный метод, но это самый простой способ начать работу и создать полнофункциональную хеш-таблицу.
Фон
Хеш-таблицы - незаменимый инструмент для решения широкого спектра интересных программных задач. Я всегда люблю включать в задачу хеш-таблицу; они могут предоставить чистое решение проблемы, которая в противном случае превратилась бы в беспорядок.
Долгое время я задавался вопросом, как создаются хеш-таблицы. Я хотел сделать свои собственные, но понятия не имел, как они работают. К счастью, я нашел Замечательный пост Джеймса Рутли, в котором подробно описано, как реализовать его на C. Всем, кому интересно, я настоятельно рекомендую его.
Используя эти знания, я перенес хеш-таблицу на Python. К концу этого урока вы поймете основные идеи, лежащие в основе хеш-таблицы. Возможно, что еще более важно, вы реализовали свое собственное!
Основы
Если вы когда-либо использовали словарь в Python или ассоциативный массив на таком языке, как PHP, вы, вероятно, раньше использовали хеш-таблицу. Такие функции, как словарь в Python или ассоциативный массив в PHP, часто реализуются с использованием хеш-таблицы. Еще более простым является класс HashTable, доступный в Java.
Зачем нам нужна такая структура? Что ж, иногда ровной площади просто недостаточно. Чтобы понять суть проблемы, вам может потребоваться хранить данные и получать к ним доступ с помощью ключа, что является определенным шагом вперед по сравнению с элементарным целочисленным индексом, предоставляемым плоскими массивами.
Созданная нами хеш-таблица будет использоваться следующим образом:
# Create a new HashTable
ht = HashTable()
# Create some data to be stored
phone_numbers = ["555-555-5555", "444-444-4444"]
# Insert our data under the key "phoneDirectory"
ht.insert("phoneDirectory", phone_numbers)
# Do whatever we need with the phone_numbers variable
phone_numbers = None
... # Later on...
# Retrieve the data we stored in the HashTable
phone_numbers = ht.find("phoneDirectory")
# find() retrieved our list object
# phone_numbers is now equal to ["555-555-5555", "444-444-4444"]
Как это действительно работает под капотом? Как оказалось, ваш ключ (phoneDirectory
в этом примере) преобразован в индекс. Этот индекс используется для хранения и извлечения значения данных из внутреннего массива хеш-таблицы. Все эти беспорядочные детали скрыты от пользователя - им просто нужно беспокоиться о insert()
, find()
и remove()
.
Поля
Для нашей хэш-таблицы потребуется несколько полей. Ему нужен size
, который будет количеством вставленных элементов. Ему нужен capacity
, который определит размер нашего внутреннего массива. Наконец, ему требуется buckets
- это внутренний массив, хранящий каждое вставленное значение в «корзине» на основе предоставленного ключа.
class HashTable:
def __init__(self):
self.capacity = INITIAL_CAPACITY
self.size = 0
self.buckets = [None] * self.capacity
Обратите внимание на переменную INITIAL_CAPACITY
, произвольно установленную на 50 в моем примере класса. Это определяет размер нашего внутреннего массива. В более сложной реализации хеш-таблицы (т. Е. Хеш-таблицы с открытым адресом и двойным хешированием) важно, чтобы емкость была простой и чтобы ее можно было изменить. С другой стороны, наша отдельная хеш-таблица с цепочкой устанавливает емкость один раз и никогда не меняет ее, независимо от того, сколько элементов хранится. Это хорошо для простоты, но плохо для масштабируемости.
Узел HashTable
Если вы думали, что у вас есть перерыв во внутренней структуре узла, вы ошибались! Для нашей хэш-таблицы потребуется собственная версия узла:
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
Выглядит знакомо? Узел имеет поле next
, потому что на самом деле это часть LinkedList. Поскольку в хэш-таблице используется отдельная цепочка, каждая корзина фактически будет содержать LinkedList узлов, содержащих объекты, хранящиеся в этом индексе. Это один из методов разрешения коллизий.
Столкновения
Когда два ключа имеют одинаковое хеш-значение, это считается конфликтом. Что должна делать наша хеш-таблица? Если бы он все равно просто записал данные в местоположение, мы бы потеряли объект, который уже хранится под другим ключом.
С помощью отдельной цепочки мы создаем связанный список по каждому индексу нашего массива buckets
, содержащий все ключи для данного индекса. Когда нам нужно найти один из этих элементов, мы перебираем список, пока не найдем узел, соответствующий запрошенному ключу.
Существуют и другие, гораздо более эффективные способы обработки коллизий, но разделение цепочек, вероятно, является самым простым методом.
Методы
Теперь мы действительно можем приступить к работе. Давайте перейдем к методам нашей хеш-таблицы.
Хеш
Нашему хэш-методу необходимо взять наш ключ, который будет строкой любой длины, и создать индекс для нашего внутреннего массива buckets
.
Мы будем создавать хэш-функцию для преобразования строки в индекс. У хорошей хеш-функции много свойств, но для наших целей наиболее важной характеристикой, которую должна иметь наша функция, является единообразие. Мы хотим, чтобы наши хеш-значения были как можно более равномерно распределены между нашими корзинами, чтобы в полной мере использовать каждую корзину и избегать коллизий. Идеальный случай изображен ниже:
С другой стороны, неравномерное распределение полностью лишит хеш-таблицы цели, в результате чего получится не что иное, как раздутый LinkedList.
Рассмотрим крайний случай: наша хеш-функция будет h(x) = 1
. Правильно, каждый вход дает одно и то же постоянное значение. Итак, что происходит? Каждый раз, когда мы хэшируем ключ, на выходе получается 1, что означает, что мы назначаем этот узел сегменту 1. Результат будет выглядеть примерно так:
Не очень! Нам просто нужно убедиться, что мы любой ценой избегаем этого узкого места.
Вот код нашей хеш-функции:
def hash(self, key):
hashsum = 0
# For each character in the key
for idx, c in enumerate(key):
# Add (index + length of key) ^ (current char code)
hashsum += (idx + len(key)) ** ord(c)
# Perform modulus to keep hashsum in range [0, self.capacity - 1]
hashsum = hashsum % self.capacity
return hashsum
Хотя эта функция довольно произвольна, она обеспечит приемлемую степень единообразия для наших целей.
Вставлять
Чтобы вставить пару ключ / значение в нашу хеш-таблицу, мы выполним следующие шаги:
- Увеличить размер хеш-таблицы.
- Вычислить
index
ключа с помощью хеш-функции. - Если сегмент
index
пуст, создайте новый узел и добавьте его туда. - В противном случае произошла коллизия: уже существует связанный список хотя бы из одного узла по этому индексу. Перейдите в конец списка и добавьте туда новый узел.
Это отражено в следующем коде:
def insert(self, key, value):
# 1. Increment size
self.size += 1
# 2. Compute index of key
index = self.hash(key)
# Go to the node corresponding to the hash
node = self.buckets[index]
# 3. If bucket is empty:
if node is None:
# Create node, add it, return
self.buckets[index] = Node(key, value)
return
# 4. Collision! Iterate to the end of the linked list at provided index
prev = node
while node is not None:
prev = node
node = node.next
# Add a new node at the end of the list with provided key/value
prev.next = Node(key, value)
Находить
После сохранения данных в нашей хэш-таблице нам обязательно понадобится их получить в какой-то момент. Для этого мы выполним следующие шаги:
- Вычислите
index
для предоставленного ключа с помощью хеш-функции. - Иди к ведру за этим
index
. - Перебирайте узлы в этом связанном списке, пока не будет найден ключ или не будет достигнут конец списка.
- Вернуть значение найденного узла или None, если не найден.
Эта идея может быть выражена в таком коде:
def find(self, key):
# 1. Compute hash
index = self.hash(key)
# 2. Go to first node in list at bucket
node = self.buckets[index]
# 3. Traverse the linked list at this node
while node is not None and node.key != key:
node = node.next
# 4. Now, node is the requested key/value pair or None
if node is None:
# Not found
return None
else:
# Found - return the data value
return node.value
Удаление элемента из хеш-таблицы аналогично удалению элемента из связанного списка. Этот метод вернет удаленное значение данных или None, если запрошенный узел не был найден.
- Вычислить хэш ключа, чтобы определить
index
. - Итерировать связанный список узлов. Продолжайте до конца списка или до тех пор, пока не будет найден ключ.
- Если ключ не найден, верните None.
- В противном случае удалите узел из связанного списка и верните значение узла.
Это будет отражено в коде как таковом:
def remove(self, key):
# 1. Compute hash
index = self.hash(key)
node = self.buckets[index]
prev = None
# 2. Iterate to the requested node
while node is not None and node.key != key:
prev = node
node = node.next
# Now, node is either the requested node or none
if node is None:
# 3. Key not found
return None
else:
# 4. The key was found.
self.size -= 1
result = node.value
# Delete this element in linked list
if prev is None:
node = None
else:
prev.next = prev.next.next
# Return the deleted language
return result
Дополнительную информацию об удалении узла из связанного списка см. В моей статье LinkedList.
Приложения
Хеш-таблицы могут быть полезны в самых разных приложениях информатики. Как только вы научитесь их использовать, вы не сможете остановиться! Кажется, на каждом шагу появляется новое приложение для хеш-таблицы.
Ниже приведены несколько проблем, которые вы можете попытаться решить с помощью новой хеш-таблицы:
- Напишите функцию, чтобы определить, содержит ли строка повторяющиеся символы.
- Для строки любой длины найдите наиболее часто используемый символ в строке.
- Напишите функцию, чтобы определить, являются ли две строки анаграммами.
Источник
Спасибо за чтение. Ознакомьтесь с полным исходным кодом того, что мы сделали сегодня, ниже!
Вам нравится изучать программирование и компьютерную инженерию? Если да, то блог о решениях PageKey - это то, что вам нужно! Щелкните здесь, чтобы посетить.
Первоначально опубликовано на сайте linebylinecode.com 24 ноября 2017 г.