Lookup за O(1) — это когда мы можем проверить или достать значение почти
мгновенно, без прохода по всей коллекции.
lookup — это операция «посмотреть, есть ли ключ» или «достать значение по
ключу».
Например:
seen = {3, 5, 8}
5 in seen
Это lookup: «есть ли 5 в seen?»
Для set, HashSet, dict, HashMap и похожих hash-структур такой поиск
обычно считается O(1) в среднем.
O(1) значит: время операции не растёт от размера коллекции напрямую.
То есть если у тебя:
10 элементов
1000 элементов
1 000 000 элементов
проверка примерно остаётся одной и той же по характеру операции:
x in seen
Она не превращается в проход по всем элементам.
Контраст с массивом
Если искать в обычном массиве:
arr = [3, 5, 8, 10, 12]
if 10 in arr:
...
то в худшем случае надо пройти почти весь массив:
3? нет
5? нет
8? нет
10? да
Это O(n).
А если использовать set:
seen = {3, 5, 8, 10, 12}
if 10 in seen:
...
то структура сразу примерно знает, где искать 10. Поэтому это O(1) в
среднем.
Почему HashMap и HashSet дают O(1)
Потому что они используют hash function.
Упрощённо:
ключ -> hash -> индекс внутри таблицы
Например:
"apple" -> hash("apple") -> ячейка 42
И когда ты потом спрашиваешь:
"apple" in seen
структура не перебирает все элементы. Она снова считает hash и идёт примерно в
ту же ячейку.
Связь с seen set
seen = set()
for x in nums:
if x in seen: # lookup O(1)
return True
seen.add(x)
Вот эта строка:
x in seen
это lookup за O(1) в среднем.
Поэтому проверка дубликатов становится O(n), а не O(n^2).
Связь с frequency map
freq = {}
for x in nums:
freq[x] = freq.get(x, 0) + 1
Вот это:
freq.get(x, 0)
тоже lookup за O(1) в среднем.
Мы быстро достаём текущее количество для x.
Связь с grouping
groups = {}
for word in words:
key = "".join(sorted(word))
if key not in groups:
groups[key] = []
groups[key].append(word)
Здесь:
key in groups
groups[key]
groups.get(key)
тоже lookup за O(1) в среднем.
Мы быстро находим нужную группу.
Важная точность
Когда говорят:
HashMap lookup is O(1)
обычно имеют в виду:
average case / expected case
То есть в среднем.
В худшем случае из-за hash collisions lookup может быть хуже. Например, если
много ключей попали в одну корзину, внутри неё придётся искать дольше.
Но в нормальных реализациях HashMap, HashSet, dict, set, Map и Set
это обычно работает как O(1) в среднем.
Коротко
lookup за O(1) — это быстрый доступ по ключу:
set: есть элемент или нет?
map: какое значение лежит по ключу?
Именно поэтому seen set, frequency map и grouping такие сильные паттерны:
они заменяют постоянный перебор массива быстрым вопросом к hash-структуре.
