Что решает
есть ли элемент
Статьи
DS
Структура данных
Хеш-таблица
Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива.
O(1) в среднем
2 задачи
DS
Структура данных
Хеширование кукушки
Два гнезда на ключ, поиск — не больше двух проб; вставка выселяет жильцов. Работает до заполнения 1/2, с корзинами — до 98 %.
поиск — не больше d проб в худшем; вставка — O(1) в среднем ниже порога
1 задача
DS
Структура данных
Фильтр Блума
Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент.
O(k)
2 задачи
SYS
Структура данных
LSM-дерево
Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым.
запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень
2 задачи
Задачи
Часто рядом
хеширование 3 базы данных 3 собеседования 3 в проде 3 безопасность 2 классика 2 хеш-таблица 1 массив 1 частоты 1 граф 1 случайность 1 вероятностная структура 1