Хеширование (29 апреля)

  1. Антихеш тесты
    1. Строчка Туэ-Морса (__builtin_popcount(i) mod 2, или рекурсивно: Sn = Sn-1 + not Sn-1). Оценка длины строки, чтобы была коллизия.
    2. Тест против (P,MOD)-хеша
    3. Что делать? Выбирать случайную точку P или случайный простой MOD! Лучше P.
    4. Lm: если (P,MOD) фиксировано, MOD простое, мы берём случайный многочлен, то вероятность, что P − корень, равна 1/MOD
    5. Lm: если многочлен и MOD фиксированы, MOD простое, мы берём случайное P, то вероятность, что P − корень, ≤ degree/MOD
    6. Lm: если многочлен MOD фиксирован, MOD простое, мы берём случайное P и случайный многочлен, то вероятность, что P − корень равна 1/MOD
  2. Время работы хеш-таблицы на списках
    1. Хеш-таблица со списком, хеш-таблица с открытой адресацией
    2. Матожидание средней длины списка.
    3. Матожидание максимальной длины списка. Доказательство.
    4. Двойное хеширование для списков. Матожидание максимальной длины списка. Набросок доказательства.
    5. Двойное хеширование для открытой адресации. Оценка?!
    6. [не успеем] Хеширование кукушки.
  3. Совершенное хеширование
    1. Определение
    2. Построение: space = O(n2), time = O(n)
    3. 2-Level: space = O(n), time = O(n)
  4. Фильтр Блюма.
    1. Алгоритм с односторонней ошибкой, интерфейс: add, isAdded.
    2. Оценка вероятности ошибки [wiki]
  5. [не успеем] Универсальное семейство хеш-функций (Carter, Wegman, 1977)
    1. Принцип: выбирать случайную хеш-функцию из ``хорошего'' семейства
    2. Опеределение: ∀ x, y : Prh ∈ H (h(x) = h(y)) ≤ 1/m. Свойства равномерной разности: h(x)-h(y) равномерно.
    3. Пример: fix m, p > m ⇒ H = {x → (ax+b) mod p mod m}. |H| = p(p-1). Доказательство.