Типы данных и Коллекции #

1. Как работает set? #

Что такое set #

set — это встроенная коллекция Python для хранения уникальных элементов.

s = {1, 2, 3, 3, 2}

print(s)  # {1, 2, 3}

Дубликаты автоматически убираются, потому что множество хранит каждый элемент только один раз. В документации Python set описан как неупорядоченная коллекция уникальных hashable-объектов.

Главное отличие от list #

list хранит элементы по позициям:

lst = [10, 20, 30]
print(lst[0])  # 10

set не хранит элементы по индексам:

s = {10, 20, 30}

print(s[0])  # TypeError

У set нет индексов, срезов и гарантированного порядка элементов, потому что это не последовательность. Python прямо указывает, что множества не записывают позицию элемента или порядок вставки.

Как set ищет элементы #

Внутри CPython set работает примерно как хеш-таблица.

Когда ты делаешь:

s = {10, 20, 30}

print(20 in s)

Python не перебирает все элементы по очереди, как список. Он делает примерно следующее:

20
↓
hash(20)
↓
индекс в таблице
↓
проверка: лежит ли там нужный элемент

Именно поэтому проверка наличия элемента в set обычно очень быстрая. В Python Tutorial отдельно указано, что set используют для быстрой проверки принадлежности и удаления дубликатов.

Упрощённая схема #

set = хеш-таблица

элемент: "cat"
hash("cat") -> число
число -> позиция внутри таблицы

таблица:
[ пусто ]
[ "dog" ]
[ пусто ]
[ "cat" ]
[ "bird" ]

Когда ты пишешь:

"cat" in animals

Python вычисляет хеш "cat" и почти сразу понимает, где искать.

Почему элементы должны быть hashable #

Элемент set должен иметь стабильный хеш.

Можно:

s = {1, "hello", (1, 2)}

Нельзя:

s = {[1, 2, 3]}
# TypeError: unhashable type: 'list'

list изменяемый, поэтому его нельзя безопасно использовать как элемент множества. Документация Python указывает, что элементы set, как и ключи словаря, должны быть hashable.

Почему дубликаты удаляются #

Пример:

s = set([1, 2, 2, 3, 3, 3])

print(s)  # {1, 2, 3}

Когда Python добавляет элемент, он проверяет:

1 уже есть? нет  -> добавить
2 уже есть? нет  -> добавить
2 уже есть? да   -> не добавлять
3 уже есть? нет  -> добавить
3 уже есть? да   -> не добавлять

Поэтому set часто используют для удаления повторов:

numbers = [1, 2, 2, 3, 3, 4]

unique = set(numbers)

print(unique)  # {1, 2, 3, 4}

Основные операции #

a = {1, 2, 3}
b = {3, 4, 5}

Объединение:

print(a | b)  # {1, 2, 3, 4, 5}

Пересечение:

print(a & b)  # {3}

Разность:

print(a - b)  # {1, 2}

Симметрическая разность:

print(a ^ b)  # {1, 2, 4, 5}

Эти операции официально указаны в документации Python: union, intersection, difference и symmetric difference.

Скорость операций #

Для CPython в среднем:

x in set        -> O(1)
add(x)          -> O(1)
remove(x)       -> O(1)
перебор set     -> O(n)

Но в худшем случае из-за коллизий хешей поиск может деградировать до O(n). Python Wiki по временной сложности указывает для x in s у set: средний случай O(1), худший случай O(n).

Что такое коллизия #

Коллизия — это когда разные элементы попали в одну или близкую позицию хеш-таблицы.

Условно:

hash("cat") -> 5
hash("dog") -> 5

Тогда Python должен дополнительно проверить, какой именно элемент лежит в этой позиции. Поэтому set сначала использует hash(), а потом при необходимости сравнивает элементы через ==.

set изменяемый, frozenset неизменяемый #

Обычный set можно менять:

s = {1, 2}

s.add(3)
s.remove(1)

print(s)  # {2, 3}

Но сам set нельзя положить внутрь другого set:

s = {{1, 2}}
# TypeError: unhashable type: 'set'

Для этого есть frozenset:

s = {frozenset({1, 2}), frozenset({3, 4})}

Документация Python различает set и frozenset: set изменяемый и не имеет хеша, а frozenset неизменяемый и hashable.

Коротко #

set — это коллекция для уникальных элементов.

list -> порядок, индексы, дубликаты
set  -> уникальность, быстрый поиск, без индексов

Используй set, когда нужно:

быстро проверить наличие элемента
убрать дубликаты
сравнивать группы элементов
делать объединение / пересечение / разность

Главная идея: set жертвует порядком и индексами ради уникальности и быстрого поиска.

2. Что представляет собой тип данных множество (set) #

Что представляет собой set #

set — это встроенный тип данных Python, который представляет собой множество.

Множество — это коллекция элементов, где:

1. Каждый элемент хранится только один раз
2. Порядок элементов не считается важным
3. Быстро проверяется наличие элемента
4. Элементы должны быть hashable

Официальная документация Python определяет set как неупорядоченную коллекцию без повторяющихся элементов. Основные применения: проверка принадлежности элемента и удаление дубликатов.

Пример #

numbers = {1, 2, 3, 3, 4, 4}

print(numbers)

Результат:

{1, 2, 3, 4}

Повторяющиеся значения 3 и 4 не сохраняются повторно.

Важные свойства set #

1. Уникальность элементов #

s = {1, 1, 2, 2, 3}

print(s)

{1, 2, 3}

set автоматически убирает дубликаты.

2. Нет доступа по индексу #

s = {10, 20, 30}

print(s[0])

Будет ошибка:

TypeError: 'set' object is not subscriptable

Потому что set — не последовательность вроде list или tuple.

3. Быстрая проверка наличия элемента #

users = {"admin", "moderator", "guest"}

print("admin" in users)  # True
print("root" in users)   # False

Для таких проверок set обычно подходит лучше, чем list, потому что внутри он использует хеширование.

4. Элементы должны быть неизменяемыми / hashable #

Можно хранить:

s = {1, "hello", (1, 2)}

Нельзя хранить:

s = {[1, 2, 3]}

Будет ошибка:

TypeError: unhashable type: 'list'

list изменяемый, поэтому его нельзя использовать как элемент множества. Документация Python указывает, что элементы множества должны быть hashable, как и ключи словаря.

Для чего используют set #

Удаление дубликатов #

numbers = [1, 2, 2, 3, 3, 4]

unique_numbers = set(numbers)

print(unique_numbers)

{1, 2, 3, 4}

Проверка принадлежности #

allowed_roles = {"admin", "manager", "moderator"}

role = "admin"

if role in allowed_roles:
    print("Доступ разрешён")

Математические операции над множествами #

a = {1, 2, 3}
b = {3, 4, 5}

Объединение:

print(a | b)  # {1, 2, 3, 4, 5}

Пересечение:

print(a & b)  # {3}

Разность:

print(a - b)  # {1, 2}

Симметрическая разность:

print(a ^ b)  # {1, 2, 4, 5}

Эти операции поддерживаются встроенными объектами set и frozenset.

set vs list #

list:
- хранит порядок
- допускает дубликаты
- есть индексы
- поиск элемента обычно медленнее

set:
- хранит только уникальные элементы
- не предназначен для доступа по индексу
- быстро проверяет наличие элемента
- удобен для операций множеств

Пример:

items = ["a", "b", "a", "c"]

lst = list(items)
st = set(items)

print(lst)  # ['a', 'b', 'a', 'c']
print(st)   # {'a', 'b', 'c'}

Коротко #

set — это тип данных для хранения уникальных элементов без привязки к индексам.

Главная идея:

set нужен не для порядка,
а для уникальности и быстрой проверки наличия.

На практике set чаще всего используют, когда нужно убрать дубликаты, быстро проверить x in collection или выполнить операции вроде объединения и пересечения множеств.

3. Как разрешаются коллизии в hash-таблицах? #

Что такое коллизия #

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

Условно:

hash("cat") % table_size -> 5
hash("dog") % table_size -> 5

Оба ключа хотят попасть в ячейку 5, но физически в одной ячейке нельзя просто хранить два разных значения одинаковым образом. Поэтому hash-таблице нужен механизм разрешения коллизий.

Основные способы разрешения коллизий #

1. Метод цепочек #

Идея: каждая ячейка массива хранит не один элемент, а контейнер элементов.

индекс 0 -> пусто
индекс 1 -> пусто
индекс 2 -> [("cat", 10), ("dog", 20), ("fox", 30)]
индекс 3 -> пусто

Когда возникает коллизия, новый элемент добавляется в цепочку по этому индексу.

Поиск работает так:

1. Вычисляем hash(key)
2. Получаем индекс массива
3. Заходим в цепочку по этому индексу
4. Ищем нужный ключ через сравнение ==

Пример:

bucket = [
    ("cat", 10),
    ("dog", 20),
    ("fox", 30),
]

for key, value in bucket:
    if key == "dog":
        print(value)

Минус: если много элементов попало в одну цепочку, поиск становится медленнее.

В Java HashMap построен как hash-table-based реализация Map; документация указывает, что при нормальном распределении хешей базовые операции get и put дают constant-time performance, но много ключей с одинаковым hashCode() замедляют любую hash-таблицу. Также Java учитывает capacity и load factor, а при превышении порога выполняет rehash. ( Документация Oracle)

2. Открытая адресация #

Идея: все элементы хранятся прямо внутри массива hash-таблицы.

Если нужная ячейка занята, таблица ищет другую свободную ячейку по определённому правилу.

хотели положить key в индекс 5

индекс 5 занят
↓
проверяем индекс 6
↓
занят
↓
проверяем индекс 7
↓
свободен
↓
кладём туда

Упрощённо:

индекс 0 -> пусто
индекс 1 -> ("apple", 100)
индекс 2 -> ("cat", 10)
индекс 3 -> ("dog", 20)
индекс 4 -> пусто

Тут "cat" и "dog" могли изначально попасть в один индекс, но один из них был смещён в другую ячейку.

Виды поиска свободной ячейки #

Линейное пробирование #

Проверяем следующую ячейку:

i
i + 1
i + 2
i + 3
...

Пример:

hash(key) -> 3

3 занято
4 занято
5 свободно

Плюс: просто и хорошо работает с кэшем процессора.

Минус: может появляться кластеризация — длинные плотные участки занятых ячеек.

Квадратичное пробирование #

Прыгаем не на +1, а по возрастающим смещениям:

i + 1²
i + 2²
i + 3²
...

То есть:

i + 1
i + 4
i + 9
i + 16
...

Это уменьшает проблему плотных кластеров, но реализация сложнее.

Двойное хеширование #

Используются две хеш-функции:

index = hash1(key)
step = hash2(key)

Если первая ячейка занята, следующая позиция считается через шаг step.

index
index + step
index + 2 * step
index + 3 * step
...

Плюс: разные ключи получают разные последовательности поиска.

Минус: нужно аккуратно подбирать вторую хеш-функцию.

Как это работает в CPython #

В CPython dict использует открытую адресацию, а не метод цепочек. При коллизии он строит последовательность проб: сначала берёт начальный индекс, потом переходит к другим индексам по специальной формуле. В комментариях к исходному коду CPython указано, что при коллизиях стратегия разрешения коллизий критически важна; CPython использует рекуррентную формулу j = ((5*j) + 1) mod 2**i, а затем добавляет perturb, чтобы задействовать больше битов хеша.

