Встроенные коллекции: list, tuple, dict и set — что когда брать

База: четыре коллекции и три вопроса

Ответ уровня Junior на «что когда брать»: список — для упорядоченного набора, который меняется; кортеж — для неизменяемой записи из нескольких полей; словарь — когда значение ищут по ключу; множество — когда нужны уникальные элементы и быстрая проверка «есть ли такой». Это верно, и за этим ответом обычно идут три уточнения: насколько быстрее проверка по множеству, почему список нельзя положить в множество и что с порядком. Им и посвящены механизмы ниже.

Чем список отличается от кортежа в памяти и по скорости — отдельный урок, «Список против кортежа». Здесь — выбор между всеми четырьмя.

Механизм 1: повторы и уникальность

Вывод bench/collections/basics.py, раздел 1:

1) дубли
   list(data)          -> [3, 1, 3, 2, 1]
   set(data)           -> {1, 2, 3}
   dict.fromkeys(data) -> {3: None, 1: None, 2: None}
   {'a': 1, 'a': 2}    -> {'a': 2}
   len(set(data)) == len(data) -> False

Список хранит всё, что в него положили. Множество — только разные элементы, и порядок исходного списка теряется. Словарь хранит уникальные ключи, и при повторе ключа побеждает последнее значение.

Из этого вывода складываются два рабочих приёма:

• «Есть ли дубли» — len(set(data)) != len(data).
• «Убрать дубли, сохранив порядок» — list(dict.fromkeys(data)). Через set так нельзя: у множества порядка нет (Механизм 3), а у словаря он есть.

Механизм 2: хешируемость — кто может быть ключом

Элементы множества и ключи словаря должны быть хешируемыми. К значениям словаря это требование не относится. Множество и словарь находят элемент или ключ по хешу, поэтому хеш у него должен быть и не должен меняться; значение словаря лежит рядом с ключом, по нему не ищут, и хешировать его незачем:

Это видно на полном коротком примере. Полный файл bench/collections/hashable.py:

import sys
 
print("PY", sys.version.split()[0])
 
d = {"items": []}
d["items"].append(1)
print('{"items": []} after append:', d)
print('{(1, 2): "ok"}:', {(1, 2): "ok"})
 
for text, make in [('{[]: "x"}', lambda: {[]: "x"}), ("{[1, 2]}", lambda: {[1, 2]})]:
    try:
        make()
    except TypeError as e:
        print(text, "-> TypeError:", e)

Запуск — python3.13 bench/collections/hashable.py; вывод на CPython 3.13.7 (на 3.11 и 3.12 — тот же):

PY 3.13.7
{"items": []} after append: {'items': [1]}
{(1, 2): "ok"}: {(1, 2): 'ok'}
{[]: "x"} -> TypeError: unhashable type: 'list'
{[1, 2]} -> TypeError: unhashable type: 'list'

Словарь со списком в значении создался и даже изменился на месте; кортеж стал ключом. Список не годится ни в ключ, ни в элемент множества. Подробнее о том, что хешируемо, — вывод bench/collections/basics.py, раздел 2:

2) хешируемость: что можно класть в set и в ключи dict
   {[1, 2]}            -> TypeError: unhashable type: 'list'
   {[1, 2]: 'x'}       -> TypeError: unhashable type: 'list'
   {(1, 2)}            -> исключения нет
   {(1, [2])}          -> TypeError: unhashable type: 'list'
   {frozenset({1, 2})} -> исключения нет
   {{1, 2}}            -> TypeError: unhashable type: 'set'

Строка, которую стоит запомнить, — {(1, [2])}. Кортеж хешируем, только если хешируемо всё, что в нём лежит: хеш кортежа считается из хешей элементов, а у списка его нет. Поэтому ключом «из нескольких полей» служит кортеж неизменяемых значений, а множество множеств строят из frozenset.

Почему хеша нет у изменяемых объектов, которые сравниваются по значению, — списков, словарей, множеств: словарь кладёт ключ по хешу и потом ищет его по тому же хешу. Изменись такой ключ после вставки — его хеш изменился бы, и словарь искал бы не там. Со значением такой беды нет: его не ищут по хешу, поэтому d["items"].append(1) выше ничего не ломает. Экземпляры обычных классов изменяемы, но хешируемы: они сравниваются по тождеству, а не по значению, — об этом урок «Классы и ООП». Как это устроено внутри, разобрано в статье о словарях.

Механизм 3: порядок — у словаря есть, у множества нет

У множества такой гарантии нет. Порядок, в котором оно печатается, зависит от хешей элементов, а хеш строки от запуска к запуску разный:

Это случайное «зерно» можно зафиксировать переменной окружения PYTHONHASHSEED. Скрипт запустил сам себя трижды с разными значениями — вывод bench/collections/basics.py, раздел 3:

3) порядок
   dict в порядке вставки: ['дыня', 'яблоко', 'груша']
   удалили и вставили снова — ключ в конце: ['дыня', 'груша', 'яблоко']
   множество строк при разных PYTHONHASHSEED:
   PYTHONHASHSEED=1: ['дыня', 'груша', 'слива', 'яблоко', 'вишня']
   PYTHONHASHSEED=2: ['вишня', 'яблоко', 'дыня', 'слива', 'груша']
   PYTHONHASHSEED=3: ['дыня', 'слива', 'яблоко', 'груша', 'вишня']
   разных порядков из трёх запусков: 3
   множество целых {5, 1, 3}: {1, 3, 5} — порядок от хеша, а не от вставки
   hash(1), hash(3), hash(5): 1 3 5 — хеш небольшого целого равен ему самому
   множество целых {8, 1}: {8, 1} — и не всегда по возрастанию

Последние строки — ловушка наоборот. Множество маленьких целых часто печатается «по возрастанию», потому что хеш небольшого целого равен ему самому. Но это совпадение реализации, а не сортировка: {8, 1} напечаталось как {8, 1}, а код, который опирается на порядок, сломается на строках. Если нужен порядок — список, словарь или sorted(...).

Механизм 4: цена поиска — где разница огромна, а где её нет

Документация называет «быструю проверку вхождения» первым применением множеств. Насколько быструю — замер. Искомый элемент последний, то есть для списка худший случай:

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

Но O(1) у множества и словаря — средняя оценка, а не обещание одной проверки. Если у многих ключей один и тот же хеш, поиск сравнивает их по очереди, и худший случай — O(n): в уроке «Сложность операций» поиск в множестве из ста объектов с одинаковым хешем вызвал __eq__ 105 раз, а не один. И одна проверка сама не бесплатна: она стоит вычисления хеша и вызова __eq__, а у длинной строки и то и другое проходит по её символам.

В числах есть и сам цикл for, в котором шла проверка: пустой цикл стоит 18,7 нс на шаг — строка «пустой цикл» в записи прогона. На больших размерах это мелочь, а на десяти элементах — половина времени множества, поэтому 3,4 раза — оценка снизу: сама проверка отличается сильнее.

Но правило «всегда множество» на маленьких коллекциях не работает. На десяти элементах разница всего в 3,4 раза, а если искомый элемент первый, список находит его за 33,7 нс — так же быстро, как множество. И строить множество ради одной проверки невыгодно: построение хеширует каждый элемент и раскладывает его по таблице. Замер выше этого не видит — там коллекции готовы до начала отсчёта, — поэтому построение мерили отдельно. Вывод bench/collections/build.py (CPython 3.13.7):

построить set ради проверок: нс на сценарий, медианы 9 кругов
    размер  проверок   по списку   set(lst) + проверки
        10         1        98.8                 211.1
        10       100      8499.6                1962.7
      1000         1      4638.7                7926.6
      1000       100    596511.4               10674.0

Ради одной проверки построение множества проиграло перебору и на десяти, и на тысяче элементов; ради ста — выиграло. Множество окупается, когда проверок много; если же оно уже есть, оно быстрее и на десяти элементах. Где точка окупаемости на ваших данных — вопрос замера, а не правила.

Механизм 5: очередь — не список

Вывод bench/collections/cost.py, раздел 2:

2) удаление из начала: 50 000 удалений из коллекции в 100 000, нс на удаление
   (создание коллекции в замер не входит)
   форма                            мин   медиана      макс
   list.pop(0)                  11920.9   12662.3   13358.6
   deque.popleft()                 41.6      42.4      47.3
   list.pop() с конца              42.5      43.7      46.3
   list.pop(0) / deque.popleft() по медианам: 299

Список хранит элементы подряд, и удаление первого сдвигает все остальные на одну позицию — чем длиннее список, тем дороже. При удалении с конца сдвигать нечего, поэтому list.pop() дешёвый. Для очереди «добавляем в конец, забираем из начала» в стандартной библиотеке есть collections.deque — a list-like sequence optimized for data accesses near its endpoints (похожая на список последовательность, оптимизированная для доступа к данным у её концов). В замере popleft() дешевле list.pop(0) в 299 раз.

Глубже: что стоит память

Вывод bench/collections/basics.py, раздел 4:

4) память: сам контейнер на 1000 целых, байт (sys.getsizeof)
   list     8056
   tuple    8040
   set     32984
   dict    36952
   set / list: 4.1

sys.getsizeof считает сам контейнер, без элементов: числа общие и в счёт не идут. Список и кортеж хранят по указателю на элемент — 8 байт на 64-битной сборке, плюс заголовок. Множество и словарь держат хеш-таблицу с запасом пустых ячеек — без запаса поиск по хешу перестал бы быть быстрым, — плюс служебные данные. Отсюда в 4,1 раза больше памяти у множества: это цена быстрого in. Но 4,1 — отношение для тысячи целых на этой версии, а не константа: оно зависит от числа и вида элементов и от реализации.

Устроены множество и словарь в CPython по-разному. У множества каждая ячейка таблицы — указатель на элемент и его запомненный хеш (setentry, Include/cpython/setobject.h:20–23 в CPython 3.13.7). Словарь — это таблица индексов (dk_indices) плюс отдельный массив записей (dk_entries). Запись общего вида хранит хеш, ключ и значение (PyDictKeyEntry, Include/internal/pycore_dict.h:76–81), а запись словаря, у которого все ключи — строки, только ключ и значение (PyDictUnicodeEntry, строки 83–86): хеш строка хранит в самой себе (поле hash, Include/cpython/unicodeobject.h:101). Это видно по памяти — вывод bench/collections/basics.py, раздел 6, одинаковый на 3.11–3.14:

6) память и вид ключей: 1000 ключей, байт (sys.getsizeof)
   dict, ключи int     36952
   dict, ключи str     26032
   set, int            32984
   set, str            32984

Словарь на тех же тысяче ключах, но строковых, меньше на 10 920 байт; у множества размер от вида элементов не зависит. Детали — в статьях об устройстве списка и словаря.

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

Короткий ответ: список — упорядоченный изменяемый набор с повторами, кортеж — неизменяемый, словарь — ключ → значение с уникальными ключами, множество — уникальные элементы без порядка. Проверку вхождения и поиск по значению делают по множеству или словарю: там это поиск по хешу — O(1) в среднем и O(n) в худшем случае, когда хеши совпадают, — а в списке — перебор. Элементом множества и ключом словаря может быть только хешируемый объект; значения словаря могут быть любыми. Словарь хранит порядок вставки, множество — нет.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

На «насколько быстрее множество». «Зависит от размера и от данных. В моём прогоне на CPython 3.13.7 x in по списку на тысяче элементов был медленнее в 216 раз, на десяти — в 3,4, а первый элемент список находит так же быстро. Строить множество ради одной проверки не стоит: в замере это дольше одного перебора, окупилось на ста проверках. O(1) у множества — среднее: при совпадающих хешах поиск вырождается в перебор. Точные отношения на другой машине — мерить».

На «почему список нельзя положить в множество». «Множество ищет по хешу, а хеш изменяемого объекта мог бы поменяться после вставки. Поэтому у списка хеша нет. Кортеж хешируем, только если хешируемо всё, что в нём: {(1, [2])} падает. А значением словаря список быть может — по значениям не ищут: {"items": []} работает».

На «упорядочен ли словарь». «С 3.7 порядок вставки — гарантия языка. Удалённый и вставленный снова ключ уходит в конец. У множества порядка нет: множество строк при разных PYTHONHASHSEED печаталось по-разному».

На «как сделать очередь». «collections.deque. list.pop(0) сдвигает все элементы — у меня он был в 299 раз дороже popleft() на ста тысячах».

Дальше спросят

Частые заблуждения

История версий

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ взят из прогона скрипта, а не назначен.

words = ["b", "a", "b", "c", "a"]
print(list(dict.fromkeys(words)))
print(sorted(set(words)))
print(len(set(words)), len(words))

['b', 'a', 'c']
['a', 'b', 'c']
3 5

['a', 'b', 'c']
['a', 'b', 'c']
3 5

['b', 'a', 'b', 'c', 'a']
['a', 'b', 'c']
5 5

['b', 'a', 'c']
['b', 'a', 'c']
3 3

Проверьте себя

Чем измерено

Числа этого урока получены этими скриптами. Каждый открывается прямо отсюда — вместе с записью прогона: на чём считали, что получилось и с каким разбросом.

Наблюдения без времени — CPython 3.11.15, 3.12.3, 3.13.7 и 3.14.7; замеры времени — 3.13.7 и 3.14.7 на одной машине с двумя ядрами. Скрипты bench/collections/hashable.py, bench/collections/build.py и раздел 6 bench/collections/basics.py добавлены и запущены 14.10.2026 на linux/x86_64. Контракты и цитаты сверены 14.10.2026. Python 3.15 (вышел 9 октября 2026) урок не запускал — о нём только строка в истории версий.

• bench/collections/basics.py
• bench/collections/cost.py
• bench/collections/build.py
• bench/collections/hashable.py
• bench/collections/practice.py