Изменения

При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.== Структура и алгоритм =='''Метод расширяемого хеширования''' (англ. ''extendable extendible hashing'') представляет собой изящный вариант основного метода хешированиязаключается в том, что хеш-таблица представлена как '''каталог''' (англ. ''directory''), позволяющий устранить проблемы хеширования при увеличении размеров хешированного файла а каждая ячейка будет указывать на '''емкость''' (англ. ''bucket'') которая имеет определенную '''вместимость''' (увеличение количества коллизий и среднего времени доступаангл. capacity). В действительностиСама хеш-таблица будет иметь '''глобальную глубину''' (англ. ''global depth''), расширяемое хеширование гарантирует, что количество операций доступа к диску, необходимых а каждая из емкостей имеет '''локальную глубину''' (англ. ''local depth''). Глобальная глубина показывает сколько последних бит будут использоваться для поиска определенной записи, никогда не превышает двух того чтобы определить в какую емкость следует заносить значения. А из разницы локальной глубины и обычно сводится только к одной операцииглобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой <tex>K = 2 </tex>^{<tex>G-L</tex>} где <tex>G</tex> — глобальная глубина, независимо от того<tex>L</tex> — локальная глубина, какого размера достигает сам файла <tex>K</tex> количество ссылающихся ячеек. (Поэтому данный метод гарантирует также, что никогда не возникнет потребность в реорганизации файлаДля поиска емкости используется [[Wikipedia:Trie|цифровое дерево]].)

