list, tuple, dict и set в Python: устройство и сложность

На собесе по коллекциям спрашивают две вещи: как они устроены внутри и сколько стоят операции. Ответ «dict это хеш-таблица, поиск за O(1) в среднем» обязателен, но интервьюер почти всегда копает дальше.

list: динамический массив

list хранит массив указателей на объекты. Когда место кончается, CPython выделяет новый массив с запасом и переносит указатели, поэтому append в среднем O(1) (амортизированно).

Операция	Сложность
lst[i], lst[i] = x, len, append, pop()	O(1)
insert(0, x), pop(0), del lst[0]	O(n): сдвиг всех элементов
x in lst, lst.index(x), remove	O(n)
sort	O(n log n), алгоритм Timsort, сортировка стабильная
срез lst[a:b]	O(b - a), создаёт новый список

Если нужна очередь, берите collections.deque: appendleft и popleft за O(1).

tuple

Неизменяемая последовательность фиксированной длины. Занимает чуть меньше памяти, чем список, хешируема (если хешируемы элементы), годится как ключ словаря и как «запись» из нескольких полей. Для записей с именами полей есть typing.NamedTuple и dataclass.

dict: хеш-таблица с порядком вставки

С Python 3.7 порядок вставки ключей гарантирован языком. Внутри CPython держит компактный массив записей (хеш, ключ, значение) в порядке вставки и отдельную разреженную таблицу индексов. Поиск: считаем hash(key), по нему ищем слот, при коллизии пробуем следующие слоты (открытая адресация), затем сравниваем ключи через ==.

• Поиск, вставка, удаление: O(1) в среднем, O(n) в худшем случае (если у всех ключей одинаковый хеш).
• Ключ обязан быть хешируемым, и его хеш не должен меняться.
• Менять размер словаря во время итерации нельзя: RuntimeError: dictionary changed size during iteration. Итерируйтесь по list(d).

d = {'a': 1}
d.get('b', 0)                 # 0, без KeyError
d.setdefault('list', []).append(1)
merged = d | {'c': 3}         # 3.9+: слияние в новый словарь

set

Множество тоже хеш-таблица, только без значений. Проверка x in s за O(1) в среднем, есть операции |, &, -, ^. Порядок элементов не гарантирован. Пустое множество это set(), а {} создаёт словарь.

Типичное ускорение на собесе: заменить x in list в цикле на x in set, и O(n²) превращается в O(n).

Comprehension и генераторные выражения

squares = [x * x for x in range(10) if x % 2]
index = {name: i for i, name in enumerate(names)}
unique = {w.lower() for w in words}
total = sum(x * x for x in range(10))  # без промежуточного списка

У comprehension своя область видимости: переменная цикла не утекает наружу.

Модуль collections

• Counter: подсчёт, most_common(k), арифметика счётчиков.
• defaultdict(list): группировка без проверок if key not in d.
• deque(maxlen=n): очередь с двух сторон и «последние n элементов».
• OrderedDict: сейчас нужен ради move_to_end и popitem(last=False), например для LRU.
• ChainMap: несколько словарей как один (настройки по слоям).

Частые ошибки

• pop(0) в цикле на большом списке: O(n²). Нужен deque.
• Удаление элементов списка во время прохода по нему: элементы пропускаются.
• Изменяемый объект как ключ словаря или элемент множества.
• Ожидание, что set сохраняет порядок.
• dict.fromkeys(keys, []): все ключи получат один и тот же список.

Что спросят на собесе

• Как устроен dict, что такое коллизия и почему ключ должен быть хешируемым.
• Сложность append, insert(0), in для списка и множества.
• Чем list отличается от tuple, когда что брать.
• Гарантирован ли порядок в dict и в set.
• Как сгруппировать или посчитать элементы: defaultdict, Counter.