🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
🤔 Как избегают коллизии в хеш мапе ?
Это ситуации, когда два ключа имеют один и тот же хеш-код и, следовательно, претендуют на одно и то же место в структуре данных. Управление коллизиями — важная часть дизайна хеш-таблиц, поскольку эффективность хеш-таблицы сильно зависит от того, насколько эффективно решается проблема коллизий.
🚩Открытая адресация (Open Addressing)
Открытая адресация решает проблемы коллизий путем поиска другого места в хеш-таблице для элемента, вызвавшего коллизию. Существуют различные методы открытой адресации:
🟠Линейное пробирование
При коллизии проверяется следующая ячейка таблицы. Если она занята, проверяется следующая и т.д., пока не будет найдена свободная ячейка.
🟠Квадратичное пробирование
Используется квадратичная функция для вычисления смещения от исходной позиции при каждом шаге пробирования (например, 1, 4, 9, 16 и т.д.).
🟠Двойное хеширование
Используются две хеш-функции для вычисления начального индекса и шага пробирования, чтобы найти свободную ячейку.
🚩Сцепление (Chaining)
Это метод, при котором каждая ячейка хеш-таблицы содержит указатель на связный список (или другую структуру данных, такую как дерево), содержащий все элементы, которые были отображены в эту ячейку. При коллизии новый элемент просто добавляется в конец списка. Сцепление может обрабатывать неограниченное количество коллизий, хотя производительность может снизиться, если списки становятся слишком длинными.
🚩Рехеширование (Rehashing)
Рехеширование предполагает использование дополнительных хеш-функций при коллизиях. Если первичная хеш-функция приводит к коллизии, применяется вторая хеш-функция, и так далее, пока не будет найдена свободная ячейка или не будут использованы все доступные хеш-функции.
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
item[1] = value
return
self.table[index].append([key, value])
def get(self, key):
index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
return item[1]
raise KeyError('Key not found')
def remove(self, key):
index = self.hash_function(key)
for i, item in enumerate(self.table[index]):
if item[0] == key:
del self.table[index][i]
return
raise KeyError('Key not found')
# Пример использования
ht = HashTable()
ht.insert("key1", "value1")
ht.insert("key2", "value2")
print(ht.get("key1")) #
выводит "value1"
ht.remove("key1")
Ставь 👍 и забирай 📚 Базу знаний