Коллизии в хеш-таблицах 🤩
Коллизия возникает, когда два разных ключа попадают в один и тот же индекс массива. Например, при размере таблицы 10: 5 % 10 = 5 и 15 % 10 = 5 → оба ключа попадают в одну ячейку.
Чтобы это решать, используют два подхода: цепочки и открытую адресацию.
1️⃣В методе цепочек каждая ячейка хранит список элементов. Если по индексу уже есть данные — новый ключ добавляется в связанный список. Это просто в реализации и не сильно зависит от заполненности таблицы, но требует дополнительной памяти и при большом числе коллизий списки могут становиться длинными.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
print(hash_table.table)
2️⃣ В методе открытой адресации элементы хранятся прямо в массиве. Если ячейка занята — ищем следующую свободную. Самый простой вариант — линейное пробирование:
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
Есть и другие стратегии: квадратичное пробирование (index + i^2) и двойное хеширование (шаг вычисляется второй функцией).
⚡️ Почему это важно? Без коллизий доступ к данным в хеш-таблице занимает O(1), но при большом количестве коллизий время может увеличиться до O(n). В цепочках проблема — длинные списки, в открытой адресации — кластеризация (занятые подряд ячейки, из-за которых коллизии становятся ещё чаще).
Вывод: коллизии неизбежны, но при грамотной обработке хеш-таблицы остаются одним из самых быстрых и удобных способов хранения данных.
