Хеш-таблица
Отображение ключ-значение с доступом в среднем за O(1).
Сигнатура
среднее O(1)Хеш-таблица хранит пары ключ-значение, вычисляя позицию ключа хеш-функцией. В Python это dict. Коллизии разрешаются цепочками или открытой адресацией.
Сложность: вставка, поиск, удаление — в среднем O(1), в худшем случае O(n) при множестве коллизий. Память: O(n). Ключи должны быть хешируемыми (неизменяемыми).
d = {}
d["apple"] = 3 # вставка O(1) в среднем
print(d["apple"]) # поиск O(1)
print("pear" in d) # проверка O(1)
del d["apple"] # удаление O(1)