Изменения

'''Идеальная хеш-функция''' {{---}} (англ. ''perfect hash function'') — [[Хеш-таблица#Хеширование|хеш-функция]], которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex>O(1)</tex> временив худшем случае.

== Практический смысл Основная идея ==Задача идеального хеширования возникает тогдаИдеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, когда возникает необходимость проверять наличие элемента (скажемкак все ключи сохранены в таблице, слова из словаряих множество никогда не изменяется) за гарантировано константное времядля обеспечения хорошей асимптотики даже в худшем случае. При этом подразумеваетсямы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно. В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что набор делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных , в таблице статичен либо изменяется очень редкоалгоритмах со статической (известной заранее) информацией.

Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>h(k) = ((a\cdot k+b) \bmod p) \bmod m</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций.Сама хеш-функция будет иметь вид ]] <tex>H_{p,m}</tex>, где <tex>h(k) = ((a*k+b) \mod p)</tex> — простое число, превышающее <tex>m</tex>. 

На данном уровне будет вместо создания списка ключей будем использовать вторичную хеш-таблицу <tex>S_j</tex> , хранящую все ключи, хешированные функцией <tex>h</tex> в ячейку <tex>j</tex>, со своей функций функцией <tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>, выбранной из множества <tex>H_{p,m_j}</tex>. Путем точного выбора хеш-функции <tex>h_j</tex>мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> будет хранить все ключибыл равен квадрату числа <tex>n_j</tex> ключей, хешированные хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>. Соответственно Несмотря на квадратичную зависимость, ниже будет показано, что при корректном выборе хеш-функция функции первого уровня количество требуемой для хеш-таблицы памяти будет вида <tex>h_j(O(a_j*k + b_jn) \mod p) \mod m_j</tex>.<br> == Теоретическое обоснование ==

Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбранный выбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то вероятность возникновения [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.

Всего имеется <tex>\dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций ]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> - — [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание ]] числа коллизий равно<tex>E[X] = </tex> <tex dpi="180"> \binom{n}{2} * \cdot {1 \over n^2} = {n^2-n \over n2} * \cdot {1 \over n^2} < {1 \over 2}</tex>Это является очень хорошим результатом, если хотя бы вспомнить на примере [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#.D0.92.D0.B2.D0.B5.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5 парадокса дней рождения] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.

Как видно Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица#Введение | парадокса дней рождения]] о том, что вероятность возникновения коллизийрастет крайне быстро по сравнению с размером хеш-таблицы.== Метод №2 ==Будем использовать <tex>O(n)</tex> памяти.

Если мы сохраняем <tex>n</tex> ключей в хеш-таблице в хеш-таблице размеров <tex>m=n</tex> c использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из универсального множества хеш-функций, то <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</tex> - — количество ключей, хешированных в ячейку <tex>j</tex>.

<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} (\dbinom{n_j }{2)}\right]= </tex> <tex> E\left[n\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = n + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2} \right]</tex> Первый переход в равенстве мы совершили благодаря формуле <brtex>a^2 = a + 2\cdot\dbinom{a}{2}</tex>. Далее мы воспользовались свойствами [[Математическое_ожидание_случайной_величины | математического ожидания]], в частности - линейности.

<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \leqslant </tex> <tex dpi="150"> n + 2*\cdot {n-1 \over 2} = 2n - 1 < 2n</tex>, ч.т.д.}}Теперь выведем 2 следствия из этой теоремы. {{Теорема|statement=Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размером <tex>m=n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2</tex> <tex>(j=0,1,...,m-1)</tex>, то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает <tex>2n</tex>.|proof=Поскольку <tex>m_j=n_j^2</tex> для <tex>j=0,1,...,m-1</tex>, согласно предыдущей теореме: <tex>E\left[\displaystyle \sum_{j=0}^{m-1} m_j \right] = E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, ч.т.д. }} {{Теорема|statement=Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размером <tex>m=n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2</tex> <tex>(j=0,1,...,m-1)</tex>, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее <tex>4n</tex>, меньше чем <tex dpi="180">{1 \over 2}</tex>.|proof=Применим [[Неравенство Маркова| неравенство Маркова]] <tex>P(X \geqslant t) \leqslant E[X]/t</tex> Пусть <tex>X=\displaystyle \sum_{j=0}^{m-1} m_j</tex> и <tex>t=4n</tex>. Тогда <tex>P \left \{\displaystyle \sum_{j=0}^{m-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{j=0}^{m-1} mj\right]</tex> <tex dpi="150"> {1 \over 4n} < </tex> <tex dpi="150">{2n \over 4n} = {1 \over 2}</tex>, ч.т.д.

==СсылкиИсточники информации==* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — Perfect hash function {{---}} Wikipedia]