Расширяемое хеширование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники информации)
(не показаны 22 промежуточные версии 2 участников)
Строка 1: Строка 1:
'''Метод расширяемого хеширования''' (англ. ''extendable hashing'') заключается в том, что мы представляем хеш-таблицу в качестве нескольких групп, которые имеют определенное количество ячеек. При переполнении группы нам не требуется перехешировать всю таблицу, а лишь перехешировать заполненную группу, разделив ее при этом на две группы. Таким образом вся хеш-таблица никогда не будет полностью заполнена. К тому же при использовании данного метода использование памяти будет наиболее экономичным.
+
При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.
== Алгоритм ==
+
== Структура и алгоритм ==
Посмотрим, как работает алгоритм, на примере заполнения гипотетической хеш-таблицы. Первоначально в таблице имеется одна группа. Предположим, что каждая группа будет содержать 10 хеш-значений и номер записи каждого хеш-значения, чтобы ее можно было извлечь.
+
'''Метод расширяемого хеширования''' (англ. ''extendible hashing'') заключается в том, что хеш-таблица представлена как '''каталог''' (англ. ''directory''), а каждая ячейка будет указывать на '''емкость''' (англ. ''bucket'') которая имеет определенную '''вместимость''' (англ. capacity). Сама хеш-таблица будет иметь '''глобальную глубину''' (англ. ''global depth''), а каждая из емкостей имеет '''локальную глубину''' (англ. ''local depth''). Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы определить в какую емкость следует заносить значения. А из разницы локальной глубины и глобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой <tex>K = 2 </tex><sup><tex>G-L</tex></sup> где <tex>G</tex> — глобальная глубина, <tex>L</tex> — локальная глубина, а <tex>K</tex> количество ссылающихся ячеек. Для поиска емкости используется [[Wikipedia:Trie|цифровое дерево]].
  
Начнем вставлять в таблицу хеш-значения вместе с номерами их записей. При наличии только одной группы их можно вставить только в одно место, поэтому после 10 вставок группа заполняется. Разобьем заполненную группу на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом — в другую. Эти две группы имеют так называемую '''разрядную глубину''' (англ. ''bit—depth''), равную одному разряду. Теперь при каждой вставке пары хеш-значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда хеш-значения.
+
Теперь рассмотрим сам алгоритм если нам поступило некоторое значение:
 +
#Переводим значение в двоичный вид, смотрим на последние <tex>G</tex> битов и решаем в какую емкость отправить значение.
 +
#Если емкость имеет свободное место, то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости:
 +
##Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на <tex>1</tex>.  
 +
##Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две емкости и так далее.  
  
Со временем мы заполним еще одну группу. Предположим, что это группа, в которую мы вставляли все хеш-значения, завершающиеся 0. Снова разобьем группу на две отдельные группы. На этот раз все элементы, хеш-значения которых заканчиваются двумя нулевыми разрядами, т.е. 00, будут помещаться в первую группу, а завершающиеся разрядами 10 — во вторую группу. Обе группы имеют разрядную глубину, равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда хеш-значения. Теперь у нас имеются три группы: в первую вставляются элементы, завершающиеся разрядами 00, во вторую — разрядами 10, а в третью — просто 1.
+
==Пример==
 +
Рассмотрим алгоритм на примере.
  
Предположим, что мы продолжаем вставку и заполняем группу 10. Мы снова разбиваем заполненную группу на две и повторяем вставку ее элементов в две новые группы. На этот раз две новые группы будут принимать элементы, завершающиеся разрядами 010 и 110. Таким образом, теперь у нас имеются четыре группы: одна с разрядной глубиной, равной 1, в которую выполняется вставка хеш-значений, завершающихся 1, одна с разрядной глубиной равной 2, содержащая хеш-значения, которые завершаются разрядами 00, и две группы с разрядной глубиной, равной 3, которые предназначены для хеш-значений, завершающихся разрядами 010 и 110.
+
Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения <tex>9, 20, 26</tex> (смотри рисунок №1) где <tex>G</tex> — глобальная глубина, <tex>l1, l2, l3, l4</tex> — локальные глубины емкостей, а вместимость емкостей равна <tex>3</tex>.
  
Для поддержания отображения того, какие хеш-значения помещаются в те или иные группы, используется структура, называемая каталогом (англ. ''catalogue''). По существу каталог содержит список всех возможных окончаний групп и связных с ними номеров групп. Вместо того чтобы поддерживать какой—либо причудливый набор значений разрядной глубины и номеров групп, выбранный методом проб и ошибок, каталог поддерживает собственное значение разрядной глубины, равное максимальной разрядной глубине группы, и имеет ячейку для каждого значения этой разрядной глубины.
+
Первым на вход поступает значение <tex>9</tex>. Представим его в двоичном виде: <tex>9 = 8+1 = 1000+1 = 1001</tex>. Окончание <tex>01</tex> соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем <tex>9</tex> в нее (смотри рисунок №2). На этом работа с <tex>9</tex> закончена.  
  
