Уявімо, що перед нами стоїть класичне завдання отримати дані по якомусь ключу. Причому кількість даних та їх ключів заздалегідь відома.
Як вирішувати подібну задачу?
Якщо кількість пар ключ-значення завідомо невелика, то буває сенс просто захардкодити. Але якщо таких значень багато мільйонів?
Можна просто перебором пройтися за списком поки не зустрінеться потрібне значення ключа. Але тоді складність буде лінійна O (N), що, в даному випадку, має засмутити будь-якого інженера. А яка складність алгоритму тоді потрібна? Яка не залежить від кількості даних і виконується за фіксований час, тобто з костянтною складністю O (1).
Як можна отримувати дані за фіксований час?
Хешування
Якщо розташувати дані в пам'яті послідовно, то знаючи зсув, де знаходиться необхідна інформація, можна отримувати доступ, який не буде залежати від початкової кількості даних.
Іншими словами, нам треба знайти спосіб перетворювати ключ на зсув, де будуть знаходитися дані. Зміщення - це просто ціле число: [0, n - 1], де n - кількість значень, що зберігаються.
На допомогу приходять хеш-функції, завдання яких якраз полягає в перетворенні ключів на цілі числа. Такі числа можуть бути інтерпретовані як зсув, за яким зберігають дані.
Але, на жаль, хеш-функції породжують колізії, тобто два різних ключа можуть давати однакове зміщення.
Виходячи із завдання, у нас фіксована і заздалегідь відома кількість даних, що дає можливість уникнути подібних проблем.
Ідеальне хешування
Ідеальна хеш-функція (Perfect Hash Function) - це така хеш-функція, яка перетворює заздалегідь відому статичну безліч ключів на діапазон цілих чисел [0, m - 1] без колізій, тобто один ключ відповідає тільки одному унікальному значенню. А якщо кількість результуючих значень така ж як і кількість вхідних ключів, така функція називається Мінімальною Ідеальною Хеш-функцією (Minimal Perfect Hash Function).
Розглянемо приклад мінімальної ідеальної хеш-функції заснованої на випадкових графах.
Давайте пофантазуємо і уявимо, що кожен ключ відповідає одному унікальному ребру, і, відповідно, двох вершин.
Тоді ключ може бути представлений у вигляді такого примітивного графа:
Ріс 1. Граф, де ребро відповідає ключу і описується через дві вершини.
Оскільки ключ представлений у вигляді ребра, а ребро завжди з'єднує як мінімум (тому що бувають ще гіперграфи) дві вершини, значить шукана функція може виглядати приблизно так:
h(key) = g(node1, node2)
де h (key) - це мінімальна ідеальна хеш-функція, значення якої описує ребро, key - ключ, g () - якась поки невідома функція залежна від вершин графа node1 і node2. Оскільки вони повинні залежати від ключа, то виходить
h(key) = g(f1(key), f2(key))
По суті для f1 і f2 можна вибрати будь-які хеш-функції, які будуть застосовуватися для одного ключа.
Залишилося визначити невідому функцію g (), яка описує взаємозв'язок двох вузлів f1 (key), f2 (key) і ребро.
Ось тут починаються фокуси
Для простоти визначимо значення ребра як суму значень вузлів, що з'єднуються цим руба.
Так як ребро відповідає лише одному ключу, то це і є шукане значення, результат мінімальної ідеальної функції.
h(key) = (g1(f1(key)) + g2(f2(key))) mod m
де h (key) - це значення ребра, f1 (key) - це перший вузол графа, g1 () - значення цього вузла, f2 (key) - другий вузол, g2 () - значення другого вузла, m - кількість ребер.
Якщо ще простіше, то
значення мінімальної ідеальної функції = (значення вузла 1 + значення вузла 2) mod кількість ребер.
Ріс 2. Перегляд одного ключа у графі.
Іншими словами, щоб визначити номери вузлів використовується хеш-функції, і часто бувають колізії, тому один вузол може містити безліч ребер.
Рис 3. Колізії в хеш-функціях породжують кілька ребер на одній вершині. Так само вершини одного ключа можуть не поєднуватися з вершинами іншого ключа.
Ось де сіль
Визначившись як взаємопов'язані вузли графа з їх ребрами, ми спершу визначаємо значення ребер h (key) (це просто інкрементний індекс), які будуть свідомо унікальні, а потім підбираємо значення вузлів.
Наприклад, значення подальшого вузла можна порахувати так:
g2(f2(key)) = h(key) — g1(f1(key))
або
значення вузла 2 = значення ребра - значення вузла 1
Залишилося тільки пройтися по графу, взяти 0 за початкове значення першого вузла підграфа і порахувати всі інші.
На жаль, даний підхід не працює якщо граф вийшов зацикленим. Оскільки немає способу заздалегідь гарантувати незацікленість графа, то в разі виявлення зацикленості доведеться перерисувати граф з іншими хеш-функціями.
Зациклінність найкраще перевіряти видаленням вершин з тільки одним руба. Якщо вершини залишаться, то граф зациклений.
На простому прикладі
Тепер прийшла черга описати сам алгоритм на прикладі.
Завдання: Є безліч ключів, що складаються з назв 12 місяців. Необхідно створити мінімальну ідеальну хеш-функцію, де кожного місяця транслюється лише одне унікальне ціле число в діапазоні [0, 11].
1. Проходимо по всіх ключах і додаємо вершини і ребра. Для цього вибираємо дві хеш-функії f1 і f2.
Наприклад:
Для ключа jan отримуємо номер першого вузла f1 (jan):= 4 і номер другого вузла f2 (jan):= 13
Для ключа feb, f1 (feb):= 0, f2(feb) := 17
і так далі.
2. Перевіряємо чи вийшов граф зацикленим, якщо так, то повторюємо крок № 1 заново і при цьому змінюємо хеш функції f1/f2.
Ймовірність появи циклу у графі залежить від кількості можливих вершин. Тому введемо поняття як фактор розміру графа. Кількість вузлів визначається як:
m = c * n
де m - кількість вузлів у графі, з - костянтний фактор розміру, n - кількість ключів.
3. У разі успішного створення незацікленого графа, треба пройтися по всіх вузлах і порахувати їх значення за формулою
g2(f2(key)) = h(key) — g1(f1(key))
або
значення дочірнього вузла = індекс ребра - значення вузла предка
Наприклад, присвоюємо вузлу з номером 0 значення 0 і йдемо по його ребру з індексом 6:
g2 (13) = 6 - 0 = 6, вузол з номером 13 отримує значення 6 тощо.
В результаті маємо такий граф.
Рис 4. Результуючий граф, де ключами виступають імена місяців і використані випадкові хеш-функції для отримання номерів вершин. Числа біля вузлів є значення вузла.
Лукап
Припустимо нам треба отримати унікальний індекс за ключем sep.
Використовуємо ті ж хеш-функції, які були використані для створення графа:
f1(sep) := 17
f2(sep) := 9
Отримавши номери вершин, складаємо їх значення:
h(sep) = (g(17) + g(9)) mod 12 = (1 + 7) mod 12 = 8
Цей алгоритм називається CHM і реалізований в бібліотеці CMPH.
І як можна переконатися, створення хеш-таблиці має лінійну складність O (N), а пошук індексу за ключем - костянтну O (1).
Післямова
А ви пам'ятаєте бородате завдання від гугл?
Як скопіювати однонапрямований список за лінійний час, якщо вузол списку виглядає так?
struct list_node
{
list_node* next;
list_node* random;
};
І рішення передбачалося схилювати вузли, щоб по дві копії вузла було підряд, а потім розділити цей списк з копіями нід на два списки, в кожному за копією. У підсумку складність виходить лінійна.
А тепер уявіть у вашому розташуванні мінімальна ідеальна хеш-функція, яка може зберегти за покажчиком його індекс у списку і за індексом зберігати покажчик. І вирішити завдання можна буде так:
1. Проходимо список, отримуємо масив покажчиків нод та їх індекс.
2. Створюємо мінімальні ідеальні хеш-функції для покажчиків нод.
3. Створюємо новий список, отримуємо масив індексів нод та їх індексів.
4. Створюємо інші ідеальні функції для індексів другого списку, щоб за індексом отримати адресу.
5. Проходимо новий список, і отримуємо адресу старої ноди, по ньому отримуємо індекс, а по другій хеш-функції отримуємо адресу вже в другому списку за індексом.
У підсумку список буде скопійовано за лінійний час.
Хоча, звичайно, ідея продублювати ноди і розділити потім на два списки, красивіше і швидше.
Дякую за зусилля.
Почитати
1. Z.J. Czech, G. Havas, and B.S. Majewski. An optimal algorithm for generating minimal perfect hash functions., Information Processing Letters, 43(5):257-264, 1992.
2. Minimal Perfect Hash Functions — Introduction.
3. mphf - Моя реалізація CHM на C++.