Упрощённо:

key
↓
hash(key)
↓
первый индекс
↓
если занято другим ключом
↓
вычислить следующий индекс
↓
проверить его
↓
повторять, пока ключ не найден или не встретится пустая ячейка

Для set в CPython логика близкая: реализация основана на dictobject.c, начальный индекс считается как hash mod table_size, а последующие пробы вычисляются похожим образом. В комментарии к setobject.c прямо указано, что используется гибрид линейного пробирования и рандомизированного пробирования, чтобы улучшить локальность кэша и разбивать длинные цепочки коллизий. ( GitHub)

Что происходит при поиске в hash-таблице #

Допустим, ищем ключ "dog".

1. Считаем hash("dog")
2. Получаем индекс, например 5
3. Смотрим ячейку 5

Дальше варианты:

ячейка пустая
-> ключа точно нет

ячейка занята ключом "dog"
-> нашли

ячейка занята другим ключом
-> коллизия, идём по следующей позиции

Важно: hash-таблица не полагается только на hash.

Она делает две проверки:

1. hash совпадает?
2. ключи равны через ==?

Потому что разные объекты могут иметь одинаковый hash.

Что происходит при добавлении #

1. Считаем hash(key)
2. Получаем индекс
3. Если ячейка свободна — кладём туда
4. Если занята таким же ключом — обновляем значение
5. Если занята другим ключом — ищем другую позицию

Для set значение не хранится отдельно, там важен только сам элемент.

s = {"cat", "dog"}

Внутри это ближе к:

hash("cat") -> позиция
hash("dog") -> позиция

Если позиции совпали, set ищет другое место для одного из элементов.

Что происходит при удалении #

В hash-таблицах с открытой адресацией нельзя всегда просто очистить ячейку.

Почему:

A попал в индекс 3
B тоже хотел индекс 3, но из-за коллизии ушёл в индекс 4

Таблица:

3 -> A
4 -> B

Если удалить A и сделать ячейку 3 полностью пустой:

3 -> пусто
4 -> B

При поиске B таблица может прийти в индекс 3, увидеть пустоту и решить:

B нет в таблице

Хотя B лежит дальше.

Поэтому часто используется специальная метка, например:

deleted / dummy / tombstone

То есть ячейка считается удалённой, но поиск через неё не останавливается.

Зачем нужен resize / rehash #

Чем сильнее заполнена hash-таблица, тем больше коллизий.

Поэтому hash-таблицы обычно следят за коэффициентом заполнения:

load factor = количество элементов / размер таблицы

Когда элементов становится слишком много, таблица расширяется, и элементы перераспределяются по новому массиву.

В Java HashMap, например, при превышении порога load factor * capacity выполняется rehash, обычно с увеличением числа bucket примерно в 2 раза. Документация также указывает, что стандартный load factor 0.75 даёт компромисс между временем и расходом памяти. ( Документация Oracle)

В CPython для dict комментарии к исходному коду указывают, что load factor держится ниже 2/3, чтобы обычно находить нужный ключ с первой попытки. ( GitHub)

Коротко #

Коллизии разрешаются двумя основными подходами:

1. Метод цепочек
   В одной ячейке хранится список / дерево элементов.

2. Открытая адресация
   Все элементы лежат прямо в массиве, а при коллизии ищется другая ячейка.

Для Python важно запомнить:

dict / set в CPython используют открытую адресацию,
а не списки внутри bucket-ов.

Главная идея разрешения коллизий:

hash даёт стартовую позицию,
а если она занята другим ключом,
таблица по специальному правилу ищет следующую подходящую позицию.

4. Какие типы данных существуют в python? #

Типы данных Python #

• Неизменяемые (немутабельные, immutable) типы данных: числа (int, float), строки (str), булевые (bool), кортежи (tuple) и frozenset. Также - None, complex, bytes.
• Изменяемые (мутабельные, muttable) типы данных. К изменяемым относятся списки (list), множества (set) и словари (dict). Также байтовый массив bytearray.

Изменяемые типы данных могут быть изменены после их создания, а неизменяемые — нет.

None - экземпляр типа объекта NoneType, который используется для обозначения отсутствия значения

bool - булевы значения (True, False)

int - целые чисел, как положительныхе, так и отрицательные

float - числа, которые могут иметь десятичную часть (с плавающей точкой)

complex - комплексные числа

str - текстовая информация (строка, последовательность символов)

tuple - неизменяемые упорядоченные коллекции элементов (кортежи)

bytes - байтовые последовательности, которые используются для работы с бинарными файлами

frozenset - неизменяемый тип данных, представляющий неупорядоченную коллекцию уникальных элементов

list - изменяемые упорядоченные коллекции элементов (списки)

dict - ассоциативный массив, пары «ключ-значение», где каждый ключ является уникальным

set - неупорядоченная коллекция уникальных элементов (поддерживает операции над множествами - объединения, вхождения, исключения)

bytearray - массив заданных байтов

5. Зачем в Python есть mutable и immutable типы? Почему не сделать изменяемую строку? #

Зачем нужны mutable и immutable типы #

В Python каждый объект имеет identity, type и value. Изменяемость объекта определяется его типом: например, list и dict изменяемые, а int, str, tuple — неизменяемые.

Главная идея такая:

immutable object
значение после создания не меняется

mutable object
значение можно менять внутри того же объекта

Пример:

s = "abc"
s = s + "d"

Здесь строка "abc" не изменилась. Создалась новая строка "abcd", а переменная s стала ссылаться на неё.

lst = [1, 2, 3]
lst.append(4)

Здесь список изменился на месте. Объект остался тот же, но его содержимое стало другим.

Зачем нужны immutable-типы #

1. Безопасность от неожиданных изменений #

Immutable-объект нельзя случайно изменить через другую ссылку.

a = "hello"
b = a

b = b.upper()

print(a)  # hello
print(b)  # HELLO

Со списком иначе:

a = [1, 2, 3]
b = a

b.append(4)

print(a)  # [1, 2, 3, 4]

Потому что a и b ссылаются на один и тот же изменяемый объект.

2. Можно использовать как ключи dict и элементы set #

Чтобы объект можно было использовать как ключ словаря или элемент множества, его хеш должен оставаться стабильным. В документации Python указано, что hashable-объект имеет хеш, который не меняется в течение жизни объекта; это нужно для dict и set.

Поэтому строка может быть ключом:

users = {
    "admin": "root",
    "guest": "readonly",
}

А список не может:

d = {}

d[[1, 2, 3]] = "value"
# TypeError: unhashable type: 'list'

Если бы список можно было использовать как ключ, возникла бы проблема:

key = [1, 2, 3]
d[key] = "value"

key.append(4)

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

3. Удобно переиспользовать объекты #

Для immutable-объектов интерпретатор может безопасно переиспользовать один и тот же объект с одинаковым значением. В документации прямо указано, что для immutable-типов операции могут возвращать ссылку на уже существующий объект с тем же типом и значением, а для mutable-объектов так делать нельзя.

Упрощённо:

a = "hello"
b = "hello"

Так как строка неизменяемая, безопасно, чтобы a и b ссылались на один и тот же объект.

Для списков так нельзя:

a = []
b = []

Это должны быть два разных списка, иначе изменение a ломало бы b.

Зачем нужны mutable-типы #

Mutable-типы нужны там, где объект должен накапливать состояние:

items = []

items.append("apple")
items.append("banana")
items.append("orange")

Создавать новый список при каждом добавлении было бы неудобно и часто неэффективно.

Mutable-типы подходят для:

list  -> динамическая коллекция
dict  -> изменяемое отображение ключ -> значение
set   -> изменяемое множество
bytearray -> изменяемая последовательность байтов

Встроенные коллекции Python специально поддерживают операции изменения на месте; документация отдельно отмечает, что некоторые коллекции изменяемые, а методы, которые добавляют, удаляют или переставляют элементы на месте, обычно возвращают None, а не сам объект.

Почему не сделать изменяемую строку #

Потому что строка в Python — это не просто «массив символов». Это базовый тип для текста: имена, ключи словарей, пути, атрибуты, сообщения, JSON-ключи, SQL-фрагменты, URL и так далее. Документация определяет str как неизменяемую последовательность Unicode code points.

Если бы строка была mutable, появились бы проблемы.

1. Строки нельзя было бы безопасно использовать как ключи dict #

Сейчас это нормально:

cache = {
    "user:42": "cached data"
}

Если бы строку можно было изменить на месте:

key = "user:42"
cache[key] = "cached data"

# гипотетически:
key.change_to("user:99")

Тогда ключ внутри словаря фактически изменился бы после вставки. Это ломает принцип работы hash-таблицы.

2. Любая передача строки стала бы опаснее #

Сейчас:

def log(message: str):
    print(message)

text = "error"
log(text)

Можно быть уверенным, что log() не изменит исходную строку.

С mutable-строками пришлось бы постоянно думать:

А функция изменила мою строку?
А строка изменилась в другом месте?
Нужно ли делать копию перед передачей?

Это усложнило бы код.

3. Большинство операций со строками логически создают новый текст #

s = "hello"
s2 = s.replace("h", "H")

print(s)   # hello
print(s2)  # Hello

replace(), upper(), strip(), split() и похожие операции не портят исходный текст. Это предсказуемое поведение.

А как тогда эффективно собирать строку? #

Для большого количества склеек обычно используют join():

parts = []

for word in ["hello", "world"]:
    parts.append(word)

result = " ".join(parts)
print(result)  # hello world

То есть изменяемым буфером выступает list, а итоговая строка создаётся один раз.

Для бинарных данных есть bytearray — это изменяемый аналог bytes, он поддерживает mutable sequence operations.

data = bytearray(b"abc")
data[0] = ord("A")

print(data)  # bytearray(b'Abc')

Но bytearray — это байты, не полноценный Unicode-текст как str.

Итог #

Mutable и immutable типы нужны для разных задач:

immutable:
- значение стабильно
- безопасно передавать
- можно хешировать
- удобно использовать как ключ dict / элемент set
- меньше неожиданных побочных эффектов

mutable:
- можно менять на месте
- удобно накапливать данные
- эффективно для коллекций и буферов

Строка в Python immutable, потому что текст чаще нужен как стабильное значение, а не как изменяемый контейнер символов. Для изменения текста обычно создаётся новая строка, а для эффективной сборки используют list + ''.join(...).

6. Чем отличается списки от кортежа? | list vs tuple #

Отличие списка от кортежа #

Список и кортеж в Python различаются главным образом изменяемостью: список является изменяемым (может быть изменен после создания), тогда как кортеж является неизменяемым (не может быть изменен после создания). Это означает, что элементы списка можно добавлять, удалять или изменять, а элементы кортежа после создания остаются неизменными.

Под список выделяется определенное место в памяти, когда оно заканчивается (после добавления новых элементов) выделяется новое место памяти большего размера, в которое переносится весь список, для кортежа выделяется фиксированное место в памяти и никогда не меняется, так как кортеж неизменяем(поэтому работа с ним быстрее)

Семантическое различие

• Список обычно содержит однородные данные (элементы одного типа и назначения).
• Кортеж часто содержит разнородные данные, где позиция элемента имеет смысловое значение.

