хеширование

Статьи

DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных Хеширование кукушки Два гнезда на ключ, поиск — не больше двух проб; вставка выселяет жильцов. Работает до заполнения 1/2, с корзинами — до 98 %.

поиск — не больше d проб в худшем; вставка — O(1) в среднем ниже порога

1 задача DS Структура данных Фильтр Блума Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент. O(k) 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача STR Алгоритм LZ77 и LZW Повторы — ссылками назад (LZ77) или номерами фраз растущего словаря (LZW); хеш-цепочки, уровни, окно. O(n · chain) 2 задачи PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача SYS Алгоритм Рандеву-хеширование Каждый ключ уходит к серверу с наибольшим хешем пары «ключ, сервер»: равномерно, без таблиц, отказ сдвигает только ключи упавшего. O(N) на ключ 2 задачи SYS Структура данных Count-Min Sketch Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх. O(d) на элемент и на запрос 2 задачи SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи SYS Структура данных Дерево Меркла Хеши хешей: отпечаток всего набора, поиск расхождений за несколько сравнений и доказательство из log n хешей. O(n) на построение, O(log n) на доказательство и его проверку 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи SYS Алгоритм Два случайных выбора Спросить двух случайных и выбрать менее занятого: самая полная корзина — ln ln n вместо ln n / ln ln n. O(d) на решение: узнать нагрузку d серверов 2 задачи SYS Алгоритм Алгоритм rsync Передаёт только изменённые куски файла: суммы блоков туда, новые байты обратно; блоки находятся на любом смещении.

O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой

2 задачи ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи RND Приём Лас-Вегас и Монте-Карло Всегда верный, но иногда долгий против всегда быстрого, но иногда неверного — и как превратить одно в другое. O(k · стоимость одной попытки) 2 задачи TEC Приём Предподсчёт и таблицы Посчитать ответы заранее и брать из таблицы: CRC-32 байтом за шаг вместо бита и где таблица перестаёт помогать. O(размер таблицы) один раз, затем O(1) на запрос 1 задача

Задачи

Две книги на сертификат CRC по строкам Анаграммы Толстого Две оценки Дуплеты Кэрролла Кластеры на карте эпицентров Одинаковые куски Определитель языка Пароль из утечки Пары ближе r Пары из корзин Пары реплик Сверка реплик Свёрнутые стеки Старые блоки в новом файле Взломать хеш Гнёзда кукушки Две ячейки Мосты и тоннели Наивные веса Проверка доказательства Самый длинный общий кусок Словарь опечаток Фильтр учится на ходу Замок с двумя ключами

Часто рядом

в проде 14 собеседования 11 классика 8 случайность 7 вероятностная структура 6 базы данных 5 безопасность 4 скетч 4 потоковая обработка 4 распределённые системы 4 есть ли элемент 3 скользящее окно 3