Коллекции в 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. Практические советы
1. Для частых вставок/удалений используйте deque вместо list.
2. Избегайте коллизий в словарях: уникальные хэши ключей улучшают производительность.
3. Инициализируйте коллекции с ожидаемым размером, если он известен:
d = dict.fromkeys(keys, default_value) # Экономит память
Заключение
Понимание внутренней механики коллекций помогает писать эффективный код. Списки жертвуют памятью ради скорости доступа, словари и множества используют хэш-таблицы для почти мгновенного поиска. Для углубленного изучения загляните в исходный код CPython.