Аннотации типов

Кортежи можно аннотировать как записи с фиксированной структурой, где указывается тип для каждой позиции. Это полезно для представления структур данных с определенной схемой, например, информация о человеке (имя, возраст, активен) или координаты точки (x, y). tuple[int, str, bool] - кортеж из 3 элементов типов int, str, bool.

Области применения

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

7. Чем отличается списки от словаря? | list vs dict #

Главное отличие #

list — это упорядоченная коллекция значений.

dict — это коллекция пар ключ: значение.

Официальная документация Python относит list к последовательностям, а dict — к отображениям, то есть структурам, где значения ищутся по ключу. ( Python documentation)

Пример list #

users = ["Alice", "Bob", "John"]

print(users[0])  # Alice
print(users[1])  # Bob

У списка элементы лежат по индексам:

index:   0        1       2
value: "Alice"  "Bob"  "John"

То есть доступ идёт по номеру позиции.

Пример dict #

user = {
    "name": "Alice",
    "age": 20,
    "city": "Baku"
}

print(user["name"])  # Alice
print(user["age"])   # 20

У словаря данные лежат по ключам:

key      -> value
"name"   -> "Alice"
"age"    -> 20
"city"   -> "Baku"

То есть доступ идёт не по позиции, а по имени ключа. В документации Python словари описываются как структуры, индексируемые ключами, а не диапазоном чисел, как последовательности.

Сравнение #

Когда использовать list #

Используй list, когда важен порядок и данные однотипные:

numbers = [10, 20, 30, 40]
products = ["milk", "bread", "cheese"]

Например:

for product in products:
    print(product)

list хорошо подходит для:

списка товаров
списка пользователей
списка чисел
очереди элементов
набора однотипных объектов

Когда использовать dict #

Используй dict, когда нужно хранить данные с понятными именами:

user = {
    "id": 1,
    "username": "alfob",
    "email": "test@example.com"
}

Например:

print(user["username"])

dict хорошо подходит для:

данных пользователя
настроек приложения
JSON-структур
ответов API
кэша
быстрого поиска по id/name/key

Важное отличие по скорости #

У списка доступ по индексу быстрый:

items[0]

Но поиск конкретного значения обычно требует прохода по элементам:

"name" in users

У словаря доступ по ключу в среднем быстрый:

user["name"]

Python Wiki указывает, что для dict получение элемента, установка элемента и проверка ключа в среднем работают за O(1), если хеш-функция распределяет ключи нормально.

Пример разницы на практике #

Плохо через list:

users = [
    ["Alice", 20],
    ["Bob", 25],
    ["John", 30]
]

print(users[0][0])  # Alice

Работает, но плохо читается: непонятно, что значит [0][0].

Лучше через dict:

user = {
    "name": "Alice",
    "age": 20
}

print(user["name"])  # Alice

Так код читается понятнее.

Можно комбинировать #

Часто используют list из dict:

users = [
    {"id": 1, "name": "Alice"},
    {"id": 2, "name": "Bob"},
    {"id": 3, "name": "John"},
]

Это означает:

список пользователей,
где каждый пользователь описан словарём

Так обычно выглядят данные из API или базы данных.

Коротко #

list = когда важен порядок
dict = когда важны имена/ключи

Пример:

# list
skills = ["Python", "Django", "FastAPI"]

# dict
user = {
    "name": "Alfob",
    "skills": ["Python", "Django", "FastAPI"]
}

list отвечает на вопрос:

Какие элементы идут друг за другом?

dict отвечает на вопрос:

Какое значение лежит по этому ключу?

8. Возможен ли доступ к элементу множества (set) по позиции (индексу)? #

Нет, доступ по индексу к set невозможен #

У множества set нет индексов.

items = {"apple", "banana", "orange"}

print(items[0])

Будет ошибка:

TypeError: 'set' object is not subscriptable

Почему так #

set — это не последовательность, а множество уникальных элементов.

У него нет гарантированного позиционного порядка, поэтому Python не позволяет обращаться так:

items[0]
items[1]
items[2]

В отличие от списка:

items = ["apple", "banana", "orange"]

print(items[0])  # apple

Как получить элементы из set #

Через перебор:

items = {"apple", "banana", "orange"}

for item in items:
    print(item)

Но важно: порядок обхода множества не стоит использовать как стабильный порядок.

Если нужен доступ по индексу #

Можно преобразовать set в list:

items = {"apple", "banana", "orange"}

items_list = list(items)

print(items_list[0])

Но порядок после преобразования не гарантирует исходную «логическую» последовательность, потому что у set её изначально нет.

Если нужен стабильный порядок, лучше сразу использовать list:

items = ["apple", "banana", "orange"]

print(items[0])

Итог #

list  -> доступ по индексу есть
dict  -> доступ по ключу
set   -> доступа по индексу нет

set используют не для позиционного доступа, а для:

unique_ids = {1, 2, 3}

print(2 in unique_ids)  # True

То есть для хранения уникальных элементов и быстрой проверки наличия элемента.

9. Как реализованы список (list) и кортеж (tuple) на уровне внутренней структуры данных? #

Главное #

В CPython:

list  -> динамический массив ссылок на PyObject
tuple -> фиксированный массив ссылок на PyObject

То есть и list, и tuple не хранят сами значения напрямую. Они хранят ссылки на Python-объекты.

items = [10, "abc", True]

Упрощённо внутри:

list
 ├─ ob_size = 3
 ├─ allocated = например 4
 └─ ob_item -> [ ptr -> int(10), ptr -> str("abc"), ptr -> bool(True) ]

Как устроен list #

В CPython список представлен структурой PyListObject.

Упрощённо:

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

В исходниках CPython указано, что ob_item — это вектор указателей на элементы списка, а list[0] соответствует ob_item[0]. Также там есть поле allocated, которое показывает, сколько ячеек реально выделено под элементы. Количество фактически используемых элементов хранится в ob_size. ( GitHub)

То есть список хранит:

ob_size    -> текущая длина списка
allocated  -> сколько места выделено с запасом
ob_item    -> указатель на массив ссылок на элементы

Пример:

lst = [1, 2, 3]

Внутренне примерно:

PyListObject
 ├─ ob_size = 3
 ├─ allocated = 4 или больше
 └─ ob_item
     ├─ [0] -> PyLongObject(1)
     ├─ [1] -> PyLongObject(2)
     ├─ [2] -> PyLongObject(3)
     └─ [3] -> свободная ячейка

Почему list.append() обычно быстрый #

Список выделяет память с запасом.

Когда ты делаешь:

lst.append(4)

Python часто не обязан сразу перевыделять память. Он просто кладёт ссылку в уже свободную ячейку.

В list_resize() в CPython прямо указано, что список делает over-allocation — выделяет немного больше памяти, чем нужно сейчас, чтобы длинная серия append() работала амортизированно за линейное время. Там же приведён примерный паттерн роста: 0, 4, 8, 16, 24, 32, 40, 52... ( GitHub)

Поэтому:

lst.append(x)

обычно работает за:

O(1) amortized

Но иногда списоку всё-таки приходится перевыделять память и копировать ссылки в новый массив.

Как работает доступ по индексу в list #

lst[2]

Так как внутри есть массив ссылок, Python может сразу перейти к нужной ячейке:

ob_item[2]

Поэтому доступ по индексу быстрый:

O(1)

Официальная C API документация для PyList_GetItem тоже описывает получение объекта по позиции index; при выходе за границы возвращается ошибка IndexError.

Как устроен tuple #

Кортеж в CPython представлен структурой PyTupleObject.

В актуальной ветке CPython она выглядит примерно так:

typedef struct {
    PyObject_VAR_HEAD
    Py_hash_t ob_hash;
    PyObject *ob_item[1];
} PyTupleObject;

В исходниках указано, что ob_item содержит место для ob_size элементов. Также в актуальной структуре есть поле ob_hash для кэшированного хеша. ( GitHub)

Упрощённо:

tuple
 ├─ ob_size = 3
 ├─ ob_hash = cached hash
 └─ ob_item -> [ ptr, ptr, ptr ]

Пример:

tpl = (1, 2, 3)

Внутренне примерно:

PyTupleObject
 ├─ ob_size = 3
 ├─ ob_hash = -1 или уже посчитанный hash
 └─ ob_item
     ├─ [0] -> PyLongObject(1)
     ├─ [1] -> PyLongObject(2)
     └─ [2] -> PyLongObject(3)

Главное отличие tuple от list внутри #

У tuple нет поля allocated.

У списка есть:

ob_size
allocated
ob_item

У кортежа в целом:

ob_size
ob_item

Потому что кортеж фиксированного размера.

Список может расти:

lst = [1, 2]
lst.append(3)

Кортеж не может:

tpl = (1, 2)
tpl.append(3)  # AttributeError

Когда ты пишешь:

tpl = tpl + (3,)

создаётся новый кортеж, а старый не расширяется.

Почему tuple обычно компактнее #

tuple не нужен запас памяти под будущие элементы.

Список хранит дополнительную ёмкость:

len(list) <= allocated

А кортеж создаётся сразу нужного размера:

len(tuple) == количество ячеек под элементы

Поэтому кортеж обычно немного экономнее по памяти, особенно если коллекция неизменяемая.

Важный момент про неизменяемость #

tuple неизменяемый не потому, что его элементы физически невозможно трогать на уровне C, а потому что Python API не даёт менять ссылки внутри кортежа после создания.

tpl = (1, 2, 3)

tpl[0] = 100

Ошибка:

TypeError: 'tuple' object does not support item assignment

Но если внутри кортежа лежит изменяемый объект, сам этот объект менять можно:

tpl = ([1, 2], "abc")

tpl[0].append(3)

print(tpl)  # ([1, 2, 3], 'abc')

Кортеж не поменял ссылку tpl[0]. Она как указывала на тот же список, так и указывает. Изменился сам список внутри.

Сравнение на уровне структуры #

Почему это не linked list #

Python list — это не связный список.

Связный список выглядел бы так:

node -> node -> node -> node

А Python list ближе к массиву:

[ ptr ][ ptr ][ ptr ][ ptr ]

Поэтому:

lst[1000]

работает быстро, потому что Python не идёт от первого элемента до тысячного. Он сразу вычисляет адрес нужной ячейки массива.

Но вставка в середину дорогая:

lst.insert(0, x)

Потому что элементы нужно сдвигать:

[1][2][3]
 insert 0
[x][1][2][3]

Это уже:

O(n)

Общая модель объектов #

И list, и tuple — это объекты переменной длины. В CPython для таких объектов используется PyObject_VAR_HEAD, который расширяется до PyVarObject ob_base; эта структура содержит размер переменной части объекта.

Упрощённо:

PyObject
 ├─ refcount
 └─ type pointer

PyVarObject
 ├─ PyObject header
 └─ ob_size

Для list:

PyListObject
 ├─ PyVarObject header
 ├─ ob_item
 └─ allocated

Для tuple:

PyTupleObject
 ├─ PyVarObject header
 ├─ ob_hash
 └─ ob_item

Итог #

list:
динамический массив ссылок с запасом памяти

tuple:
фиксированный массив ссылок без возможности менять размер

Практически:

# list — когда надо менять
users = []
users.append("Alice")
users.append("Bob")

