> Как устроены структуры данных list, dict и set в Python? (Python)

Короткий ответ

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

Подробное объяснение

list:

• Внутри - массив указателей (PyObject**), размер которого больше числа элементов (capacity > size).
• При переполнении - realloc с увеличением capacity примерно в 1.125 раза (формула new_allocated = (size >> 4) + (size < 8 ? 3 : 6) + size).
• Вставка/удаление в середине - сдвиг всех последующих элементов, O(n).
• Индексация - O(1), прямой доступ по смещению.

dict:

• Хеш-таблица с открытой адресацией (open addressing), схема probing - линейная с псевдослучайным шагом (perturb).
• Таблица хранит записи в двух массивах: indices (индексы) и entries (пары ключ-значение + хеш).
• Load factor ~2/3, при превышении - resize в 2 раза (или в 4 при маленьких размерах).
• Поиск: вычисление хеша → маскирование по размеру → проверка пустой ячейки → сравнение хешей и ключей (сначала по хешу, потом по ==).
• Ключи должны быть hashable и immutable (на практике - неизменяемые типы).
• Порядок вставки сохраняется с Python 3.7 (implementation detail в 3.6).

set:

• Использует ту же структуру, что и dict, но entries хранят только ключи (без значений).
• Операции union/intersection/difference оптимизированы через хеш-таблицы.
• Для маленьких множеств (< 5 элементов) - отдельная оптимизация через линейный поиск.

Ключевые отличия от других языков:

• В отличие от Java HashMap, Python dict не использует chaining (связные списки), а открытую адресацию - это даёт лучшую локальность кэша.
• list - не linked list, поэтому операции в начале - O(n), в отличие от deque.

На практике

• Для частых вставок/удалений в начало - использовать collections.deque.
• Для больших dict с числовыми ключами - рассмотреть array или numpy.
• Хеширование строк в Python рандомизировано (SipHash) - защита от DoS-атак через коллизии.
• Не использовать изменяемые объекты как ключи dict - нарушение инварианта хеш-таблицы.
• Для слияния dict - оператор | (Python 3.9+) создаёт новый dict, а update мутирует существующий.
• set - идеален для проверки принадлежности, удаления дубликатов, но не для упорядоченных данных.

Пример кода

PYTHON
# Внутреннее устройство list: амортизированный рост
import sys
lst = []
for i in range(1000):
    lst.append(i)
    if i % 100 == 0:
        print(f"size={i}, allocated={sys.getsizeof(lst)} bytes")

# dict: порядок вставки сохраняется
d = {}
for k in ["b", "a", "c"]:
    d[k] = 1
print(list(d.keys()))  # ['b', 'a', 'c']

# set: хеширование и коллизии
class BadHash:
    def __hash__(self):
        return 42  # все объекты в одну корзину
    def __eq__(self, other):
        return self is other

s = {BadHash() for _ in range(100)}  # O(n^2) из-за коллизий

# Практический пример: дедупликация с сохранением порядка
def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

Как отвечать на собеседовании

Начни с краткого определения каждой структуры, затем переходи к деталям реализации. Упомяни амортизационную сложность и trade-off между памятью и скоростью. Если спросят про коллизии - объясни схему probing и почему она лучше chaining для CPU-кэша. Для senior-уровня важно показать понимание внутреннего устройства: два массива в dict, формула роста list, влияние load factor на производительность. Свяжи ответ с практикой: когда выбирать list вместо set, почему нельзя использовать list как ключ dict.

Что проверяет интервьюер

• Понимание разницы между амортизированной и гарантированной сложностью.
• Знание внутреннего представления данных (массив vs linked list, хеш-таблица).
• Умение объяснить trade-off: память vs скорость, порядок vs скорость поиска.
• Понимание требований к ключам dict/set (hashable, immutable).
• Осведомлённость о деталях CPython (открытая адресация, SipHash, порядок вставки).

Типичные ошибки

• Утверждение, что list - это linked list (путаница с collections.deque).
• Заявление, что dict - это красно-чёрное дерево (как в C++ std::map).
• Игнорирование того, что set и dict требуют hashable ключи.
• Утверждение, что вставка в list в начало - O(1) (это O(n)).
• Непонимание, что dict в Python 3.7+ гарантирует порядок вставки (это не случайность).
• Путаница между == и is при сравнении ключей в хеш-таблице.