Как получить O(1) при обращении к элементу по ключу?

O(1) доступ по ключу: Hash Tables

Добиться O(1) средней сложности при доступе к элементу по ключу можно используя хеш-таблицы. В Python это основной механизм работы dict и set.

Базовая идея: Hash Function

# Хеширование преобразует ключ в индекс массива
def simple_hash(key: str, size: int) -> int:
    """Простая хеш-функция"""
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % size

# Пример
size = 10
key = "python"
index = simple_hash(key, size)  # Всегда вернёт одинаковый индекс
print(index)  # Например: 7

Как работает dict в Python

# Python dict — это хеш-таблица
data = {}  # Внутри огромный массив с пустыми слотами

# Когда ты добавляешь элемент
data['user_id'] = 123

# Компьютер делает так:
# 1. hash('user_id') -> 45678 (огромное число)
# 2. 45678 % len(data) -> индекс в массиве (например, 5)
# 3. data[5] = (ключ='user_id', значение=123)

# Когда ты получаешь элемент
value = data['user_id']

# Компьютер делает:
# 1. hash('user_id') -> 45678 (тот же хеш)
# 2. 45678 % len(data) -> индекс 5 (тот же индекс)
# 3. Возвращает data[5].value -> 123

# Это O(1) если нет коллизий!

Реализация простой хеш-таблицы

from typing import Any, Optional, Tuple

class HashTable:
    """Простая реализация хеш-таблицы с chaining для разрешения коллизий"""
    
    def __init__(self, capacity: int = 16):
        self.capacity = capacity
        # Таблица содержит списки (цепочки) для разрешения коллизий
        self.table: list = [[] for _ in range(capacity)]
        self.size = 0
    
    def _hash(self, key: Any) -> int:
        """Хеш-функция"""
        return hash(key) % self.capacity
    
    def put(self, key: Any, value: Any) -> None:
        """Добавить или обновить элемент - O(1) в среднем"""
        index = self._hash(key)
        bucket = self.table[index]
        
        # Проверить, есть ли уже такой ключ
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Обновить
                return
        
        # Добавить новую пару
        bucket.append((key, value))
        self.size += 1
        
        # Resize если коэффициент загрузки > 0.75
        if self.size / self.capacity > 0.75:
            self._resize()
    
    def get(self, key: Any) -> Optional[Any]:
        """Получить значение по ключу - O(1) в среднем"""
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return None
    
    def remove(self, key: Any) -> bool:
        """Удалить элемент - O(1) в среднем"""
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        
        return False
    
    def _resize(self) -> None:
        """Увеличить размер таблицы"""
        old_table = self.table
        self.capacity *= 2
        self.table = [[] for _ in range(self.capacity)]
        self.size = 0
        
        # Перехешировать все элементы
        for bucket in old_table:
            for key, value in bucket:
                self.put(key, value)
    
    def __setitem__(self, key: Any, value: Any) -> None:
        self.put(key, value)
    
    def __getitem__(self, key: Any) -> Any:
        return self.get(key)
    
    def __delitem__(self, key: Any) -> None:
        self.remove(key)
    
    def __contains__(self, key: Any) -> bool:
        return self.get(key) is not None

# Использование
table = HashTable()

# O(1) добавление
table['user_1'] = {'name': 'Alice', 'age': 30}
table['user_2'] = {'name': 'Bob', 'age': 25}

# O(1) получение
user = table['user_1']  # {'name': 'Alice', 'age': 30}

# O(1) проверка
if 'user_1' in table:
    print('Found')

# O(1) удаление
del table['user_2']

Python dict и set уже O(1)

# В Python dict и set — встроенные хеш-таблицы

# dict — O(1)
users = {}
users['alice'] = {'age': 30}  # O(1)
value = users['alice']        # O(1)
'alice' in users              # O(1)
del users['alice']            # O(1)

# set — O(1)
active_users = set()
active_users.add('alice')     # O(1)
'alice' in active_users       # O(1)
active_users.remove('alice')  # O(1)

# ⚠️ Но итерация: O(n)
for user in users:            # O(n)
    print(user)

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

import time

# dict (хеш-таблица) — O(1)
data_dict = {f'key_{i}': i for i in range(100_000)}

start = time.time()
for _ in range(1_000_000):
    value = data_dict['key_50000']  # O(1)
print(f'dict: {time.time() - start:.4f}s')

# list (массив) — O(n) если искать линейный поиск
data_list = [('key_' + str(i), i) for i in range(100_000)]

start = time.time()
for _ in range(1_000_000):
    for key, val in data_list:  # O(n)
        if key == 'key_50000':
            value = val
            break
print(f'list: {time.time() - start:.4f}s')

# list (бинарный поиск) — O(log n)
data_list_sorted = sorted([(f'key_{i}', i) for i in range(100_000)])
import bisect

start = time.time()
for _ in range(1_000_000):
    idx = bisect.bisect_left(data_list_sorted, ('key_50000',))
    if idx < len(data_list_sorted) and data_list_sorted[idx][0] == 'key_50000':
        value = data_list_sorted[idx][1]