# tuple — когда набор фиксированный
point = (10, 20)
rgb = (255, 128, 0)

list оптимизирован под изменение коллекции.

tuple оптимизирован под фиксированную, компактную и неизменяемую последовательность.

10. Как происходит выделение памяти для списка и его внутреннего хранилища? #

Коротко #

В CPython список состоит из двух частей:

PyListObject
 ├─ служебная часть объекта
 ├─ ob_size     -> текущая длина списка
 ├─ allocated   -> сколько ячеек выделено во внутреннем массиве
 └─ ob_item     -> указатель на массив ссылок PyObject*

То есть память выделяется отдельно:

1. Под сам объект списка
2. Под внутренний массив ссылок на элементы

В исходниках CPython list описан как PyListObject, где ob_item — это вектор указателей на элементы, а allocated показывает количество выделенных ячеек. Там же указано, что len(list) == ob_size, а ob_item == NULL означает пустой список с ob_size == allocated == 0. ( GitHub)

Важно: список хранит не сами объекты #

Например:

lst = [10, "abc", True]

Внутри список хранит не сами 10, "abc" и True, а ссылки на объекты:

lst
 ├─ ob_size = 3
 ├─ allocated = например 4
 └─ ob_item
     ├─ [0] -> PyLongObject(10)
     ├─ [1] -> PyUnicodeObject("abc")
     ├─ [2] -> PyBoolObject(True)
     └─ [3] -> свободная ячейка

Поэтому при расширении списка обычно копируются не сами Python-объекты, а указатели на них.

Создание пустого списка #

lst = []

Упрощённо:

ob_size = 0
allocated = 0
ob_item = NULL

То есть под внутреннее хранилище элементов память ещё не выделяется.

В PyList_New() в CPython при размере size <= 0 поле ob_item устанавливается в NULL, затем выставляются размер и allocated. ( GitHub)

Создание списка известного размера #

Например, на уровне C API:

PyList_New(3)

CPython создаёт объект списка и выделяет массив под 3 указателя:

ob_size = 3
allocated = 3
ob_item -> [NULL, NULL, NULL]

Документация Python C API прямо указывает: если len > 0, элементы нового списка сначала установлены в NULL, и такой список нельзя показывать Python-коду до заполнения реальными объектами.

На Python-уровне ты обычно этого не видишь:

lst = [1, 2, 3]

Потому что интерпретатор создаёт список и сразу заполняет его ссылками на элементы.

Что происходит при append #

lst = []
lst.append(10)

Сначала список пустой:

ob_size = 0
allocated = 0
ob_item = NULL

После первого append нужно место под элемент. CPython вызывает внутреннюю функцию изменения размера списка — list_resize().

Она выделяет не ровно 1 ячейку, а с запасом:

ob_size = 1
allocated = 4
ob_item -> [ptr, free, free, free]

То есть список заранее получает несколько свободных ячеек, чтобы следующие append() не требовали нового выделения памяти каждый раз.

Почему список выделяет память с запасом #

Если бы список каждый раз выделял память ровно под новый размер, то такой код был бы дорогим:

lst = []

for i in range(1000):
    lst.append(i)

Почти каждый append требовал бы:

выделить новый массив
скопировать старые ссылки
освободить старый массив

Поэтому CPython использует over-allocation — выделение памяти с запасом.

В list_resize() прямо указано, что список выделяет память пропорционально текущему размеру, чтобы длинная последовательность append() имела амортизированное линейное поведение. Там же указан примерный паттерн роста: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76.... ( GitHub)

Формула роста #

В актуальных исходниках CPython используется такая формула:

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

То есть новый размер внутреннего массива примерно:

newsize + newsize / 8 + небольшой запас

И потом результат округляется до кратности 4. Эта логика находится в list_resize(). ( GitHub)

Примерно:

len:        0  1  5  9   17  25  33
allocated: 0  4  8  16  24  32  40

Точные значения могут зависеть от конкретной версии CPython, но принцип такой:

len(list) <= allocated

Что происходит, когда свободное место уже есть #

Допустим:

ob_size = 3
allocated = 4

И ты делаешь:

lst.append(40)

Новая длина — 4. Место уже есть.

ob_size = 4
allocated = 4

Новый массив выделять не нужно. CPython просто кладёт ссылку в свободную ячейку.

Что происходит, когда места не хватает #

Допустим:

ob_size = 4
allocated = 4

И ты делаешь:

lst.append(50)

Новая длина — 5, но свободных ячеек нет.

Тогда происходит примерно следующее:

1. CPython считает новую ёмкость
2. Вызывает PyMem_Realloc для внутреннего массива ob_item
3. Старые ссылки переносятся в новое хранилище
4. ob_item начинает указывать на новый массив
5. allocated обновляется
6. новый элемент записывается в свободную ячейку

В обычной сборке CPython list_resize() использует PyMem_Realloc() для изменения размера внутреннего массива ob_item, после чего обновляет self->ob_item, ob_size и allocated. ( GitHub)

Важный момент про копирование #

При расширении списка не копируются сами объекты:

lst = ["abc", "def"]

Не копируются строки "abc" и "def".

Копируется массив ссылок:

старый ob_item:
[ptr1][ptr2]

новый ob_item:
[ptr1][ptr2][free][free]

Объекты остаются там же в памяти. Меняется только внутреннее хранилище списка.

Что происходит при удалении элементов #

Например:

lst.pop()

Список уменьшает ob_size.

Но CPython не обязан сразу отдавать лишнюю память системе. Если после уменьшения список всё ещё занимает хотя бы половину выделенной ёмкости, list_resize() не делает реальное realloc, а просто меняет размер. В исходниках это проверяется условием: если allocated >= newsize и newsize >= allocated >> 1, то меняется только ob_size. ( GitHub)

То есть было:

ob_size = 10
allocated = 16

После удаления может стать:

ob_size = 9
allocated = 16

Память под 16 ячеек пока остаётся.

Когда список может уменьшить внутреннее хранилище #

Если список стал сильно меньше, CPython может перевыделить внутренний массив уже под меньшую ёмкость.

Упрощённо:

если newsize >= allocated / 2:
    не перевыделять память

если newsize < allocated / 2:
    можно уменьшить хранилище

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

Общая схема append #

lst.append(x)

1. newsize = ob_size + 1

2. Если allocated хватает:
      просто записать x в ob_item[ob_size]
      увеличить ob_size

3. Если allocated не хватает:
      посчитать новую ёмкость
      перевыделить ob_item
      обновить allocated
      записать x
      увеличить ob_size

Почему append считается быстрым #

Один конкретный append иногда может быть дорогим, потому что вызывает перевыделение памяти.

Но большинство append() просто кладут элемент в уже выделенную свободную ячейку.

Поэтому:

append -> O(1) amortized

То есть в среднем на длинной серии добавлений операция работает как константная.

Итог #

list в CPython — это динамический массив ссылок

Он хранит:

ob_size    -> сколько элементов реально лежит в списке
allocated  -> сколько ячеек выделено во внутреннем массиве
ob_item    -> указатель на массив PyObject*

Главная идея:

len(list) может быть меньше allocated

Именно поэтому список может эффективно расти:

lst = []

lst.append(1)
lst.append(2)
lst.append(3)

CPython не выделяет память заново на каждый append, а держит запас свободных ячеек внутри списка.

11. Как ведут себя элементы списка в момент увеличения его внутренней ёмкости? #

Когда список увеличивает внутреннюю ёмкость, его элементы как Python-объекты не перемещаются и не копируются.

Копируется или перемещается только внутренний массив ссылок:

старое хранилище ob_item:

[ ptr1 ][ ptr2 ][ ptr3 ][ ptr4 ]

новое хранилище ob_item:

[ ptr1 ][ ptr2 ][ ptr3 ][ ptr4 ][ free ][ free ][ free ][ free ]

ptr1, ptr2, ptr3 — это ссылки на реальные Python-объекты. Сами объекты остаются на своих местах в памяти.

Что именно происходит #

Допустим:

lst = [a, b, c, d]
lst.append(e)

Если внутренняя ёмкость уже заполнена:

ob_size = 4
allocated = 4

то при append(e) CPython вызывает list_resize().

Упрощённо происходит так:

1. Считается новая ёмкость, например 8
2. Выделяется/перевыделяется массив ob_item
3. Старые указатели копируются в новое хранилище
4. ob_item начинает указывать на новый массив
5. allocated обновляется
6. Новый элемент записывается в свободную ячейку

В исходниках CPython прямо указано, что ob_item — это вектор указателей на элементы списка, а allocated показывает, сколько ячеек выделено под эти указатели.

Объекты не копируются #

Например:

x = {"name": "Alice"}
y = {"name": "Bob"}

lst = [x, y]
lst.append({"name": "John"})

При расширении списка не создаются копии x и y.

Было:

lst.ob_item
 ├─ [0] -> x
 └─ [1] -> y

После расширения:

lst.ob_item
 ├─ [0] -> x
 ├─ [1] -> y
 ├─ [2] -> new_object
 └─ [3] -> free

Сами объекты x и y остались теми же.

Может измениться адрес внутреннего массива #

Важный момент:

id(lst) не меняется
id(lst[0]) не меняется
адрес внутреннего ob_item может измениться

То есть сам объект списка остаётся тем же самым, но его внутреннее хранилище ссылок может быть перенесено в другое место памяти.

В комментарии к list_resize() в CPython прямо сказано, что self->ob_item может измениться. ( GitHub)

Почему id(lst) не меняется #

lst = [1, 2, 3]

before = id(lst)

for i in range(1000):
    lst.append(i)

after = id(lst)

print(before == after)  # True

Объект списка тот же.

Меняется не сам PyListObject, а его поле ob_item, то есть указатель на внутренний массив ссылок:

PyListObject остался тот же:

lst
 ├─ ob_size
 ├─ allocated
 └─ ob_item -> новый массив ссылок

Почему id(lst[0]) тоже не меняется #

obj = {"value": 123}

lst = [obj]

before = id(lst[0])

for i in range(1000):
    lst.append(i)

after = id(lst[0])

print(before == after)  # True

Потому что при расширении списка переносится не объект obj, а только ссылка на него.

Упрощённо:

до resize:

ob_item[0] -> obj

после resize:

new_ob_item[0] -> obj

Объект obj тот же.

Что происходит с порядком элементов #

Порядок сохраняется.

lst = [10, 20, 30, 40]
lst.append(50)

После расширения:

[10, 20, 30, 40, 50]

Старые ссылки переносятся в тот же порядок:

old_ob_item[0] -> new_ob_item[0]
old_ob_item[1] -> new_ob_item[1]
old_ob_item[2] -> new_ob_item[2]
old_ob_item[3] -> new_ob_item[3]

Что происходит с reference count #

Для старых элементов при обычном расширении списка их счётчик ссылок не обязан меняться.

Почему:

старый массив ссылок исчезает
новый массив ссылок содержит те же самые ссылки

Логически количество ссылок от списка на каждый старый объект остаётся тем же: одна ссылка была, одна ссылка осталась.

А вот для нового элемента, который добавляется через append, список начинает хранить новую ссылку на этот объект. В реализации PyList_Append используется внутренняя логика добавления элемента после list_resize(). В коде _PyList_AppendTakeRefListResize() сначала вызывается list_resize(self, len + 1), затем новый элемент записывается в self->ob_item[len].

