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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Метод расширяемого хеширования''' (''extendable hashing'') представляет собой изящный вариант осн...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Метод расширяемого хеширования''' (''extendable hashing'') представляет собой изящный вариант основного метода хеширования, позволяющий устранить проблемы хеширования при увеличении размеров хешированного файла (увеличение количества коллизий и среднего времени доступа). В действительности, расширяемое хеширование гарантирует, что количество операций доступа к диску, необходимых для поиска определенной записи, никогда не превышает двух и обычно сводится только к одной операции, независимо от того, какого размера достигает сам файл. (Поэтому данный метод гарантирует также, что никогда не возникнет потребность в реорганизации файла.)
+
При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.
 +
== Структура и алгоритм ==
 +
'''Метод расширяемого хеширования''' (англ. ''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|цифровое дерево]].
  
'''Примечание''': В этой схеме расширяемого хеширования значения хешированного поля должны быть уникальными, а такое условие, разумеется, будет соблюдено, если данное поле фактически является первичным ключом.
+
Теперь рассмотрим сам алгоритм если нам поступило некоторое значение:
== Схема хеширования ==
+
#Переводим значение в двоичный вид, смотрим на последние <tex>G</tex> битов и решаем в какую емкость отправить значение.
# Допустим, что основной функцией хеширования является h, а значение первичного ключа некоторой конкретной записи r равно к. Хеширование значения к (т.е. вычисление выражения h(к)) приводит к получению значения s, называемого псевдоключом (pseudokey) записи к. Псевдоключи не интерпретируются непосредственно как адреса, а вместо этого применяются для косвенного поиска адресов хранения, как описано ниже.
+
#Если емкость имеет свободное место, то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости:
# Файл имеет связанный с ним каталог, который также хранится на диске. Каталог состоит из заголовка, содержащего значение d (сокращение от depth — глубина каталога), наряду с 2<sup>d</sup> указателями. Указатели указывают на страницы с данными, содержащими фактические записи (на каждой странице имеется много записей). Таким образом, каталог с глубиной d позволяет управлять файлом с максимальным размером, составляющим 2<sup>d</sup> отдельных страниц с данными.[[Файл:Deit vvedenie v DB 8e.jpg|мини| Пример применения способа расширяемого хеширования]]
+
##Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на <tex>1</tex>.
# Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака b, то i-й указатель в каталоге (1 < i < 2<sup>d</sup>) указывает на страницу, содержащую все записи, для которых b принимает значение i-l. Иными словами, первый указатель указывает на страницу, содержащую все записи, для которых b состоит из одних нулей, второй указатель указывает на страницу, для которой b равно 0. .. 01, и т.д. (Обычно все эти 2<sup>d</sup> указателя не являются различными; это означает, что количество различных страниц с данными, как правило, меньше чем 2<sup>d</sup>, как показано на рис.) Поэтому, чтобы найти запись, имеющую значение первичного ключа к, необходимо хешировать к для определения псевдоключа s и взять первые d битов этого псевдоключа; если эти биты имеют числовое значение i-l, осуществляется переход к i-му указателю в каталоге (первая операция доступа к диску) и переход по этому указателю к странице, содержащей требуемую запись (вторая операция доступа к диску). '''Примечание''': На практике этот каталог обычно остается достаточно небольшим для того, чтобы его можно было почти все время хранить в оперативной памяти. Поэтому упомянутые "две" операции доступа к диску обычно сводятся к одной.
+
##Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две емкости и так далее.  
#Каждая страница с данными имеет также заголовок, указывающий локальную глубину р этой страницы (р < d). Предположим, например, что d равно 3 и первый указатель в каталоге (указатель 000) указывает на страницу, для которой локальная глубина р равна 2. В данном случае локальная глубина 2 означает, что эта страница содержит не только все записи с псевдоключами, начинающимися с 000, но и содержит все записи с псевдоключами, начинающимися с 00 (т.е. теми, которые начинаются с 000, а также теми, которые начинаются с 001). Иными словами, указатель каталога 001 также указывает на эту страницу (см. рис).
+
 
#Теперь предположим, что страница с данными 000 заполнена и нужно вставить новую запись, имеющую псевдоключ, который начинается с 000 (или с 001). В этот момент указанная страница разделяется на две; это означает, что из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется таким образом, чтобы он указывал на новую страницу (указатель 000 все еще указывает на старую страницу). Локальная глубина р для каждой из этих двух страниц теперь будет равна 3, а не 2.
+
==Пример==
#Теперь допустим, что страница с данными, соответствующая начальной строке битов 000, снова заполняется и должна быть опять разделена. Существующий каталог не позволяет обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже равна глубине каталога. Поэтому размер каталога удваивается; это означает, что значение d увеличивается на единицу и каждый указатель заменяется парой смежных, идентичных указателей. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой странице, а записи 0001 перемещаются на новую страницу; первый указатель в каталоге остается неизменным (т.е. по-прежнему указывает на старую страницу), а второй указатель корректируется таким образом, чтобы он указывал на новую страницу. Следует отметить, что операция удваивания размера каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с данными.
+
Рассмотрим алгоритм на примере.
 +
 
 +
Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения <tex>9, 20, 26</tex> (смотри рисунок №1) где <tex>G</tex> — глобальная глубина,  <tex>l1, l2, l3, l4</tex> — локальные глубины емкостей, а вместимость емкостей равна <tex>3</tex>.
 +
 
 +
Первым на вход поступает значение <tex>9</tex>. Представим его в двоичном виде: <tex>9 = 8+1 = 1000+1 = 1001</tex>. Окончание <tex>01</tex> соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем <tex>9</tex> в нее (смотри рисунок №2). На этом работа с <tex>9</tex> закончена.  
 +
 
 +
Далее на вход поступает значение <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> закончена.
 +
 
 +
Последним на вход поступает значение <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]]
 +
|}
 +
 
 +
== Использование ==
 +
Чаще всего расширяемое хеширование используется в базах данных так как. Базы данных могут быть крайне большими и перехеширование всей базы данных займет продолжительное время при этом лишая пользователей доступа к базе данных. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу базы данных. Также расширяемое хэширование хорошо работает в условиях динамически изменяемого набора записей в хранимом файле.
 
== См. также ==
 
== См. также ==
 
*[[Хеш-таблица]]
 
*[[Хеш-таблица]]
Строка 16: Строка 36:
 
*[[Перехеширование]]
 
*[[Перехеширование]]
 
== Источники информации ==
 
== Источники информации ==
*[http://src-code.net/rasshiryaemyj-metod-xeshirovaniya/ http://src-code.net - Расширяемый метод хеширования]
+
*Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
*Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236
+
*Дейт К. Дж. Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
 +
*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Хеширование]]
 +
[[Категория: Базы данных]]

Текущая версия на 19:35, 4 сентября 2022

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

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

Метод расширяемого хеширования (англ. 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