В рассмотренном нами примере максимальная разрядная глубина группы была равна 3, поэтому разрядная глубина каталога также равна этому значению. Три разряда позволяют образовать восемь комбинаций разрядов: 000, 001, 010, 011, 100, 101, 110 и 111. Все комбинации, которые завершаются 1 (т.е. вторая, четвертая, шестая и восьмая), указывают на одну и ту же группу, принимающую элементы, хеш-значения которых завершаются 1. Аналогично, записи каталога для значений 000 и 100 указывают на одну и ту же группу, в которую помещаются элементы с хеш-значениями, завершающимися разрядами 00.
+
Далее на вход поступает значение <tex>20</tex>. Представим его в двоичном виде: <tex>20 = 16+4 = 10000+100 = 10100</tex>. Это значение оканчивается на <tex>00</tex> и должно пойти в первую емкость, но первая емкость полностью заполнена. Следовательно мы смотрим на локальную глубину первой емкости то есть на <tex>l1</tex>. <tex>l1 = G</tex> а значит следуя выше описанному алгоритму мы должны удвоить количество ячеек каталога, увеличить глобальную глубину, затем увеличить количество последних бит по которым мы раскидываем значения на <tex>1</tex> и перехешировать первую емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №3). На этом работа с <tex>20</tex> закончена.  
  
[[Файл:7_1.png|400px|мини|Вставка в расширяемую хеш-таблицу]]
+
Последним на вход поступает значение <tex>26</tex>. Представим его в двоичном виде: <tex>26 = 16+8+2 = 10000+1000+10 = 11010</tex>. Последние <tex>3</tex> бита (<tex>010</tex>) соответствуют третьей емкости, но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная глубина, а следовательно нам надо только перехешировать емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №4). На этом работа с <tex>26</tex> закончена.
 +
{|align="center"
 +
|-valign="top"
 +
|[[Файл:FirstStep.png|мини|250px|рисунок №1]]
 +
|[[Файл:SecondStep.png|мини|250px|рисунок №2]]
 +
|[[Файл:ThirdStep.png|мини|250px|рисунок №3]]
 +
|[[Файл:ForthStep.png|мини|250px|рисунок №4]]
 +
|}
  
===Примечание===
+
== Использование ==
 
+
Чаще всего расширяемое хеширование используется в базах данных так как. Базы данных могут быть крайне большими и перехеширование всей базы данных займет продолжительное время при этом лишая пользователей доступа к базе данных. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу базы данных. Также расширяемое хэширование хорошо работает в условиях динамически изменяемого набора записей в хранимом файле.
Однако эта схема не учитывает ряд особенностей. Две записи каталога, которые указывают на группу для элементов, хеш-значения которых завершаются разрядами 00, разделены тремя другими записями. Аналогично единственной группе, принимающей все элементы, хеш-значения которых завершаются 1, соответствуют четыре записи, равномерно распределенные по каталогу. При разбиении группы дополняющие друг друга группы не будут размещаться в каталоге по соседству. Для дальнейших рассуждений было бы проще предположить, что записи каталога, соответствующие одной группе, располагаются по соседству, чтобы при разбиении группы дополняющая первую группа помещалась непосредственно за ней.
 
 
 
Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога. Так, например, если хеш-значение завершается разрядами 001, при поиске мы обратимся не к записи 001 каталога, а к записи 100 (4, которая соответствует инвертированному значению 001). В результате использование каталога значительно упрощается. В нашем примере хеш-значения, которые завершаются разрядами 00, помещаются в запись каталога 000 (0) или 001 (1). Хеш-значения, которые завершаются разрядами 010, помещаются в запись каталога 010 (2). Хеш-значения, которые завершаются разрядами 011, помещаются в запись каталога 011 (3). И, наконец, хеш-значения, которые завершаются разрядом 1, помещаются в записи 100, 101, 110 или 111 (4, 5, 6, 7).
 
 
 
===Визуализация===
 
 
 
Вернемся немного назад, и вставим элементы в пустую хеш-таблицу, как это было сделано ранее. Выполняемые при этом действия показаны на рис. Мы начинаем с каталога только с одной записью с индексом 0 (a). Принято считать, что в подобной ситуации разрядная глубина равна 0. Мы заполняем единственную группу (назовем ее  <tex> A </tex> ) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до 1. Иначе говоря, теперь он будет содержать две записи (b). В результате будут созданы две группы, на первую из которых указывает запись 0 (исходная запись  <tex> A </tex> ), а на вторую — запись 1,  <tex> B </tex>  (c). Все элементы, хеш-значения которых завершаются разрядом 0, помещаются в группу  <tex> A </tex> , а остальные — в группу  <tex> B </tex> . Снова заполним группу  <tex> A </tex> . Теперь разрядную глубину каталога необходимо увеличить с 1 до 2, чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога 00 и 01 будут указывать на исходную группу  <tex> A </tex> , а записи 10 и 11 — на группу  <tex> B </tex>  (d). Группа  <tex> A </tex>  разбивается на группу, которая принимает хеш-значения с окончанием 00 (снова  <tex> A </tex> ), и группу, которая принимает хеш-значения с окончанием 10,  <tex> C </tex> . На группу  <tex> A </tex>  будет указывать запись 00 каталога, а на группу  <tex> C </tex>  — запись 01 (e). И, наконец, группа  <tex> C </tex>  (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядов.
 
 
== См. также ==
 
== См. также ==
 
*[[Хеш-таблица]]
 
*[[Хеш-таблица]]
Строка 33: Строка 38:
 
*Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
 
*Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
 
*Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
 
*Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
[[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]
+
*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Хеширование]]

Версия 10:51, 7 июня 2015

При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.

Структура и алгоритм

Метод расширяемого хеширования (англ. extendible hashing) заключается в том, что хеш-таблица представлена как каталог (англ. directory), а каждая ячейка будет указывать на емкость (англ. bucket) которая имеет определенную вместимость (англ. capacity). Сама хеш-таблица будет иметь глобальную глубину (англ. global depth), а каждая из емкостей имеет локальную глубину (англ. local depth). Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы определить в какую емкость следует заносить значения. А из разницы локальной глубины и глобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой [math]K = 2 [/math][math]G-L[/math] где [math]G[/math] — глобальная глубина, [math]L[/math] — локальная глубина, а [math]K[/math] количество ссылающихся ячеек. Для поиска емкости используется цифровое дерево.

Теперь рассмотрим сам алгоритм если нам поступило некоторое значение:

  1. Переводим значение в двоичный вид, смотрим на последние [math]G[/math] битов и решаем в какую емкость отправить значение.
  2. Если емкость имеет свободное место, то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости:
    1. Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на [math]1[/math].
    2. Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на [math]1[/math], удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две емкости и так далее.

Пример

Рассмотрим алгоритм на примере.

Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения [math]9, 20, 26[/math] (смотри рисунок №1) где [math]G[/math] — глобальная глубина, [math]l1, l2, l3, l4[/math] — локальные глубины емкостей, а вместимость емкостей равна [math]3[/math].

Первым на вход поступает значение [math]9[/math]. Представим его в двоичном виде: [math]9 = 8+1 = 1000+1 = 1001[/math]. Окончание [math]01[/math] соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем [math]9[/math] в нее (смотри рисунок №2). На этом работа с [math]9[/math] закончена.

Далее на вход поступает значение [math]20[/math]. Представим его в двоичном виде: [math]20 = 16+4 = 10000+100 = 10100[/math]. Это значение оканчивается на [math]00[/math] и должно пойти в первую емкость, но первая емкость полностью заполнена. Следовательно мы смотрим на локальную глубину первой емкости то есть на [math]l1[/math]. [math]l1 = G[/math] а значит следуя выше описанному алгоритму мы должны удвоить количество ячеек каталога, увеличить глобальную глубину, затем увеличить количество последних бит по которым мы раскидываем значения на [math]1[/math] и перехешировать первую емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №3). На этом работа с [math]20[/math] закончена.

Последним на вход поступает значение [math]26[/math]. Представим его в двоичном виде: [math]26 = 16+8+2 = 10000+1000+10 = 11010[/math]. Последние [math]3[/math] бита ([math]010[/math]) соответствуют третьей емкости, но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная глубина, а следовательно нам надо только перехешировать емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №4). На этом работа с [math]26[/math] закончена.

рисунок №1
рисунок №2
рисунок №3
рисунок №4

Использование

Чаще всего расширяемое хеширование используется в базах данных так как. Базы данных могут быть крайне большими и перехеширование всей базы данных займет продолжительное время при этом лишая пользователей доступа к базе данных. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу базы данных. Также расширяемое хэширование хорошо работает в условиях динамически изменяемого набора записей в хранимом файле.

См. также

Источники информации

  • Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
  • Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
  • Wikipedia — Extendible hashing