Почему операция может быть дорогой #

Когда ёмкости хватает:

append -> просто записать ссылку в свободную ячейку

Это быстро.

Когда ёмкости не хватает:

append -> resize -> перевыделение памяти -> перенос старых ссылок -> запись нового элемента

Это дороже, потому что нужно обработать уже существующие ссылки.

Поэтому один конкретный append() иногда может быть O(n), если произошёл resize.

Но серия append() в среднем эффективна, потому что список заранее выделяет память с запасом. В list_resize() указано, что CPython делает over-allocation, чтобы длинная последовательность append() имела амортизированное линейное поведение; там же приведён паттерн роста 0, 4, 8, 16, 24, 32, 40, 52....

Итог #

При увеличении внутренней ёмкости списка:

1. Сами элементы-объекты не копируются
2. Копируются только ссылки на элементы
3. id(lst) остаётся тем же
4. id старых элементов остаётся тем же
5. Адрес внутреннего массива ob_item может измениться
6. Порядок элементов сохраняется
7. Операция resize может стоить O(n)

Главная формула:

list хранит не объекты, а массив ссылок на объекты

Поэтому расширение списка — это перенос массива указателей, а не перенос самих Python-объектов.

12. Массив vs список #

Главное #

В контексте Python важно понимать:

Python list — это не классический linked list
Python list — это динамический массив ссылок

То есть Python-список по внутреннему устройству ближе к массиву, чем к связному списку. В CPython у list есть ob_item — массив указателей на элементы, ob_size — текущая длина, и allocated — выделенная ёмкость.

Классический массив #

Массив обычно означает структуру, где элементы одного типа лежат в памяти подряд:

array of int:

[ 10 ][ 20 ][ 30 ][ 40 ]

Условно:

int arr[4] = {10, 20, 30, 40};

Особенности:

1. Элементы обычно одного типа
2. Память расположена компактно
3. Быстрый доступ по индексу: O(1)
4. Размер часто фиксирован или меняется дорого
5. Хорошо подходит для чисел и плотных данных

Python list #

Python list хранит не сами значения, а ссылки на Python-объекты:

lst = [10, "abc", True]

Внутри примерно:

list
 ├─ ob_size = 3
 ├─ allocated = 4
 └─ ob_item
     ├─ [0] -> PyObject int(10)
     ├─ [1] -> PyObject str("abc")
     ├─ [2] -> PyObject bool(True)
     └─ [3] -> free

Поэтому в одном списке можно хранить разные типы:

lst = [1, "hello", True, None]

Официальная документация Python описывает list как изменяемую последовательность, а элементы списка могут быть произвольными Python-объектами.

Главное различие по памяти #

Классический массив чисел:

[ 1 ][ 2 ][ 3 ][ 4 ]

Python list:

[ ptr ][ ptr ][ ptr ][ ptr ]
   ↓     ↓     ↓     ↓
  int   int   int   int

То есть list хранит массив ссылок, а не плотный массив самих чисел.

Из-за этого list гибче, но обычно требует больше памяти.

array.array в Python #

В Python есть отдельный модуль array.

from array import array

nums = array("i", [1, 2, 3, 4])

Это уже ближе к классическому массиву: элементы одного типа и хранятся компактнее. Документация Python прямо говорит, что array компактно хранит базовые значения — символы, целые числа и числа с плавающей точкой; тип задаётся при создании через type code.

Пример:

from array import array

nums = array("i", [1, 2, 3])

nums.append(4)

print(nums[0])  # 1

Но так нельзя:

from array import array

nums = array("i", [1, 2, 3])

nums.append("hello")  # TypeError

Потому что array("i") хранит целые числа, а не произвольные объекты.

Сравнение #

Почему list гибче #

Список может хранить всё подряд:

items = [
    1,
    "text",
    {"name": "Alice"},
    [10, 20],
    None,
]

Потому что внутри лежат ссылки:

[ ptr ][ ptr ][ ptr ][ ptr ][ ptr ]

А массив обычно рассчитан на один конкретный тип:

array of int:
[ int ][ int ][ int ][ int ]

Почему массив может быть эффективнее #

Если нужно хранить миллион чисел, array.array или numpy.ndarray обычно лучше, чем list.

Например:

from array import array

nums = array("i", range(1_000_000))

Так данные будут храниться компактнее, чем в обычном списке:

nums = list(range(1_000_000))

Потому что список хранит ссылки на объекты int, а array.array хранит сами C-значения заданного типа. Документация Python описывает array как более компактный вариант для базовых числовых значений.

Важный момент #

В Python слово «список» может сбивать с толку.

В структурах данных есть:

array       -> массив
linked list -> связный список
list        -> абстрактная последовательность

Но Python list — это не linked list.

Python list — это:

динамический массив ссылок

Именно поэтому:

lst = [10, 20, 30]

print(lst[1])  # 20

доступ по индексу быстрый.

Если бы это был связный список, для доступа к lst[1] пришлось бы идти от первого узла ко второму.

Когда использовать list #

Используй обычный list, когда нужна универсальная коллекция:

users = ["Alice", "Bob", "John"]
tasks = [{"id": 1}, {"id": 2}]
values = [1, "abc", True]

Подходит для:

обычных списков объектов
результатов запросов
JSON-подобных структур
очередей небольшого размера
динамического добавления элементов

Когда использовать массив #

Используй массив, когда данные однотипные и важна компактность:

from array import array

temperatures = array("f", [36.6, 37.1, 36.9])
ids = array("i", [1, 2, 3, 4])

Подходит для:

больших числовых наборов
бинарных данных
работы с C API
экономии памяти
численных вычислений

Для серьёзных численных вычислений обычно используют numpy.ndarray, потому что NumPy даёт многомерные однородные массивы и эффективные операции над ними.

Итог #

array:
компактное хранилище однотипных значений

list:
динамический массив ссылок на любые Python-объекты

Практическое правило:

Нужна обычная коллекция объектов -> list
Нужны миллионы чисел и экономия памяти -> array.array или NumPy

В Python почти всегда начинают с list, а к массивам переходят тогда, когда есть конкретная причина: память, скорость численных операций или работа с бинарными данными.

13. Почему при создании списка под его внутреннее хранилище выделяется массив фиксированной длины и определённого типа? #

Суть #

Потому что внутреннее хранилище list в CPython — это обычный C-массив указателей:

PyObject **ob_item;

То есть:

ob_item -> массив элементов типа PyObject*

В исходниках CPython ob_item описан как вектор указателей на элементы списка: list[0] соответствует ob_item[0]. Поле allocated хранит количество выделенных ячеек во внутреннем массиве. ( GitHub)

Почему массив фиксированной длины #

Потому что в C массив — это непрерывный участок памяти фиксированного размера.

Например, если CPython выделил место под 8 ссылок:

allocated = 8

[ ptr ][ ptr ][ ptr ][ ptr ][ free ][ free ][ free ][ free ]

Этот конкретный участок памяти имеет ёмкость 8 ячеек. Нельзя просто «дописать девятую ячейку рядом», потому что за этим участком памяти может находиться что-то другое.

Поэтому при нехватке места список делает resize:

старое хранилище:
[ ptr ][ ptr ][ ptr ][ ptr ]

новое хранилище:
[ ptr ][ ptr ][ ptr ][ ptr ][ free ][ free ][ free ][ free ]

В list_resize() CPython проверяет, хватает ли уже выделенной ёмкости. Если хватает, он просто меняет размер списка. Если не хватает, происходит перевыделение внутреннего массива. ( GitHub)

Почему массив определённого типа #

Потому что C-массив должен знать размер каждой ячейки.

Для быстрого доступа по индексу нужно уметь вычислить адрес:

адрес элемента = адрес начала массива + индекс * размер_ячейки

Например:

ob_item[3]

работает быстро, потому что каждая ячейка имеет одинаковый размер — размер указателя PyObject*.

Именно поэтому внутренний массив списка имеет один C-тип:

PyObject*

Но это не значит, что Python-список хранит элементы одного Python-типа.

Почему тогда в list можно хранить разные типы #

Потому что список хранит не сами объекты, а ссылки на объекты.

lst = [1, "abc", True, None]

Внутри:

ob_item
 ├─ [0] -> PyLongObject(1)
 ├─ [1] -> PyUnicodeObject("abc")
 ├─ [2] -> PyBoolObject(True)
 └─ [3] -> Py_None

Все ячейки внутреннего массива имеют один C-тип:

PyObject*

А сами объекты могут быть разными:

int
str
bool
NoneType
dict
list
custom class

Документация Python прямо указывает, что элементы списка — произвольные Python-объекты.

Зачем именно так сделали #

Главная причина — быстрый доступ по индексу.

lst[5]

CPython может сразу взять:

ob_item[5]

Без прохода по предыдущим элементам.

Если бы список был связанным списком:

node -> node -> node -> node

для доступа к элементу по индексу пришлось бы идти от узла к узлу.

А у Python list:

[ ptr ][ ptr ][ ptr ][ ptr ][ ptr ]

поэтому доступ по индексу быстрый.

Почему не выделять память под каждый элемент отдельно #

Потому что тогда список потерял бы преимущества массива.

Плохая схема:

list
 ├─ node -> object
 ├─ node -> object
 ├─ node -> object
 └─ node -> object

Минусы:

больше памяти на служебные структуры
хуже кэш CPU
медленнее доступ по индексу
сложнее перемещаться по элементам

Схема CPython:

list
 └─ ob_item -> [ ptr ][ ptr ][ ptr ][ ptr ]

Она компактнее для самих ссылок и быстрее для индексного доступа.

Почему не хранить сами объекты подряд #

Например, почему не так:

[ int ][ str ][ bool ][ dict ]

Потому что Python-объекты имеют разный размер и разную внутреннюю структуру.

int, str, dict, list — это разные C-структуры. Их нельзя удобно положить в один простой массив фиксированных ячеек.

Поэтому используется общий уровень абстракции:

любой Python-объект -> PyObject*

То есть список хранит одинаковые по размеру указатели, а не разные по размеру объекты.

Почему ёмкость не равна длине #

У списка есть:

ob_size    -> текущая длина
allocated  -> выделенная ёмкость

Например:

ob_size = 5
allocated = 8

Это значит:

в списке 5 элементов,
но во внутреннем массиве есть место под 8 ссылок

Так сделано, чтобы append() не перевыделял память каждый раз.

В list_resize() CPython использует over-allocation — выделение памяти с запасом. В комментарии к исходникам указано, что это нужно для амортизированного линейного поведения при длинной серии append().

Пример #

lst = []

Пустой список:

ob_size = 0
allocated = 0
ob_item = NULL

Добавляем первый элемент:

lst.append("A")

CPython выделяет внутренний массив с запасом:

ob_size = 1
allocated = 4

[ ptr ][ free ][ free ][ free ]

Добавляем ещё:

lst.append("B")
lst.append("C")
lst.append("D")

Пока хватает старой ёмкости:

ob_size = 4
allocated = 4

[ ptr ][ ptr ][ ptr ][ ptr ]

Добавляем пятый элемент:

lst.append("E")

Нужно новое хранилище:

ob_size = 5
allocated = 8

[ ptr ][ ptr ][ ptr ][ ptr ][ ptr ][ free ][ free ][ free ]

