12 подписчиков

Приближение реализации хэш-таблицы Python

19 октября 202319 окт 2023

3 мин

Материал взят с книги Брэда Миллер и Дэвид Рэнума "Аспекты связанные со структурами и алгоритмами".

Хэш-таблица - это коллекция элементов, которая сохраняется таким образом, чтобы позже их было легко найти. Каждая позиция в хэш-таблице (slot или bucket) может содержать элемент и целое число, начинающиеся с нуля. Связь между элементом и слотом, в который он кладётся, называется хэш-функцией. Она принимает любой элемент из коллекции и возвращает целое число из диапазона имён слотов. Для вычисления хэш значения и перехода по заданному индексу требуется константное время O(1). Но такое корректно, если каждый элемент сопоставлен уникальной позиции (идеальная хэш функция). Если же в одном слоте лежит несколько элементов, то возникают "коллизии", которые увеличивают временную сложность. Для борьбы с коллизиями применяют разные методы, среди них:

1) Метод остатков - берёт элемент и делим его на размер таблицы, возвращая остаток в качестве хэша.

2) Метод свёртки - разбиваем элемент на составляющие одинаковой длины, дальше разделённые элементы складываются, делятся на определенное число, и от этого значения берётся остаток.

3) Метод средних квадратов - значение возводится в квадрат, выделяется часть числа и от неё берётся остаток.

Чтобы захешировать символьный элемент - преобразуем его согласно таблице ASCII.

Разрешение коллизий имеют разные решения среди них: перемещение по слотам определённым образом до тех пор, пока не будет найден пустой слот. При необходимости возвращения обратно к первому слоту, для охвата всей таблице.

Реализация структуры типа хэш-таблицы на Python:

1) dict

2) выдумать свою(взять чужую) структуру

class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
"""
инициализируем класс: создаём массив данных и слотов произвольной величины
"""

def put(self,key,data):
hashvalue = self.hashfunction(key,len(self.slots))

if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data #replace
else:
nextslot = self.rehash(hashvalue,len(self.slots))
while self.slots[nextslot] != None and \
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))

if self.slots[nextslot] == None:
self.slots[nextslot]=key
self.data[nextslot]=data
else:
self.data[nextslot] = data #replace
"""
описываем вставку элемента в хэш-таблицу: если до этого данных с этим ключом не было, то ключ ставится в слот по модулю длины инициализированного массива,
если данные с этим ключом уже были, то заменяем их,
если же слот с модулем ключа уже занят, а сам ключ отличается от предыдущих, То используем функцию для устранения коллизии и поиска нового слота, для этого мы переходим в следующий слот, пока не найдем пустой.
"""

def hashfunction(self,key,size):
return key%size

def rehash(self,oldhash,size):
return (oldhash+1)%size

def get(self,key):
startslot = self.hashfunction(key,len(self.slots))
data = None
stop = False
found = False
position = startslot
print(found == True)
while self.slots[position] != None and \
not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data
"""
метод для получения значения по номеру слота: проходим по циклу пока не найдем слот равный нашему ключу или если была коллизия, пока не пройдет все ячейки для нахождения нашего ключа.
"""

def __getitem__(self,key):
return self.get(key)

def __setitem__(self,key,data):
self.put(key,data)
"""
два вспомогательных магических метода для удобного представления ключей и значений.
"""