Редактирование: Идеальное хеширование

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
{{Определение
+
'''Двойное хеширование''' {{---}} метод борьбы с возникающими коллизиями при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], в котором хеш-таблица заполняется равномерней чем при [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейном разрешении коллизий]] коллизий, что способствует уменьшению размеров кластеров.
|definition=
 
'''Идеальная хеш-функция''' (англ. ''perfect hash function'') — [[Хеш-таблица#Хеширование|хеш-функция]], которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex>O(1)</tex> времени в худшем случае.
 
}}
 
  
== Основная идея ==
+
==Принцип двойного хеширования==
Идеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.
+
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> это наш ключ, <tex> m </tex> размер нашей таблицы, <tex> \mod m </tex> это остаток от деления на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) +  h_2(k)) \mod m </tex>, затем <tex> (h_1(k) +  2 \cdot h_2(k)) \mod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) +  i \cdot h_2(k)) \mod m </tex> где <tex>  i = (0, 1, \; ... \;, m - 1) </tex>
  
В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.
+
==Выбор хеш-функций==
 +
<tex> h_1 </tex> может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, <tex> h_2 </tex> должна возвращать значения:
 +
*не равные <tex> 0 </tex>
 +
*независимые  от <tex> h_1 </tex>
 +
*взаимно простые с величиной хеш-таблицы
  
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
+
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </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>p</tex> — простое число, превышающее <tex>m</tex>.
 
  
=== Второй уровень ===
+
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \mod (m-1) + 1 </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>O(n)</tex>.
+
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
  
== Теоретическое обоснование ==
+
==Пример==
  
{{Теорема
+
Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:
|statement=
 
Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий не превышает  <tex dpi="180">{1 \over 2}</tex>.
 
|proof=
 
Всего имеется <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 2} \cdot {1 \over n^2} < {1 \over 2}</tex>
 
}}
 
Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица#Введение | парадокса дней рождения]] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
 
  
{{Теорема
+
<center>
|statement=
+
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod 13 </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>.
+
</center>
|proof=
 
<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>
 
  
Первый переход в равенстве мы совершили благодаря формуле <tex>a^2 = a + 2\cdot\dbinom{a}{2}</tex>. Далее мы воспользовались свойствами [[Математическое_ожидание_случайной_величины | математического ожидания]], в частности - линейности.
+
<center>
 +
<tex> h_1(k) = k \mod 13 </tex>
 +
</center>
  
Очевидно, что <tex>\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}</tex> - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает
+
<center>
<tex dpi="180">\binom{n}{2}{1 \over m} = {n(n-1) \over 2m} = {n-1 \over 2}</tex>
+
<tex> h_2(k) = 1 + k \mod 11 </tex>
А так как <tex>m = n</tex>, то
+
</center>
<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 следствия из этой теоремы.
 
  
{{Теорема
+
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
|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>, ч.т.д.
+
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
  
}}
+
==Простая реализация==
 +
Пускай у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> h_1(key)</tex> и <tex> h_2(key) </tex>
  
{{Теорема
+
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex> состоящая из объектов типа <tex> item </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>.
+
===Вставка===
 +
<pre>insert(item){
 +
  x = h1(item.key)
 +
  y = h2(item.key)
 +
  for (i = 0; i < m; i++){   
 +
      if (table[x] == null){
 +
        table[x] = item
 +
        return
 +
      }
 +
      x = (x + y) mod m
 +
  }
 +
  error() //ошибка, требуется увеличить размер таблицы
 +
}</pre>
  
Тогда <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>, ч.т.д.
+
===Поиск===
}}
+
<pre>contains(key){
 +
  x = h1(key)
 +
  y = h2(key)
 +
  for (i = 0; i < m; i++){  
 +
      if (table[x] != null)
 +
        if (table[x].key == key)
 +
            return table[x]
 +
      else
 +
        return null
 +
      x = (x + y) mod m
 +
  }
 +
  return null
 +
}</pre>
 +
 
 +
==Реализация с удалением==
 +
Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
 +
 
 +
===Вставка===
 +
<pre>insert(item){
 +
  x = h1(item.key)
 +
  y = h2(item.key)
 +
  for (i = 0; i < m; i++){   
 +
      if (table[x] == null || deleted[x]){
 +
        table[x] = item
 +
        deleted[x] = false
 +
        return
 +
      }
 +
      x = (x + y) mod m
 +
  }
 +
  error() //ошибка, требуется увеличить размер таблицы
 +
}</pre>
 +
 
 +
===Поиск===
 +
<pre>contains(key){
 +
  x = h1(key)
 +
  y = h2(key)
 +
  for (i = 0; i < m; i++){  
 +
      if (table[x] != null)
 +
        if (table[x].key == key && !deleted[x])
 +
            return table[x]
 +
      else
 +
        return null
 +
      x = (x + y) mod m
 +
  }
 +
  return null
 +
}</pre>
 +
 
 +
===Удаление===
 +
<pre>remove(key){
 +
  x = h1(key)
 +
  y = h2(key)
 +
  for (i = 0; i < m; i++){
 +
      if (table[x] != null)
 +
        if (table[x].key == key)
 +
            deleted[x] = true
 +
      else
 +
        return
 +
      x = (x + y) mod m
 +
  }
 +
}</pre>
  
 
==См. также==
 
==См. также==
 
* [[Хеширование]]
 
* [[Хеширование]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Разрешение коллизий]]
+
* [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешировании]]
 +
 
 +
== Литература ==
 +
* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''
 +
* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''
 +
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''
 +
* Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''
  
==Источники информации==
+
==Ссылки==
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308
+
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia: Double_hashing]
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
+
* [http://rain.ifmo.ru/cat/view.php/vis/hashtables/hash-2001-2 Пример хеш таблицы]
* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — Perfect hash function]
+
* [http://research.cs.vt.edu/AVresearch/hashing/double.php Пример хеш таблицы с двойным хешированием]
* [http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0215.pdf Universal and Perfect Hashing]
 
* [http://nord.org.ua/static/course/algo_2009/lecture8.pdf Универсальное хэширование. Идеальное хэширование]
 
  
 
[[Категория:Дискретная математика и алгоритмы]]  
 
[[Категория:Дискретная математика и алгоритмы]]  
 
[[Категория:Хеширование]]
 
[[Категория:Хеширование]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: