Как устроены изменяемые типы в Python?

Основные концепции изменяемых типов

Изменяемые (mutable) типы в Python — это объекты, которые можно изменять после создания без создания нового объекта. Главные представители: списки (list), словари (dict) и множества (set). Понимание того, как они устроены, критично для написания эффективного кода и избежания неожиданного поведения.

Как работает изменяемость

Когда вы создаёте изменяемый объект, Python выделяет блок памяти и возвращает ссылку на этот объект. При изменении содержимого (добавление элементов, изменение значений), изменяется само содержимое памяти, но ссылка остаётся той же:

my_list = [1, 2, 3]
original_id = id(my_list)
my_list.append(4)  # Изменяем содержимое
print(id(my_list) == original_id)  # True — объект тот же!

Списки (List)

Список — это динамический массив, реализованный как массив указателей на Python-объекты:

# Создание и базовые операции
my_list = [1, 2, 3]
my_list[0] = 10  # O(1) — прямой доступ к элементу
my_list.append(4)  # O(1) amortized — добавление в конец
my_list.insert(1, 5)  # O(n) — вставка в середину смещает элементы
my_list.pop()  # O(1) — удаление с конца
my_list.remove(5)  # O(n) — удаление по значению требует поиска

Внутренняя структура: Python использует динамический размер буфера (overallocation). Когда буфер полон, создаётся новый буфер большего размера (~1.125x) и данные копируются туда. Это делает append() эффективным в среднем:

# Демонстрация переаллокации
import sys
lst = []
sizes = []
for i in range(100):
    if not sizes or sys.getsizeof(lst) != sizes[-1]:
        sizes.append(sys.getsizeof(lst))
    lst.append(i)
print(f"Количество переаллокаций: {len(sizes)}")

Словари (Dict)

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

my_dict = {"a": 1, "b": 2}
my_dict["c"] = 3  # O(1) добавление
value = my_dict["a"]  # O(1) поиск
del my_dict["b"]  # O(1) удаление

Как работает: Python вычисляет хеш ключа, использует его как индекс в таблице. При коллизиях (разные ключи с одинаковым хешем) использует probing. Python 3.6+ гарантирует сохранение порядка вставки, так как реализация включает отдельный массив для этого:

# Проверка сохранения порядка
d = {}
d["z"] = 1
d["a"] = 2
d["m"] = 3
print(list(d.keys()))  # ["z", "a", "m"] — порядок вставки

# Хеширование
print(hash("hello"))  # Хеш строки постоянен в рамках сессии

Множества (Set)

Множество — это хеш-таблица без значений, содержащая только ключи:

my_set = {1, 2, 3}
my_set.add(4)  # O(1)
my_set.remove(2)  # O(1)
my_set.discard(5)  # O(1), не вызывает ошибку если элемента нет

# Операции множеств
set1 = {1, 2, 3}
set2 = {2, 3, 4}
print(set1 & set2)  # {2, 3} — пересечение
print(set1 | set2)  # {1, 2, 3, 4} — объединение
print(set1 - set2)  # {1} — разность

Критический момент: копирование vs ссылки

Это главный источник ошибок с изменяемыми типами:

# ❌ Неправильно — изменяет обе переменные!
original = [1, 2, 3]
copy = original  # copy указывает на ТОТ ЖЕ объект
copy.append(4)
print(original)  # [1, 2, 3, 4] — original изменена!

# ✅ Правильно — поверхностная копия
copy = original.copy()  # или original[:]
copy.append(4)
print(original)  # [1, 2, 3] — original не изменена

# ✅ Глубокая копия для вложенных структур
import copy
nested = [[1, 2], [3, 4]]
deep_copy = copy.deepcopy(nested)
deep_copy[0].append(999)
print(nested)  # [[1, 2], [3, 4]] — не изменена

Производительность

# Списки: быстры для random access, медленны для удаления в начале
lst = list(range(1000000))
lst[500000] = 0  # O(1) — очень быстро
lst.pop(0)  # O(n) — медленно, смещает все элементы

# Словари: быстры для поиска
d = {i: i for i in range(1000000)}
value = d[500000]  # O(1) — очень быстро

# Множества: быстры для проверки принадлежности
s = set(range(1000000))
if 500000 in s:  # O(1) — быстрее, чем in в списке O(n)
    pass

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

• Используй списки, когда нужен порядок и индексный доступ
• Используй словари для отображений ключ→значение
• Используй множества для проверки принадлежности и уникальности
• Избегай присваивания изменяемых объектов как значений по умолчанию в функциях
• Копируй когда передаёшь в функцию и функция может изменять