Какая алгоритмическая сложность поиска в словаре в Python?

Алгоритмическая сложность поиска в словаре в Python

Поиск в словаре (dict) в Python имеет среднюю временную сложность O(1) — константную. В худшем случае это может быть O(n), но на практике это очень редко. Это один из самых важных фактов в алгоритмике Python.

Почему O(1)? Хеширование

Словарь в Python реализован через хеш-таблицу. Вот как это работает:

# Внутри Python
data = {}
data['key'] = 'value'

# Python делает:
# 1. Вычисляет хеш: hash('key') -> 12345678 (какое-то число)
# 2. Находит индекс в массиве: 12345678 % array_size -> 42
# 3. Обращается к массиву[42] -> находит значение
# ВСЁ за O(1)!

Практический пример производительности

import time

# Поиск в списке — O(n)
my_list = list(range(1000000))
start = time.time()
result = 999999 in my_list  # Проверит 1000000 элементов
print(f"List: {time.time() - start:.6f}s")  # ~0.01s

# Поиск в словаре — O(1)
my_dict = {i: i for i in range(1000000)}
start = time.time()
result = 999999 in my_dict  # Только хеширование
print(f"Dict: {time.time() - start:.6f}s")  # ~0.000001s

# Разница в 10000 раз!

Как работает хеш-таблица

class SimpleHashTable:
    def __init__(self):
        self.size = 8
        self.table = [None] * self.size
    
    def put(self, key, value):
        # 1. Вычислить хеш
        h = hash(key)
        
        # 2. Найти индекс
        index = h % self.size
        
        # 3. Сохранить (с handling коллизий)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            self.table[index].append((key, value))
    
    def get(self, key):
        h = hash(key)
        index = h % self.size
        
        if self.table[index] is None:
            raise KeyError(key)
        
        # Поиск в списке коллизий (обычно 1 элемент)
        for k, v in self.table[index]:
            if k == key:
                return v
        
        raise KeyError(key)

ht = SimpleHashTable()
ht.put('name', 'Alice')
print(ht.get('name'))  # Alice за O(1)

Коллизии (hash collisions)

Когда два разных ключа имеют один и тот же хеш, происходит коллизия:

# Пример коллизии (редко на практике)
class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 42  # Всегда возвращает одно число!
    
    def __eq__(self, other):
        return self.value == other.value

# Создаём коллизию
data = {}
for i in range(1000):
    key = BadHash(i)
    data[key] = i

# Поиск теперь может быть O(n) из-за коллизий
result = data[BadHash(999)]  # Нужно проверить все 1000 элементов!

Временная сложность операций со словарём

# O(1) операции:
d = {}
d['key'] = 'value'           # insert/update
value = d['key']             # lookup
del d['key']                 # delete
'key' in d                    # membership test

# O(n) операции:
list(d.keys())               # все ключи
list(d.values())             # все значения
list(d.items())              # все пары
d1.update(d2)                # объединение

# O(n) или O(n log n) в зависимости от реализации:
sorted(d.keys())             # сортировка ключей

Python 3.6+ особенность: сохранение порядка

По усло CPython 3.6+, словари сохраняют порядок вставки. Это не влияет на сложность O(1):

d = {}
d['first'] = 1
d['second'] = 2
d['third'] = 3

for key in d:  # Итерирует в порядке вставки
    print(key)
# first
# second
# third

# Поиск остаётся O(1)
print(d['second'])  # Быстро, несмотря на сохранение порядка

Сравнение: dict vs set

# SET тоже использует хеш-таблицу -> O(1)
my_set = {1, 2, 3, 4, 5}

result = 3 in my_set      # O(1)
my_set.add(6)             # O(1)
my_set.remove(3)          # O(1)

# vs LIST - O(n)
my_list = [1, 2, 3, 4, 5]
result = 3 in my_list     # O(n)

# Для проверки наличия элемента — используй SET!

Когда словарь медленнее

# 1. Несhashable типы как ключи
try:
    d = {[1, 2]: 'value'}  # TypeError! Списки не можно хешировать
except TypeError:
    print("Lists are not hashable")

# Используй tuple вместо list
d = {(1, 2): 'value'}  # OK

# 2. Дорогие операции на больших словарях
b = {i: i for i in range(1000000)}
d1 = b.copy()  # O(n) - копирует все элементы

Память и сложность

Словарь использует больше памяти, чем список, из-за хеш-таблицы:

import sys

my_list = list(range(1000))
my_dict = {i: i for i in range(1000)}

print(sys.getsizeof(my_list))  # ~8000 bytes
print(sys.getsizeof(my_dict))  # ~36000 bytes (больше для хеш-таблицы)

# Но поиск стоит того компромисса

Выбор структуры данных

# Нужен поиск по ключу? -> dict
users = {'alice': User('Alice'), 'bob': User('Bob')}
user = users['alice']  # O(1)

# Нужно проверить наличие? -> set
allowed_ids = {1, 2, 3, 4, 5}
if user_id in allowed_ids:  # O(1)
    grant_access()

# Нужна упорядоченность? -> list
results = [1, 2, 3, 4, 5]
for item in results:  # Гарантирует порядок
    process(item)

# Нужна комбинация? -> collections.OrderedDict (Python 3.7+ не нужна)
from collections import OrderedDict
ordered = OrderedDict()  # Сохраняет порядок + O(1) поиск

Худший случай

Худший случай O(n) в теории, но в Python это очень редко:

# Плохо написанный хеш-класс
class BadKey:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 1  # Все объекты имеют один хеш!
    
    def __eq__(self, other):
        return self.value == other.value

# Это медленно:
d = {BadKey(i): i for i in range(10000)}
result = d[BadKey(9999)]  # O(n)!

Но в реальном коде Python использует хорошие хеш-функции для встроенных типов.

Выводы

1. Поиск в dict — O(1) в среднем случае
2. Хеш-таблица лежит в основе dict и set
3. Коллизии редки благодаря хорошим хеш-функциям
4. Используй dict для поиска, set для проверки наличия
5. Понимание O(1) критично для оптимизации алгоритмов