Почему словарь быстро ищет по ключам?

Быстрый поиск по ключам в словаре Python

Словари в Python ищут по ключам за O(1) в среднем времени благодаря хэш-таблицам. Это структура данных, которая преобразует ключ в индекс массива для прямого доступа.

Как это работает

Принцип хэш-таблицы:

1. Ключ преобразуется в число (hash code) с помощью функции хэширования
2. Это число используется как индекс в массиве
3. Значение сохраняется по этому индексу

class SimpleHashTable:
    def __init__(self, size=10):
        self.table = [None] * size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def set(self, key, value):
        index = self._hash(key)
        self.table[index] = (key, value)
    
    def get(self, key):
        index = self._hash(key)
        if self.table[index]:
            return self.table[index][1]
        return None

ht = SimpleHashTable()
ht.set("name", "John")
print(ht.get("name"))

Сравнение с другими структурами

Без хэш-таблицы (список - O(n)):

array = [("alice", 1), ("bob", 2)]
def find_by_key(arr, target_key):
    for key, value in arr:
        if key == target_key:
            return value
    return None

С хэш-таблицей (словарь - O(1)):

my_dict = {"alice": 1, "bob": 2}
result = my_dict["bob"]

Функция хэширования

key1 = "hello"
key2 = 42

print(hash(key1))
print(hash(key2))

assert hash("hello") == hash("hello")

Требования для ключей

Ключ должен быть хэшируемым (hashable):

my_dict = {
    "string": 1,
    42: 2,
    (1, 2): 3,
}

try:
    bad = {[1, 2]: "list"}
except TypeError:
    pass

Ключ должен быть неизменяемым (immutable).

Коллизии хэшей

Если несколько ключей дают одинаковый хэш, Python обрабатывает коллизии методом цепочек.

Сложность операций

my_dict = {"a": 1}

my_dict["a"]        # O(1)
my_dict["a"] = 5    # O(1)
del my_dict["a"]    # O(1)
"a" in my_dict      # O(1)

len(my_dict)        # O(n)
list(my_dict.keys()) # O(n)

Итоговые выводы

1. Словари используют хэш-таблицы для O(1) поиска
2. Функция хэширования преобразует ключ в индекс
3. Коллизии обрабатываются автоматически
4. Ключи должны быть хэшируемыми и неизменяемыми
5. Производительность O(1) в среднем
6. Выбирай словари для быстрого поиска