Идеальное хеширование — различия между версиями
Rybak (обсуждение | вклад) |
Kabanov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | {{Определение | ||
| + | |definition= | ||
'''Идеальная хеш-функция''' {{---}} [[Хеш-таблица#Хеширование|хеш-функция]], которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex>O(1)</tex> времени. | '''Идеальная хеш-функция''' {{---}} [[Хеш-таблица#Хеширование|хеш-функция]], которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex>O(1)</tex> времени. | ||
| + | }} | ||
| + | == Основная идея == | ||
| + | Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне. | ||
| + | === Первый уровень === | ||
| + | Используется тот же принцип, что и в случае хеширования с цепочками: n ключей хешируются в m ячеек с использованием хеш-функции h, выбранной из семейста универсальных хеш-функций. | ||
| + | Сама хеш-функция будет иметь вид h(k) = ((a*k+b) mod p). | ||
| + | === Второй уровень === | ||
| + | На данном уровне будет использовать вторичную хеш-таблицу S_j со своей функций h_j. S_j будет хранить все ключи, хешированные в ячейку j. Соответственно, хеш-функция будет вида h_j((a_j*k+b_j) mod p) mod m_j. | ||
| + | Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер m_j хеш-таблицы S_j был равен квадрату числа n_j ключей, хешированных в ячейку j. | ||
| + | {{Теорема | ||
| + | |statement= | ||
| + | Если n ключей сохраняются в хеш-таблице размеров m=n^2 c использованием хеш-функции h, случайно выбранный из универсального множества хеш-функций, то вероятность возникновения коллизий не превыщает 1/2. | ||
| + | |proof= | ||
| + | }} | ||
==См. также== | ==См. также== | ||
* [[Хеширование]] | * [[Хеширование]] | ||
Версия 21:15, 9 июня 2013
| Определение: |
| Идеальная хеш-функция — хеш-функция, которая без коллизий отображает различные элементы из множества объектов на множество ключей за времени. |
Основная идея
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
Первый уровень
Используется тот же принцип, что и в случае хеширования с цепочками: n ключей хешируются в m ячеек с использованием хеш-функции h, выбранной из семейста универсальных хеш-функций. Сама хеш-функция будет иметь вид h(k) = ((a*k+b) mod p).
Второй уровень
На данном уровне будет использовать вторичную хеш-таблицу S_j со своей функций h_j. S_j будет хранить все ключи, хешированные в ячейку j. Соответственно, хеш-функция будет вида h_j((a_j*k+b_j) mod p) mod m_j. Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер m_j хеш-таблицы S_j был равен квадрату числа n_j ключей, хешированных в ячейку j.
| Теорема: |
Если n ключей сохраняются в хеш-таблице размеров m=n^2 c использованием хеш-функции h, случайно выбранный из универсального множества хеш-функций, то вероятность возникновения коллизий не превыщает 1/2. |