Итог #

Внутреннее хранилище списка — это массив фиксированной длины и определённого типа, потому что:

1. C-массив требует заранее выделенного непрерывного участка памяти
2. Все ячейки массива должны иметь одинаковый размер
3. Тип PyObject* позволяет хранить ссылки на любые Python-объекты
4. Фиксированная ёмкость даёт быстрый доступ по индексу
5. При нехватке места список создаёт/перевыделяет массив большей ёмкости
6. Запас allocated нужен, чтобы append() не делал resize каждый раз

Главная мысль:

Python list динамический снаружи,
но его внутреннее хранилище — фиксированный C-массив ссылок на текущую ёмкость.

14. В какой структуре данных поиск выполняется эффективнее — в списке или во множестве? #

Коротко #

Поиск выполняется эффективнее во множестве set, а не в списке list.

list -> поиск O(n)
set  -> поиск O(1) в среднем

Почему в list поиск медленнее #

Список хранит элементы последовательно:

items = [10, 20, 30, 40, 50]

print(40 in items)  # True

Чтобы найти 40, Python проверяет элементы по очереди:

10 -> не то
20 -> не то
30 -> не то
40 -> найдено

В худшем случае нужно пройти весь список:

[10][20][30][40][50][60][70]
                       ↑
                    искомый элемент

Поэтому поиск в списке:

O(n)

Чем больше список, тем дольше поиск.

Почему в set поиск быстрее #

Множество реализовано через хеш-таблицу.

items = {10, 20, 30, 40, 50}

print(40 in items)  # True

Python не перебирает все элементы подряд. Он:

1. Считает hash(40)
2. По хешу определяет примерное место в таблице
3. Проверяет, лежит ли там нужный элемент

Упрощённо:

set/hash table

hash(40) -> index 3

[ ][ ][ ][40][ ][ ][ ]
         ↑
      быстро нашли

Поэтому поиск во множестве в среднем:

O(1)

Python Wiki указывает среднюю сложность x in s для list как O(n), а для set — O(1).

Пример #

nums_list = [1, 2, 3, 4, 5]
nums_set = {1, 2, 3, 4, 5}

print(5 in nums_list)  # True
print(5 in nums_set)   # True

Результат одинаковый, но механизм разный:

list:
проверяет элементы последовательно

set:
ищет по хешу

Важное ограничение set #

Во множество можно положить только хешируемые объекты.

Можно:

items = {1, 2, "abc", (10, 20)}

Нельзя:

items = {[1, 2], [3, 4]}

Будет ошибка:

TypeError: unhashable type: 'list'

Потому что список изменяемый и не имеет стабильного хеша.

Документация Python описывает set как неупорядоченную коллекцию уникальных хешируемых объектов.

Когда list всё равно лучше #

list лучше, когда важен порядок или нужны дубликаты:

items = [10, 20, 20, 30]

Список сохраняет порядок и допускает повторяющиеся элементы.

set удаляет дубликаты:

items = {10, 20, 20, 30}

print(items)  # {10, 20, 30}

Когда set лучше #

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

banned_ids = {10, 25, 31, 44}

user_id = 25

if user_id in banned_ids:
    print("blocked")

Особенно если проверок много:

allowed_ids = {1, 2, 3, 4, 5}

for user_id in users:
    if user_id in allowed_ids:
        ...

Итог #

Для поиска элемента:
set быстрее list

Но выбор зависит от задачи:

Нужен порядок и дубликаты -> list
Нужна быстрая проверка наличия -> set

Главная разница:

list ищет перебором
set ищет через хеш-таблицу

15. С какими структурами данных из модуля collections вы работали? #

Примеры структур данных из collections #

Модуль collections даёт дополнительные контейнеры поверх обычных list, dict, tuple, set.

Официально в collections есть, например: deque, defaultdict, Counter, OrderedDict, namedtuple, ChainMap, UserDict, UserList, UserString.

deque #

Двусторонняя очередь.

from collections import deque

queue = deque()

queue.append("task1")
queue.append("task2")
queue.appendleft("urgent_task")

print(queue)
# deque(['urgent_task', 'task1', 'task2'])

print(queue.popleft())
# urgent_task

print(queue.pop())
# task2

Используется для:

очередей
BFS
sliding window
быстрого добавления/удаления с двух концов

Главное отличие:

list.pop(0)      -> O(n)
deque.popleft()  -> O(1)

defaultdict #

Словарь со значением по умолчанию.

from collections import defaultdict

counter = defaultdict(int)

words = ["python", "java", "python", "go"]

for word in words:
    counter[word] += 1

print(counter)
# defaultdict(<class 'int'>, {'python': 2, 'java': 1, 'go': 1})

Без defaultdict пришлось бы писать так:

counter = {}

for word in words:
    if word not in counter:
        counter[word] = 0

    counter[word] += 1

Частые варианты:

defaultdict(int)   # счётчик
defaultdict(list)  # группировка в списки
defaultdict(set)   # группировка в множества

Пример группировки:

from collections import defaultdict

users = [
    ("Alice", "Baku"),
    ("Bob", "Baku"),
    ("John", "Moscow"),
]

users_by_city = defaultdict(list)

for name, city in users:
    users_by_city[city].append(name)

print(users_by_city["Baku"])
# ['Alice', 'Bob']

Counter #

Счётчик элементов.

from collections import Counter

items = ["apple", "banana", "apple", "orange", "banana", "apple"]

counter = Counter(items)

print(counter)
# Counter({'apple': 3, 'banana': 2, 'orange': 1})

print(counter["apple"])
# 3

print(counter.most_common(2))
# [('apple', 3), ('banana', 2)]

Используется для:

подсчёта слов
частотного анализа
подсчёта повторяющихся элементов
поиска самых популярных значений

OrderedDict #

Словарь с дополнительными операциями над порядком.

from collections import OrderedDict

data = OrderedDict()

data["a"] = 1
data["b"] = 2
data["c"] = 3

data.move_to_end("a")

print(data)
# OrderedDict([('b', 2), ('c', 3), ('a', 1)])

Сейчас обычный dict тоже сохраняет порядок вставки, но OrderedDict полезен, когда нужны специальные операции с порядком:

data.move_to_end("key")
data.popitem(last=False)

Например, для реализации LRU-кэша.

namedtuple #

Кортеж с именованными полями.

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])

point = Point(10, 20)

print(point.x)
# 10

print(point.y)
# 20

Обычный tuple:

point = (10, 20)

print(point[0])
print(point[1])

namedtuple читается понятнее:

print(point.x)
print(point.y)

Но он остаётся неизменяемым:

point.x = 100
# AttributeError

ChainMap #

Объединяет несколько словарей в одну логическую структуру.

from collections import ChainMap

defaults = {
    "debug": False,
    "timeout": 30,
}

env = {
    "timeout": 10,
}

cli_args = {
    "debug": True,
}

config = ChainMap(cli_args, env, defaults)

print(config["debug"])
# True

print(config["timeout"])
# 10

Поиск идёт слева направо:

cli_args -> env -> defaults

Удобно для конфигураций:

аргументы командной строки
переменные окружения
дефолтные настройки

UserDict #

Обёртка для создания своих словарей.

from collections import UserDict

class UpperKeyDict(UserDict):
    def __setitem__(self, key, value):
        super().__setitem__(key.upper(), value)

data = UpperKeyDict()

data["name"] = "Alice"
data["city"] = "Baku"

print(data)
# {'NAME': 'Alice', 'CITY': 'Baku'}

Используется, когда нужно создать свой контейнер на базе словаря.

UserList #

Обёртка для создания своих списков.

from collections import UserList

class PositiveList(UserList):
    def append(self, item):
        if item <= 0:
            raise ValueError("Only positive numbers are allowed")

        super().append(item)

numbers = PositiveList()

numbers.append(10)
numbers.append(5)

print(numbers)
# [10, 5]

numbers.append(-1)
# ValueError

UserString #

Обёртка для создания своих строковых классов.

from collections import UserString

class LowerString(UserString):
    def __init__(self, value):
        super().__init__(value.lower())

text = LowerString("HELLO Python")

print(text)
# hello python

Самые часто используемые #

На практике чаще всего встречаются:

from collections import deque, defaultdict, Counter

Они используются чаще остальных:

deque        -> очередь
defaultdict  -> группировка и значения по умолчанию
Counter      -> подсчёт элементов

Итоговая таблица #

16. Что может выступать ключом в словаре (dict) и каким образом устроена внутренняя структура словаря? #

Что может быть ключом в словаре? #

Словари в Python реализованы как хеш-таблицы. При добавлении элемента вычисляется хеш ключа с помощью встроенной функции hash(), который определяет позицию для хранения пары ключ-значение в таблице. Именно благодаря этому механизму операции поиска, вставки и удаления выполняются в среднем за константное время O(1), делая словарь высокопроизводительной структурой данных.

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

Механизм работы:

• Вычисляется хеш ключа
• По хешу определяется “корзина” (bucket)
• В корзине ищется ключ (уже с использованием eq)

Если хеш объекта меняется после помещения в словарь, он окажется в неправильной корзине и станет недоступен.

Хешируемость — это протокол, состоящий из двух методов:

• __hash__— возвращает хеш-значение объекта
• __eq__ — определяет равенство объектов

Любой объект по умолчанию хешируем (благодаря реализации в object). В базовом классе object уже реализованы оба метода:

• __hash__— основан на идентификаторе объекта (id)

• __eq__— сравнивает идентификаторы объектов (is)

Это означает, что любой созданный нами класс по умолчанию хешируем.

Объект становится нехешируемым, если:

• Явно установить hash = None
• Переопределить eq, но не переопределить hash

Кортеж (tuple) не может быть ключом в словаре, в том случае если в нем изменяемые типы данных.

Как dict и set реализованы внутри? #

Dict и Set реализованы в виде хэш-таблицы.

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

Сложность получения элемента в Dict и Set в среднем случае за O(1), а в худшем случае - за O(n) (большое количество коллизий, плохая хеш-функция, т.е. не обеспечивает равномерное распределение) поскольку элемент может быть получен просто с помощью хэш-функции в качестве индекса массива. Однако в худшем случае, когда возникают хэш-коллизии, сложность может вырасти до O(n), где n — количество элементов в таблице. Также стоит заметить, что сложность операций добавления, удаления и поиска элементов в Set и Dict также составляет O(1) в наилучшем случае и O(n) в худшем случае.

Скорость поиска O(1) в словарях обусловлена использованием хеш-таблицы, которая преобразует ключ в индекс ячейки памяти. При поиске сначала вычисляется хеш ключа, а затем происходит прямой доступ к соответствующему элементу, что занимает константное время независимо от размера словаря.

Статья на хабре:  Python. Внутреннее устройство множеств set и словарей dict.

17. Может ли кортеж (tuple), использоваться в качестве ключа словаря (dict)? #

Да, но только при одном условии #

tuple может быть ключом словаря, если сам кортеж хешируемый.

А кортеж хешируемый только тогда, когда все его элементы тоже хешируемые. В документации Python указано, что неизменяемые контейнеры вроде tuple и frozenset хешируемы только при условии, что их элементы хешируемы.

Работает #

data = {
    (1, 2): "point A",
    (3, 4): "point B",
}