print(f'binary search: {time.time() - start:.4f}s')

# Результат: dict >> binary search >> linear search

Когда коллизии нарушают O(1)

# Коллизия — когда разные ключи хешируются в один индекс

class BadHashTable:
    def __init__(self):
        self.table = [[] for _ in range(10)]
    
    def bad_hash(self, key: str) -> int:
        # ❌ Плохая хеш-функция: всё хешируется в индекс 0
        return 0
    
    def put(self, key: str, value: Any):
        index = self.bad_hash(key)
        self.table[index].append((key, value))
    
    def get(self, key: str) -> Any:
        index = self.bad_hash(key)  # Всегда 0
        for k, v in self.table[index]:  # Линейный поиск в цепочке
            if k == key:
                return v
        return None

# Если много коллизий: O(n) вместо O(1)
bad_table = BadHashTable()
for i in range(1000):
    bad_table.put(f'key_{i}', i)

# get() скрывает O(n) потому что все элементы в таблице[0]
value = bad_table.get('key_500')  # O(n) вместо O(1)

Требования к хеш-функции

# Хорошая хеш-функция должна:

1. Быстрой — O(1) для вычисления
   ✅ hash('key') — быстро
   ❌ len(key) + sum(ord(c) for c in key) — медленнее

2. Детерминированной — одинаковый ключ -> одинаковый хеш
   ✅ hash('abc') всегда одинаковый в одной программе
   ❌ random.randint() — каждый раз разный

3. Равномерной — распределять ключи по всем индексам
   ✅ Встроенная hash() в Python
   ❌ Если всё хешируется в индекс 0

4. Минимизировать коллизии
   ✅ hash() использует криптографические функции
   ❌ % i для всех ключей

# Python hash() уже оптимизирована
print(hash('hello'))     # -8516432898831100022
print(hash('hello'))     # -8516432898831100022 (одинаково)
print(hash('world'))     # 5614928457815651869 (разное)

Практические примеры O(1)

Кэш

class Cache:
    def __init__(self, max_size: int = 1000):
        self.data = {}  # O(1) доступ
        self.max_size = max_size
    
    def get(self, key: str):
        return self.data.get(key)  # O(1)
    
    def set(self, key: str, value: Any):
        if len(self.data) >= self.max_size:
            # Удалить случайный элемент
            first_key = next(iter(self.data))
            del self.data[first_key]  # O(1)
        
        self.data[key] = value  # O(1)

# Использование
cache = Cache()
cache.set('user_1', {'name': 'Alice'})  # O(1)
user = cache.get('user_1')              # O(1)

Дедупликация

def remove_duplicates_fast(items: list) -> list:
    """O(n) используя set"""
    seen = set()  # Хеш-таблица
    result = []
    
    for item in items:         # O(n)
        if item not in seen:   # O(1) проверка в set
            seen.add(item)     # O(1) добавление в set
            result.append(item)
    
    return result  # O(n) итого

# Vs O(n^2) с list
def remove_duplicates_slow(items: list) -> list:
    result = []
    for item in items:                  # O(n)
        if item not in result:          # O(n) линейный поиск
            result.append(item)
    return result  # O(n^2) итого

# Сравнение
import time
items = list(range(100_000)) + list(range(50_000))  # С дубликатами

start = time.time()
remove_duplicates_fast(items)  # O(n)
print(f'Fast: {time.time() - start:.4f}s')

start = time.time()
remove_duplicates_slow(items)  # O(n^2)
print(f'Slow: {time.time() - start:.4f}s')

Counting

from collections import Counter

def count_words_fast(words: list) -> dict:
    """O(n) используя dict"""
    count = {}  # Хеш-таблица
    for word in words:                   # O(n)
        count[word] = count.get(word, 0) + 1  # O(1) get и set
    return count

# Или встроенная Counter (тоже dict)
count = Counter(['apple', 'banana', 'apple'])
print(count['apple'])  # 2, O(1)

Лучшие практики

1. Используй dict вместо list когда нужна O(1) поиск по ключу
2. Используй set для проверки принадлежности O(1)
3. Не переполняй хеш-таблицу — следи за коэффициентом загрузки
4. Ключи должны быть hashable — строки, числа, кортежи
5. Избегай mutable ключей — списки нельзя использовать как ключи
6. Для больших данных — рассмотри индексы в БД

Лимитации

# ❌ Не всё может быть ключом
data = {}
data[(1, 2)] = 'ok'  # ✅ Кортеж hashable
# data[[1, 2]] = 'ok'  # ❌ Список not hashable

# Нужны сортированные данные? dict не гарантирует порядок
data = {'z': 1, 'a': 2, 'b': 3}
for key in sorted(data):  # O(n log n) для сортировки
    print(key)

# Для сортированного доступа O(log n) используй Tree (TreeMap/Red-Black Tree)
# В Python: sortedcontainers.SortedDict
from sortedcontainers import SortedDict
sorted_data = SortedDict(data)
for key in sorted_data:  # O(n) но уже отсортирован
    print(key)

Hash table — фундаментальная структура данных для O(1) доступа по ключу!