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

Фон

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

Долгое время я задавался вопросом, как создаются хеш-таблицы. Я хотел сделать свои собственные, но понятия не имел, как они работают. К счастью, я нашел Замечательный пост Джеймса Рутли, в котором подробно описано, как реализовать его на 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

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

Вставлять

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

  1. Увеличить размер хеш-таблицы.
  2. Вычислить index ключа с помощью хеш-функции.
  3. Если сегмент index пуст, создайте новый узел и добавьте его туда.
  4. В противном случае произошла коллизия: уже существует связанный список хотя бы из одного узла по этому индексу. Перейдите в конец списка и добавьте туда новый узел.

Это отражено в следующем коде:

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)

Находить

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

  1. Вычислите index для предоставленного ключа с помощью хеш-функции.
  2. Иди к ведру за этим index.
  3. Перебирайте узлы в этом связанном списке, пока не будет найден ключ или не будет достигнут конец списка.
  4. Вернуть значение найденного узла или 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, если запрошенный узел не был найден.

  1. Вычислить хэш ключа, чтобы определить index.
  2. Итерировать связанный список узлов. Продолжайте до конца списка или до тех пор, пока не будет найден ключ.
  3. Если ключ не найден, верните None.
  4. В противном случае удалите узел из связанного списка и верните значение узла.

Это будет отражено в коде как таковом:

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.

Приложения

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

Ниже приведены несколько проблем, которые вы можете попытаться решить с помощью новой хеш-таблицы:

  1. Напишите функцию, чтобы определить, содержит ли строка повторяющиеся символы.
  2. Для строки любой длины найдите наиболее часто используемый символ в строке.
  3. Напишите функцию, чтобы определить, являются ли две строки анаграммами.

Источник

Спасибо за чтение. Ознакомьтесь с полным исходным кодом того, что мы сделали сегодня, ниже!

Полный исходный код HashTable

Тестовый код HashTable

Вам нравится изучать программирование и компьютерную инженерию? Если да, то блог о решениях PageKey - это то, что вам нужно! Щелкните здесь, чтобы посетить.

Первоначально опубликовано на сайте linebylinecode.com 24 ноября 2017 г.