print(data[(1, 2)])
# point A

Здесь (1, 2) можно использовать как ключ, потому что int — хешируемый тип.

Также можно:

users = {
    ("admin", "read"): True,
    ("admin", "write"): True,
    ("guest", "read"): True,
}

print(users[("admin", "write")])
# True

Не работает #

data = {
    ([1, 2], 3): "value"
}

Будет ошибка:

TypeError: unhashable type: 'list'

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

Почему так #

dict ищет ключи через хеш-таблицу. Поэтому ключ словаря должен иметь стабильный хеш. Python glossary прямо указывает: хешируемость делает объект пригодным для использования как ключ словаря и элемент множества.

Кортеж сам по себе неизменяемый:

key = (1, 2, 3)

Но если внутри лежит изменяемый объект:

key = ([1, 2], 3)

то содержимое списка можно изменить:

key[0].append(99)

Из-за этого такой кортеж не может иметь надёжный стабильный хеш.

Как проверить #

print(hash((1, 2, 3)))
# работает

print(hash(([1, 2], 3)))
# TypeError: unhashable type: 'list'

Практическое применение #

Кортежи часто используют как составные ключи:

prices = {
    ("BTC", "USD"): 105000,
    ("ETH", "USD"): 3500,
    ("EUR", "AZN"): 1.9,
}

print(prices[("BTC", "USD")])

Или координаты:

board = {
    (0, 0): "empty",
    (0, 1): "wall",
    (1, 0): "player",
}

print(board[(1, 0)])
# player

Итог #

tuple может быть ключом dict,
если все элементы внутри tuple хешируемые

Работает:

{(1, 2): "ok"}
{("user", 123): "ok"}
{((1, 2), "x"): "ok"}

Не работает:

{([1, 2], 3): "error"}
{({"a": 1}, 2): "error"}
{({1, 2}, 3): "error"}

Потому что list, dict, set — изменяемые и не хешируемые.

18. Может ли кортеж (tuple) содержать изменяемые объекты? #

Да, может #

tuple может содержать изменяемые объекты:

t = ([1, 2], {"name": "Alice"}, {10, 20})

Здесь сам кортеж неизменяемый, но внутри него лежат изменяемые объекты:

tuple
 ├─ list
 ├─ dict
 └─ set

Документация Python описывает tuple как неизменяемую последовательность, но неизменяемость относится к самому контейнеру: он не может заменить свои элементы после создания. При этом объект, на который указывает элемент кортежа, может быть изменяемым.

Что нельзя менять #

Нельзя заменить элемент кортежа:

t = ([1, 2], "abc")

t[0] = [3, 4]

Будет ошибка:

TypeError: 'tuple' object does not support item assignment

Потому что ты пытаешься изменить сам кортеж: заменить ссылку в позиции 0.

Что можно менять #

Можно изменить объект, который лежит внутри кортежа:

t = ([1, 2], "abc")

t[0].append(3)

print(t)
# ([1, 2, 3], 'abc')

Здесь кортеж не изменил свой элемент.

Было:

t[0] -> список [1, 2]

Стало:

t[0] -> тот же самый список [1, 2, 3]

Ссылка внутри кортежа осталась прежней. Изменилось содержимое списка.

Важная разница #

t = ([1, 2],)

t[0].append(3)   # можно
t[0] = [1, 2, 3] # нельзя

Разница такая:

t[0].append(3)
-> меняем объект, на который указывает кортеж

t[0] = [1, 2, 3]
-> пытаемся заменить элемент самого кортежа

Пример с id #

lst = [1, 2]
t = (lst,)

print(id(t[0]))

t[0].append(3)

print(id(t[0]))
print(t)

Вывод будет примерно такой:

140000000000000
140000000000000
([1, 2, 3],)

id(t[0]) не изменился, потому что это тот же список.

Итог #

tuple может содержать изменяемые объекты

Но:

нельзя менять сам tuple
можно менять изменяемые объекты внутри tuple

Главная мысль:

неизменяемость tuple означает, что нельзя заменить его ссылки на элементы,
но не означает глубокую неизменяемость всех вложенных объектов

19. Можно ли использовать объект класса как ключ словаря (dict)? #

Да, можно, но объект класса должен быть хешируемым.

Главное правило #

Объект может быть ключом dict, если:

у объекта есть __hash__()
и корректно работает __eq__()

Словарь использует хеш ключа для быстрого поиска, а при совпадении хешей дополнительно сравнивает ключи через равенство. В документации Python указано, что ключами словаря могут быть объекты с методами __hash__() и __eq__().

Обычный объект класса — можно #

class User:
    pass


u1 = User()
u2 = User()

data = {
    u1: "first user",
    u2: "second user",
}

print(data[u1])  # first user

По умолчанию пользовательские объекты хешируются по своей идентичности, то есть фактически по объекту, а не по его содержимому.

Если переопределить eq, нужно быть осторожным #

class User:
    def __init__(self, username):
        self.username = username

    def __eq__(self, other):
        return isinstance(other, User) and self.username == other.username


u = User("alex")

data = {
    u: "admin"
}

Такой код даст ошибку:

TypeError: unhashable type: 'User'

Причина: если класс переопределяет __eq__, но не задаёт __hash__, Python делает объект нехешируемым, чтобы не нарушить работу dict. Это связано с правилом: если два объекта равны, их хеши тоже должны быть равны.

Правильный вариант #

class User:
    def __init__(self, username):
        self.username = username

    def __eq__(self, other):
        return isinstance(other, User) and self.username == other.username

    def __hash__(self):
        return hash(self.username)


u1 = User("alex")
u2 = User("alex")

data = {
    u1: "admin"
}

print(data[u2])  # admin

Здесь u1 и u2 считаются одинаковыми ключами, потому что:

u1 == u2
hash(u1) == hash(u2)

Важный момент #

Не стоит делать ключ словаря на основе изменяемого состояния:

u = User("alex")

data = {
    u: "admin"
}

u.username = "bob"

После изменения username изменится и хеш объекта. Словарь может больше не найти этот ключ корректно.

Итог #

Объект класса можно использовать как ключ dict,
если он hashable.

По умолчанию обычные объекты классов hashable.

Если переопределяешь __eq__,
обычно нужно явно определить __hash__.

Хеш должен строиться только на неизменяемых данных.

20. Являются ли bytearray и bytes изменяемыми типами #

bytes      — immutable, неизменяемый тип
bytearray  — mutable, изменяемый тип

Официальная документация Python описывает bytearray как mutable sequence of integers в диапазоне 0 <= x < 256, то есть изменяемую последовательность байтов. bytes относится к неизменяемым бинарным последовательностям.

bytes — неизменяемый #

b = b"hello"

b[0] = 72

Будет ошибка:

TypeError: 'bytes' object does not support item assignment

То есть объект bytes после создания изменить нельзя.

bytearray — изменяемый #

ba = bytearray(b"hello")

ba[0] = 72

print(ba)  # bytearray(b'Hello')

Здесь первый байт изменился прямо внутри объекта.

Важно #

И bytes, и bytearray хранят не символы как str, а последовательность чисел-байтов:

b = b"ABC"

print(b[0])  # 65
print(b[1])  # 66
print(b[2])  # 67

То есть при обращении по индексу возвращается int, а не отдельный bytes.

Итог #

bytes похож на tuple/str:
создал → изменить нельзя

bytearray похож на list:
создал → можно менять элементы

Из-за этого bytes можно использовать как ключ dict, а bytearray — нельзя, потому что изменяемые объекты обычно нехешируемы.

21. Какая сложность поиска/вставки в list? #

Поиск в list #

Зависит от того, какой поиск имеется в виду.

Доступ по индексу #

items = [10, 20, 30]

items[1]

Сложность:

O(1)

Потому что list внутри CPython реализован как массив ссылок, и Python может сразу перейти к нужной позиции. В таблице сложности Python Wiki для list операция Get Item указана как O(1). ( wiki.python.org)

Поиск значения #

items = [10, 20, 30, 40]

20 in items
items.index(20)

Сложность:

O(n)

Python должен идти по элементам слева направо и сравнивать их, пока не найдёт нужный элемент.

20 in [10, 20, 30]      # может найти быстро
999 in [10, 20, 30]     # проверит весь список

В среднем и в худшем случае поиск значения в списке — O(n). В таблице Python Wiki операция x in s для list указана как O(n). ( wiki.python.org)

Вставка в list #

Тут тоже зависит от места вставки.

append в конец #

items = [1, 2, 3]

items.append(4)

Сложность:

O(1) амортизированно

Обычно добавление в конец быстрое, потому что список заранее выделяет немного больше памяти, чем нужно. В CPython при расширении списка используется over-allocation, чтобы длинная серия append() работала амортизированно эффективно. ( GitHub)

insert в начало или середину #

items = [1, 2, 3, 4]

items.insert(0, 100)
items.insert(2, 200)

Сложность:

O(n)

Причина: элементы справа от позиции вставки нужно сдвинуть.

[1, 2, 3, 4]
 insert(0, 100)
[100, 1, 2, 3, 4]
      ↑  ↑  ↑  ↑
      элементы сдвигаются

Официальная документация Python прямо указывает, что вставки и удаления из начала списка медленные, потому что остальные элементы должны быть сдвинуты.

Итоговая таблица #

Главное #

list хорош для:
- доступа по индексу: O(1)
- добавления в конец: O(1) амортизированно

list плох для:
- поиска значения: O(n)
- вставки в начало/середину: O(n)

Если нужен быстрый поиск по значению — обычно берут set или dict, потому что там поиск в среднем O(1).

22. Когда list.append() в Python не O(1)? #

Когда list.append() не O(1) #

list.append() не является строго O(1) на каждой отдельной операции.

Правильная формулировка:

list.append(x) — O(1) амортизированно
но иногда отдельный append может быть O(n)

Python Wiki указывает для list.append() сложность O(1) в среднем/амортизированно. Для текущего CPython это связано с тем, что список хранится как динамический массив и иногда расширяет внутреннее хранилище.

Обычный случай: есть свободная ёмкость #

Список хранит не только текущую длину, но и внутреннюю ёмкость.

len(lst)       = 3
capacity       = 6

[1, 2, 3, _, _, _]

Если свободное место есть, append() просто кладёт ссылку на объект в следующую ячейку:

lst.append(4)

[1, 2, 3, 4, _, _]

Сложность:

O(1)

Необычный случай: ёмкость закончилась #

Когда внутренний массив заполнен:

len(lst)       = 4
capacity       = 4

[1, 2, 3, 4]

и вызывается:

lst.append(5)

CPython должен увеличить внутреннее хранилище. Для этого он может:

1. выделить новый массив большего размера
2. перенести туда ссылки на старые элементы
3. добавить новый элемент

Схематично:

старое хранилище:
[1, 2, 3, 4]

новое хранилище:
[1, 2, 3, 4, 5, _, _, ...]

В этот момент нужно обработать n уже существующих элементов, поэтому отдельный append() может стать:

O(n)

В исходниках CPython функция изменения размера списка прямо описывает over-allocation: список выделяет памяти немного больше текущего размера, чтобы длинная серия append() оставалась линейной по времени, то есть O(1) амортизированно на одну вставку. ( GitHub)

Почему всё равно говорят O(1) #

Потому что расширение происходит не при каждом append().