'''Примечание'''Теперь рассмотрим сам алгоритм если нам поступило некоторое значение: В этой схеме расширяемого хеширования #Переводим значение в двоичный вид, смотрим на последние <tex>G</tex> битов и решаем в какую емкость отправить значение.#Если емкость имеет свободное место, то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости: ##Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения хешированного поля должны быть уникальнымив новые две емкости увеличив у этих емкостей локальную глубину на <tex>1</tex>. ##Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, а такое условиеудваивая при этом количество ячеек, разумеетсяколичество указателей на емкости, будет соблюденоа также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, если данное поле фактически является первичным ключомразделим ее на две емкости и так далее. == Схема хеширования Пример==# ДопустимРассмотрим алгоритм на примере. Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения <tex>9, что основной функцией хеширования является h20, а значение первичного ключа некоторой конкретной записи r равно к. Хеширование значения к 26</tex> (т.е. вычисление выражения h(ксмотри рисунок №1)) приводит к получению значения sгде <tex>G</tex> — глобальная глубина, <tex>l1, l2, l3, называемого псевдоключом (pseudokey) записи к. Псевдоключи не интерпретируются непосредственно как адресаl4</tex> — локальные глубины емкостей, а вместо этого применяются для косвенного поиска адресов хранения, как описано нижевместимость емкостей равна <tex>3</tex>.# Файл имеет связанный с ним каталог, который также хранится Первым на дискевход поступает значение <tex>9</tex>. Каталог состоит из заголовка, содержащего значение d (сокращение от depth — глубина каталога), наряду с 2Представим его в двоичном виде: <suptex>d9 = 8+1 = 1000+1 = 1001</suptex> указателями. Указатели указывают Окончание <tex>01</tex> соответствует второй ячейке значит смотрим на страницы с данными, содержащими фактические записи вторую емкость. В ней есть свободное место и мы просто помещаем <tex>9</tex> в нее (на каждой странице имеется много записейсмотри рисунок №2). Таким образом, каталог с глубиной d позволяет управлять файлом На этом работа с максимальным размером, составляющим 2<suptex>d9</suptex> отдельных страниц с даннымизакончена.[[Файл:Deit vvedenie v DB 8e Далее на вход поступает значение <tex>20</tex>.jpg|мини| Пример применения способа расширяемого хеширования]]# Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака b, то i-й указатель Представим его в каталоге (1 двоичном виде: < i tex>20 = 16+4 = 10000+100 = 10100< 2/tex>. Это значение оканчивается на <suptex>d00</suptex>) указывает на страницуи должно пойти в первую емкость, содержащую все записи, для которых b принимает значение i-lно первая емкость полностью заполнена. Иными словами, первый указатель указывает Следовательно мы смотрим на страницу, содержащую все записи, для которых b состоит из одних нулей, второй указатель указывает локальную глубину первой емкости то есть на страницу, для которой b равно 0. .. 01, и т<tex>l1</tex>.д. (Обычно все эти 2<suptex>dl1 = G</suptex> указателя не являются различными; это означает, что а значит следуя выше описанному алгоритму мы должны удвоить количество различных страниц с даннымиячеек каталога, как правилоувеличить глобальную глубину, меньше чем 2затем увеличить количество последних бит по которым мы раскидываем значения на <suptex>d1</suptex>и перехешировать первую емкость, как показано разделив ее на рис.) Поэтомудве, чтобы найти запись, имеющую значение первичного ключа к, необходимо хешировать к для определения псевдоключа s увеличив локальную глубину и взять первые d битов этого псевдоключа; если эти биты имеют числовое значение i-l, осуществляется переход к i-му указателю в каталоге (первая операция доступа к диску) и переход разместив значения по этому указателю к странице, содержащей требуемую запись новым емкостям (вторая операция доступа к дискусмотри рисунок №3). '''Примечание''': На практике этот каталог обычно остается достаточно небольшим для того, чтобы этом работа с <tex>20</tex> закончена.  Последним на вход поступает значение <tex>26</tex>. Представим его можно было почти все время хранить в оперативной памятидвоичном виде: <tex>26 = 16+8+2 = 10000+1000+10 = 11010</tex>. Поэтому упомянутые "две" операции доступа к диску обычно сводятся к одной.#Каждая страница с данными имеет также заголовок, указывающий локальную глубину р этой страницы Последние <tex>3</tex> бита (р < dtex>010</tex>). Предположимсоответствуют третьей емкости, например, что d равно 3 но она также полностью заполнена как и первый указатель в каталоге (указатель 000) указывает на страницуво втором случае, для которой но ее локальная глубина р равна 2. В данном случае локальная меньше чем глобальная глубина 2 означает, что эта страница содержит не а следовательно нам надо только все записи с псевдоключамиперехешировать емкость, начинающимися с 000разделив ее на две, но увеличив локальную глубину и содержит все записи с псевдоключами, начинающимися с 00 разместив значения по новым емкостям (тсмотри рисунок №4).е. теми, которые начинаются На этом работа с 000, а также теми, которые начинаются с 001)<tex>26</tex> закончена. Иными словами, указатель каталога 001 также указывает на эту страницу (см{|align="center" |-valign="top" |[[Файл:FirstStep. рис)png|мини|250px|рисунок №1]] |[[Файл:SecondStep.png|мини|250px|рисунок №2]]#Теперь предположим, что страница с данными 000 заполнена и нужно вставить новую запись, имеющую псевдоключ, который начинается с 000 (или с 001) |[[Файл:ThirdStep. В этот момент указанная страница разделяется на две; это означает, что из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новуюpng|мини|250px|рисунок №3]] |[[Файл:ForthStep. Указатель 001 png|мини|250px|рисунок №4]] |} == Использование ==Чаще всего расширяемое хеширование используется в каталоге корректируется таким образом, чтобы он указывал на новую страницу (указатель 000 все еще указывает на старую страницу)базах данных так как. Локальная глубина р для каждой из этих двух страниц теперь будет равна 3, а не 2Базы данных могут быть крайне большими и перехеширование всей базы данных займет продолжительное время при этом лишая пользователей доступа к базе данных.#Теперь допустимА при использовании расширяемого хеширования перехешировать придется только малые группы, что страница с данными, соответствующая начальной строке битов 000, снова заполняется и должна быть опять разделена. Существующий каталог не позволяет обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже равна глубине каталогасильно замедлит работу базы данных. Поэтому размер каталога удваивается; это означает, что значение d увеличивается на единицу и каждый указатель заменяется парой смежных, идентичных указателей. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой странице, а записи 0001 перемещаются на новую страницу; первый указатель Также расширяемое хэширование хорошо работает в условиях динамически изменяемого набора записей в каталоге остается неизменным (т.е. по-прежнему указывает на старую страницу), а второй указатель корректируется таким образом, чтобы он указывал на новую страницу. Следует отметить, что операция удваивания размера каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с даннымихранимом файле.

*[http://src-codeБакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр.net/rasshiryaemyj-metod-xeshirovaniya/ http://src-code50.net - Расширяемый метод хеширования]*Дейт К. Дж., — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing]