Внутренняя реализация коллекций в Python: списки, множества, словари

Коллекции в Python кажутся простыми в использовании, но под капотом скрываются сложные алгоритмы и оптимизации. Разберем, как работают списки, множества и словари на уровне памяти и вычислений.

1. Списки (List): динамические массивы

Структура

Список в Python — это динамический массив указателей на объекты. Он хранит элементы в непрерывной области памяти, что обеспечивает быстрый доступ по индексу (O(1)).

Аллокация памяти

При создании списка выделяется память с запасом (over-allocation), чтобы минимизировать переаллокации при добавлении элементов.
Рост массива: При заполнении текущего буфера Python увеличивает его размер по формуле:
```
new_size = (current_size >> 3) + (current_size < 9 ? 3 : 6) + current_size
```
Например, для списка из 10 элементов новый размер будет 10 + 1 + 6 = 17.

Пример роста списка:

import sys
lst = []
prev_size = 0
for _ in range(20):
    curr_size = sys.getsizeof(lst)
    if curr_size != prev_size:
        print(f"Элементов: {len(lst)}, Выделено байт: {curr_size}")
        prev_size = curr_size
    lst.append(None)

Вывод:

Элементов: 0, Выделено байт: 56
Элементов: 4, Выделено байт: 88
Элементов: 8, Выделено байт: 120
...

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

Доступ по индексу: O(1).
append(): O(1) (амортизированная, из-за редких переаллокаций).
insert(): O(n) (сдвиг элементов).

2. Словари (Dict): хэш-таблицы с открытой адресацией

Структура

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

Аллокация памяти

Изначально создается таблица на 8 бакетов.
При достижении коэффициента заполнения (load factor) ~2/3 таблица расширяется в 2–4 раза.

Хэш-функции и коллизии

Ключи должны быть хешируемыми (реализовывать __hash__ и __eq__).
Коллизии разрешаются через квадратичное пробирование:
```
index = (hash + i + i^2) % table_size
```
где i — номер попытки.

Пример коллизии:

class TestKey:
    def __init__(self, hash):
        self.hash = hash
    def __hash__(self):
        return self.hash
    def __eq__(self, other):
        return self is other

d = {}
key1 = TestKey(10)
key2 = TestKey(10)  # Имитация коллизии
d[key1] = "A"
d[key2] = "B"  # Пробирование найдет новый бакет

Оптимизации

Compact dict (Python 3.6+): Данные хранятся в плотном массиве, а индексы — в отдельной таблице.
Удаление элементов: Бакеты помечаются как “пустые” (dummy), чтобы не ломать цепочки пробирования.

3. Множества (Set): хэш-таблицы без значений

Множества реализованы аналогично словарям, но хранят только ключи (без значений). Используют ту же логику хэширования и разрешения коллизий.

Пример:

s = set()
s.add("apple")
s.add("banana")

4. Ключевые алгоритмы и оптимизации

Хэш-функции

Для строк: вычисляется на основе всех символов.
Для чисел: хэш = само число (кроме -1, который заменяется на -2).

Переаллокация таблиц

Словари: При достижении 2/3 заполнения размер увеличивается в 4 раза, пока не достигнет 50 000 элементов, затем в 2 раза.
Множества: Аналогично словарям.

Потребление памяти

Структура	Память на элемент (в байтах, CPython 3.10)
List	8 (указатель на объект)
Dict	~48 (хэш, ключ, значение)
Set	~32 (хэш, ключ)

5. Сравнение сложности операций

Операция	List	Dict/Set
Добавление	O(1)*	O(1)
Удаление	O(n)	O(1)
Поиск	O(n)	O(1)
Доступ по ключу	–	O(1)

*Амортизированная сложность для append().

6. Практические советы

Для частых вставок/удалений используйте deque вместо list.
Избегайте коллизий в словарях: уникальные хэши ключей улучшают производительность.
Инициализируйте коллекции с ожидаемым размером, если он известен:
```
d = dict.fromkeys(keys, default_value)  # Экономит память
```

Заключение

Понимание внутренней механики коллекций помогает писать эффективный код. Списки жертвуют памятью ради скорости доступа, словари и множества используют хэш-таблицы для почти мгновенного поиска. Для углубленного изучения загляните в исходный код CPython.