Например:

append 1  → O(1)
append 2  → O(1)
append 3  → O(1)
append 4  → O(1)
append 5  → O(n), потому что нужно расширение
append 6  → O(1)
append 7  → O(1)
...

Если сделать много добавлений подряд:

lst = []

for i in range(1_000_000):
    lst.append(i)

общая сложность будет:

O(n)

а не O(n²), потому что расширения происходят редко.

Отсюда:

один конкретный append       → может быть O(n)
длинная серия append'ов      → O(1) амортизированно на операцию

Итог #

list.append() не O(1), когда у списка закончилась внутренняя ёмкость и CPython вынужден расширять внутренний массив.

Есть свободное место  → O(1)
Нужно расширение      → O(n)
В среднем по серии    → O(1) amortized

Важно: переносит не сами Python-объекты, а ссылки на них. То есть объекты внутри списка не копируются полностью, копируется массив указателей.

23. Когда list.append() в Python больше O(n)? #

В нормальной модели сложности list.append(x) в Python не бывает хуже O(n) по размеру списка.

Для CPython:

list.append(x)

имеет:

амортизированно: O(1)
в отдельный момент resize: O(n)
хуже O(n): обычно нет

Когда append() становится O(n) #

Это происходит, когда у списка закончилась внутренняя ёмкость.

Python list внутри хранит массив ссылок:

[ref, ref, ref, свободно, свободно]

Если свободное место есть:

lst.append(x)

просто кладёт ссылку в следующую ячейку:

O(1)

Если свободного места нет, CPython должен увеличить внутренний массив. Для этого он выделяет больше памяти и переносит старые ссылки в новое хранилище:

старый массив из n ссылок
↓
новый массив большей ёмкости
↓
копирование n ссылок

Это уже:

O(n)

В исходниках CPython list_resize() прямо указано, что список делает over-allocation — выделяет память с запасом, чтобы длинная серия append() имела линейное амортизированное поведение. Там же показан рост ёмкости: 0, 4, 8, 16, 24, 32, 40, 52, ... ( GitHub)

Почему тогда говорят append() — O(1) #

Потому что это амортизированная сложность.

Пример:

lst = []

for i in range(1_000_000):
    lst.append(i)

Не каждый append() вызывает resize. Большинство вставок просто занимают уже выделенные свободные ячейки.

Поэтому вся серия из n добавлений стоит примерно:

O(n)

а один append() в среднем:

O(1)

Python Wiki по текущему CPython тоже указывает для list.append средний случай O(1) и амортизированный worst case O(1), но отдельно объясняет, что основные затраты у списка появляются при росте за пределы текущей выделенной ёмкости, потому что элементы должны перемещаться

Может ли быть больше O(n) #

Формально по размеру списка — нет, если мы говорим именно об алгоритме append().

Но по реальному времени на практике может казаться хуже из-за внешних факторов:

нехватка памяти
работа системного realloc
свопинг
фрагментация памяти
паузы ОС / аллокатора
MemoryError

Это уже не алгоритмическая сложность append(), а поведение памяти и операционной системы.

Важно: при resize Python не копирует сами объекты, он копирует ссылки на объекты. То есть если в списке лежат огромные объекты, сами они не дублируются при append().

Итог #

append без resize      -> O(1)
append с resize        -> O(n)
серия append           -> O(n) всего
один append в среднем  -> O(1)
хуже O(n) алгоритмически -> нет

То есть корректнее говорить так:

list.append() — амортизированно O(1), но отдельный вызов может быть O(n) при расширении внутреннего массива.

24. Какая сложность поиска в set? #

Поиск в set в Python:

средний случай: O(1)
худший случай: O(n)

То есть проверка:

x in my_set

обычно работает за константное время.

Почему в среднем O(1) #

set реализован через хеш-таблицу.

Когда выполняется:

x in my_set

Python:

1. Вычисляет hash(x)
2. По хешу находит предполагаемую ячейку
3. Проверяет, лежит ли там нужный элемент

Упрощённо:

элемент -> hash -> индекс в таблице -> проверка

Поэтому не нужно проходить все элементы, как в списке.

Для сравнения:

x in my_list

для list обычно требует последовательного поиска:

O(n)

А для set:

O(1) в среднем

Когда может быть O(n) #

Худший случай возникает при большом количестве коллизий.

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

hash(a) -> ячейка 5
hash(b) -> ячейка 5
hash(c) -> ячейка 5

Тогда Python приходится искать дальше по таблице и сравнивать элементы.

В самом плохом случае поиск может деградировать до:

O(n)

Но на практике для нормальных хешируемых объектов это редкая ситуация.

Важно про hash и __eq__ #

Для поиска в set объект должен быть хешируемым.

Например, можно:

s = {1, 2, 3}

print(2 in s)  # True

Нельзя положить изменяемый list:

s = {[1, 2, 3]}  # TypeError: unhashable type: 'list'

Потому что list изменяемый и не имеет стабильного хеша.

Итог #

x in set

имеет сложность:

average case: O(1)
worst case:   O(n)

Главная причина эффективности set — использование хеш-таблицы, а не последовательного перебора элементов.

25. Что значит неизменяемый объект в Python? #

Что значит неизменяемый объект #

Неизменяемый объект в Python — это объект, значение которого нельзя изменить после создания. В документации Python такие объекты называются immutable: значение объекта фиксировано после создания.

Пример:

x = "hello"

Строка "hello" — неизменяемый объект.

Нельзя изменить саму строку по индексу:

x[0] = "H"

Будет ошибка:

TypeError: 'str' object does not support item assignment

Важно: переменная не объект #

В Python переменная — это не контейнер со значением, а имя, которое ссылается на объект.

x = "hello"
x = "Hello"

Это не изменение старой строки "hello".

Происходит вот что:

x ──> "hello"

x = "Hello"

x ──> "Hello"

Имя x просто стало ссылаться на другой объект.

Старый объект "hello" не изменился.

Пример через id() #

x = "hello"
print(id(x))

x = x + "!"
print(id(x))

Скорее всего, id будет разным:

1400...
1401...

Потому что выражение:

x + "!"

создаёт новую строку, а не меняет старую.

Примеры неизменяемых типов #

К неизменяемым встроенным типам относятся:

int
float
bool
str
tuple
bytes
frozenset
NoneType

В документации Python прямо указано, что числа, строки и кортежи являются неизменяемыми, а списки и словари — изменяемыми.

Пример с числом:

a = 10
a += 1

Это не изменение объекта 10.

Это примерно так:

a ──> 10

a = a + 1

a ──> 11

Число 10 не стало числом 11.

Сравнение с изменяемым объектом #

Список — изменяемый объект:

lst = [1, 2, 3]
lst.append(4)

Тот же самый объект списка изменился:

[1, 2, 3]
↓
[1, 2, 3, 4]

А строка так не работает:

s = "abc"
s += "d"

Создаётся новая строка:

"abc"  -> старый объект
"abcd" -> новый объект

Нюанс с tuple #

tuple сам по себе неизменяемый:

t = (1, 2, 3)
t[0] = 100  # ошибка

Но tuple может содержать изменяемый объект:

t = ([1, 2], 3)

t[0].append(99)

print(t)

Результат:

([1, 2, 99], 3)

Здесь сам tuple не изменился: он всё ещё содержит ссылку на тот же список. Но изменился список внутри него.

В документации Python отдельно отмечается этот нюанс: неизменяемый контейнер может содержать ссылку на изменяемый объект, и тогда внутренний объект может измениться, хотя сам контейнер остаётся неизменяемым.

Итог #

Неизменяемый объект = объект, состояние которого нельзя изменить после создания.

При “изменении” immutable-объекта Python обычно создаёт новый объект:

x = 5
x += 1

Фактически:

x ──> 5
x ──> 6

А не:

объект 5 превратился в объект 6

26. Какие есть альтернативы dict в Python? #

Альтернативы dict зависят от задачи. В большинстве случаев обычный dict — лучший вариант, но в стандартной библиотеке Python есть несколько специализированных замен.

Основные альтернативы из collections #

В документации collections эти классы прямо описаны как dict-подобные контейнеры или подклассы dict: Counter, OrderedDict, defaultdict, ChainMap, UserDict.

defaultdict #

Используется, когда при обращении к отсутствующему ключу нужно автоматически создавать значение.

Обычный dict:

data = {}

if "python" not in data:
    data["python"] = []

data["python"].append("dict")

Через defaultdict:

from collections import defaultdict

data = defaultdict(list)

data["python"].append("dict")

Полезно для группировки:

from collections import defaultdict

users_by_city = defaultdict(list)

users_by_city["Baku"].append("Ali")
users_by_city["Baku"].append("Murad")

print(users_by_city)

Counter #

Используется для подсчёта элементов.

from collections import Counter

words = ["a", "b", "a", "c", "b", "a"]

counter = Counter(words)

print(counter)

Результат:

Counter({'a': 3, 'b': 2, 'c': 1})

По документации Counter — это подкласс dict, где элементы хранятся как ключи, а их количество — как значения.

OrderedDict #

Раньше часто использовался, когда нужно было сохранить порядок вставки.

Но в современных версиях Python обычный dict уже гарантирует порядок вставки. Это стало гарантией языка с Python 3.7.

Поэтому сейчас OrderedDict нужен реже. Его стоит использовать, когда нужны специальные операции с порядком, например:

from collections import OrderedDict

cache = OrderedDict()

cache["a"] = 1
cache["b"] = 2

cache.move_to_end("a")

print(cache)

То есть:

Обычный dict      -> порядок вставки есть
OrderedDict       -> порядок + специальные методы управления порядком

ChainMap #

Используется, когда нужно работать с несколькими словарями как с одним, но без их физического объединения.

from collections import ChainMap

defaults = {"theme": "light", "debug": False}
user_settings = {"debug": True}

settings = ChainMap(user_settings, defaults)

print(settings["theme"])  # light
print(settings["debug"])  # True

ChainMap ищет ключи последовательно по нескольким mapping-объектам. При записи изменения идут только в первый mapping.

Упрощённо:

ChainMap(user_settings, defaults)

поиск:
user_settings -> defaults

MappingProxyType #

Это не полноценная замена dict, а read-only view над словарём.

from types import MappingProxyType

config = {
    "debug": False,
    "host": "localhost",
}

readonly_config = MappingProxyType(config)

print(readonly_config["host"])

Изменить через proxy нельзя:

readonly_config["debug"] = True

Будет ошибка:

TypeError

Документация Python указывает, что types.MappingProxyType можно использовать для создания read-only view над dict.

Важный нюанс:

config["debug"] = True

print(readonly_config["debug"])  # True

MappingProxyType запрещает изменение через proxy, но если исходный словарь изменился, proxy это увидит.

UserDict #

Используется, когда нужно сделать собственный словарь с переопределённым поведением.

from collections import UserDict

class LowerKeyDict(UserDict):
    def __setitem__(self, key, value):
        super().__setitem__(key.lower(), value)

data = LowerKeyDict()

data["Name"] = "Alex"

print(data)

Результат:

{'name': 'Alex'}

UserDict — это wrapper вокруг словаря, который удобнее использовать для создания своих dict-подобных классов.

collections.abc.Mapping и MutableMapping #

Это не конкретные контейнеры, а интерфейсы.