Почему вставка в начало списка стоит O(n), откуда у словаря O(1) и когда оно превращается в O(n), как устроены dict в Python, map в Go и HashMap в Java — и как узнать задачу на хеш-таблицу на собеседовании.
Листайте стрелками ← →, свайпом или кнопками внизу. В схемах нажимайте кнопки, вводите ключи и двигайте ползунки.
Массив — непрерывный кусок памяти: адрес i-го элемента = начало + i × размер элемента. Отсюда O(1) по индексу и быстрый последовательный проход. Но вставка или удаление в середине сдвигает весь хвост — O(n).
list в Python, slice в Go, ArrayList в Java, Array в JS — держит запас ёмкости. Место кончилось — выделяет блок побольше и копирует всё.append: копирований за всё время — не больше n·1/(k−1).list в Python хранит указатели на объекты, а не числа подряд — об этом в «Данных в памяти».Каждый узел — отдельный объект в куче. Адрес следующего узнаётся, только когда прочитан текущий, поэтому процессор не может подгрузить его заранее: каждое звено — возможный промах кэша, ~100 нс (подробнее о кэшах).
functools.lru_cache), списки свободных блоков в аллокаторах, list_head в ядре Linux — узел встроен прямо в структуру.LinkedList в Java почти всегда медленнее ArrayList — даже на вставках в середину: найти позицию — те же O(n), но с промахами.collections.deque — компромисс: двусвязный список блоков по 64 элемента.append/pop у list, slice в Go, ArrayDeque в Java. Вызовы функций, отмена действий, скобки, обход в глубину.head и tail бегут по кругу, элементы не сдвигаются. Так устроены ArrayDeque, буфер канала в Go (про каналы), очереди сетевой карты, io_uring, буфер perf.Нажимайте кнопки и следите, как индексы переходят через конец массива: (i + 1) % cap.
Воркер на Python разбирает очередь задач: tasks — обычный list на 1 000 000 элементов, в цикле task = tasks.pop(0), пока список не опустеет. Сколько это стоит?
pop(0) делает memmove всех оставшихся указателей на одну позицию: в сумме n²/2 ≈ 5·10¹¹ перемещений, терабайты копирования. Очередь в Python — collections.deque с popleft() за O(1). То же в Go: q = q[1:] дёшево, но держит в памяти весь старый массив; в JS Array.shift() на больших массивах тоже O(n).Хеш-функция превращает ключ в число, а остаток от деления на размер таблицы m — в номер корзины. Хорошая функция раскидывает даже похожие ключи равномерно: в каждой корзине ≈ n/m ключей.
h & (m − 1), то есть младшие биты. Java поэтому подмешивает к ним старшие: h ^ (h >>> 16).str в Python, aeshash/wyhash в Go, 31·h + c в Java String.hashCode(). Строки кэшируют свой хеш — второй раз он не считается.Введите ключ и выберите функцию. Гистограмма — 1000 ключей user:1…user:1000.
Два ключа попали в одну корзину — это нормально, вопрос в том, где хранить второй.
HashMap, C++ std::unordered_map, Go map до 1.24 (корзины по 8 + overflow-корзины).dict и set, Go map с 1.24 (Swiss tables), Rust HashMap, Abseil flat_hash_map.Вставка начинается с ячейки h(k) и идёт вправо до первого свободного места. Поиск идёт тем же путём и останавливается на пустой ячейке: дальше ключа быть не может.
Здесь h(k) = k mod 10 — последняя цифра. Вставьте 12, 22, 32, удалите 22 и найдите 32. Потом включите удаление без надгробия и повторите.
Коэффициент заполнения α = n/m. При линейном пробировании поиск отсутствующего ключа стоит в среднем ½·(1 + 1/(1−α)²) проб: при α = 0,5 — 2,5, при 0,9 — уже 50. Поэтому таблицу расширяют заранее.
h & (m−1) зависит от m. Одна вставка стоит O(n), в среднем — O(1).dict — 2/3, Java HashMap — 0,75, Go Swiss tables — 7/8.make(map[K]V, n), HashMap.newHashMap(n).O(1) обещано для «случайных» ключей. Если подобрать ключи с одинаковым хешем, таблица вырождается в список: n вставок — n²/2 сравнений.
"Aa" и "BB" имеют один хеш — из таких блоков собирается 2k коллизий.PYTHONHASHSEED, в Go — свой seed у каждой map), дерево вместо длинной цепочки (Java 8), лимит числа параметров запроса.Выберите защиту и двигайте число ключей.
С 3.6 словарь — два массива: маленький разреженный массив индексов и плотный массив записей (хеш, ключ, значение) в порядке вставки. Поэтому dict помнит порядок — с 3.7 это гарантия языка — и занимает меньше памяти.
i = (5·i + 1 + perturb) mod m, а perturb >>= 5 — так в выбор ячейки входят все биты хеша.Добавляйте и удаляйте ключи. Хеши здесь условные: в настоящем Python хеш строки меняется от запуска к запуску.
Map.Общее у всех: порядок обхода — деталь реализации. Go специально начинает обход со случайной позиции, чтобы никто на порядок не полагался. Ни одна из этих map не потокобезопасна: sync.Map/мьютекс в Go, ConcurrentHashMap в Java.
Контракт: равные объекты обязаны иметь равные хеши, а хеш не должен меняться, пока объект лежит в таблице. Нарушили — элемент «потерян»: он в таблице, но найти его нельзя.
list, dict, set не хешируемы; @dataclass(frozen=True) — хешируем. Определили __eq__ — __hash__ сбрасывается в None.equals без hashCode — HashSet хранит «дубликаты»; поменяли поле ключа — remove() молча не работает.NaN != NaN, поэтому m[math.NaN()] = 1 каждый раз добавляет новую запись.Что напечатает Python?
d = {1: "int", True: "bool", 1.0: "float"}
print(d)
1 == True == 1.0 и hash(1) == hash(True) == hash(1.0) == 1 — для таблицы это один ключ. Второе и третье присваивание находят существующую запись и меняют только значение, а ключом остаётся первый объект — 1. На практике это ловят, когда смешивают в ключах int и float из JSON или bool и числа.set — хеш-таблица без значений: in, add, remove — O(1) в среднем. А x in list — O(n), и проверка в цикле незаметно делает из O(n) O(n²).a & b стоит O(min(|a|, |b|)): перебирается меньшее множество, каждый элемент ищется в большем.map[T]struct{} — пустая структура не занимает памяти. Java: HashSet — обёртка над HashMap, LinkedHashSet помнит порядок.
ids = set(user_ids) # O(n) один раз
active = [o for o in orders if o.user_id in ids]
# со списком: 10⁵ × 10⁵ / 2 сравнений — минуты,
# с set — 10⁵ проверок, миллисекунды
uniq = list(dict.fromkeys(xs)) # дедуп с порядком
both, either, only_a = a & b, a | b, a - b
from collections import Counter
Counter("mississippi").most_common(2)
# [('i', 4), ('s', 4)]
Надо за O(1) найти ключ, за O(1) поднять его в начало и при переполнении выкинуть самый давний. Таблица даёт поиск и указатель на узел, список — порядок: узел вынимается из середины за O(1), потому что искать его не нужно.
functools.lru_cache — dict + кольцевой двусвязный список на C; руками — OrderedDict.move_to_end. Java: LinkedHashMap(…, true) + removeEldestEntry. Go: container/list + map.Классическая задача собеседования (LeetCode 146). Обращайтесь к ключам: кэш на 4 элемента.
dict или set увиденного: Two Sum за O(n) вместо O(n²)."".join(sorted(w)), кортеж частот.Counter.[l, r] + счётчики или последние позиции в dict.dict (следующий слайд).Размен почти всегда один: O(n) памяти ради O(n) времени. Проговаривайте его вслух.
Сумма nums[i..j] = Pj+1 − Pi, где P — префиксные суммы. На каждом шаге спрашиваем: сколько раз раньше встречался префикс s − k? Счётчик префиксов в dict отвечает за O(1) — итого O(n).
def subarray_sum(nums, k):
seen = Counter({0: 1}) # пустой префикс
s = count = 0
for x in nums:
s += x
count += seen[s - k]
seen[s] += 1
return count
Скользящее окно не годится: с отрицательными числами сумма окна не растёт монотонно. Префиксы — и в жизни: счётчик в Prometheus только растёт, а значение за интервал — разность двух точек.
В Go-сервисе кэш — обычная map[string]*User. HTTP-обработчики пишут в неё из разных горутин без мьютекса. Что будет под нагрузкой?
sync.Mutex/RWMutex или sync.Map, а находится заранее go test -race. В Java старый HashMap при одновременном росте мог зациклить цепочку — поток вечно крутился на 100% CPU.sys.getsizeof прыгает в момент перевыделения.hash("abc") дважды; алгоритм — в sys.hash_info.list против set: python -m timeit. Go: go test -bench . -benchmem покажет аллокации на рост map без ёмкости.go test -race; в Java — ConcurrentHashMap по умолчанию для общего состояния.make([]T, 0, n), make(map[K]V, n), new ArrayList<>(n), HashMap.newHashMap(n) (Java 19+).
>>> import sys
>>> xs, sizes = [], []
>>> for i in range(17):
... xs.append(i); sizes.append(sys.getsizeof(xs))
>>> sorted(set(sizes)) # ёмкость 4 → 8 → 16 → 24
[88, 120, 184, 248]
$ python3 -c 'print(hash("abc"))'
-4573226438459138812
$ python3 -c 'print(hash("abc"))'
7012385830413725190
>>> sys.hash_info.algorithm
'siphash13'
$ python3 -m timeit -s 'x=[*range(10**6)]' '-1 in x'
50 loops, best of 5: 6.1 msec per loop
$ python3 -m timeit -s 'x={*range(10**6)}' '-1 in x'
10000000 loops, best of 5: 21 nsec per loop
pop(0) — O(n). Динамический массив растёт в k раз, и append амортизированно O(1).dict.O(1) — это обещание в среднем, а не гарантия. Гарантию дают seed, запас места и неизменяемые ключи.