Расширяемое хеширование (extendible hashing) - Динамическое хеширование
Расширяемое хеширование близко к динамическому. Этот метод также предусматривает изменение размеров блоков по мере роста базы данных, но это компенсируется оптимальным использованием места. Т. к. за один раз разбивается не более одного блока, накладные расходы достаточно малы [9].
Вместо бинарного дерева расширяемое хеширование предусматривает список, элементы которого ссылаются на блоки. Сами же элементы адресуются по некоторому количеству i битов псевдоключа (см. рис). При поиске берется i битов псевдоключа и через список (directory) находится адрес искомого блока. Добавление элементов производится сложнее. Сначала выполняется процедура, аналогичная поиску. Если блок неполон, добавляется запись в него и в базу данных. Если блок заполнен, он разбивается на два, записи перераспределяются по описанному выше алгоритму. В этом случае возможно увеличение числа бит, необходимых для адресации. В этом случае размер списка удваивается и каждому вновь созданному элементу присваивается указатель, который содержит его родитель. Таким образом, возможна ситуация, когда несколько элементов показывают на один и тот же блок. Следует заметить, что за одну операцию вставки пересчитываются значения не более, чем одного блока. Удаление производится по такому же алгоритму, только наоборот. Блоки, соответственно, могут быть склеены, а список - уменьшен в два раза.
Итак, основным достоинством расширяемого хеширования является высокая эффективность, которая не падает при увеличении размера базы данных. Кроме этого, разумно расходуется место на устройстве хранения данных, т. к. блоки выделяются только под реально существующие данные, а список указателей на блоки имеет размеры, минимально необходимые для адресации данного количества блоков. За эти преимущества разработчик расплачивается дополнительным усложнением программного кода.
Функции, сохраняющие порядок ключей (Order preserving hash functions)
Существует класс хеш-функций, которые сохраняют порядок ключей [11]. Другими словами, выполняется
K1 < K2 h(K1) < h(K2)
Эти функции полезны для сортировки, которая не потребует никакой дополнительной работы. Другими словами, мы избежим множества сравнений, т. к. для того, чтобы отсортировать объекты по возрастанию достаточно просто линейно просканировать хеш-таблицу.
В принципе, всегда можно создать такую функцию, при условии, что хеш-таблица больше, чем пространство ключей. Однако, задача поиска правильной хеш-функции нетривиальна. Разумеется, она очень сильно зависит от конкретной задачи. Кроме того, подобное ограничение на хеш-функцию может пагубно сказаться на ее производительности. Поэтому часто прибегают к индексированию вместо поиска подобной хеш-функции, если только заранее не известно, что операция последовательной выборки будет частой.
Минимальное идеальное хеширование
Как уже упоминалось выше, идеальная хеш-функция должна быстро работать и минимизировать число коллизий. Назовем такую функцию идеальной (perfect hash function) [12]. С такой функцией можно было бы не пользоваться механизмом разрешения коллизий, т. к. каждый запрос был бы удачным. Но можно наложить еще одно условие: хеш-функция должна заполнять хеш-таблицу без пробелов. Такая функция будет называться минимальной идеальной хеш-функцией. Это идеальный случай с точки зрения потребления памяти и скорости работы. Очевидно, что поиск таких функций - очень нетривиальная задача.
Один из алгоритмов для поиска идеальных хеш-функций был предложен Р. Чичелли [13]. Рассмотрим набор некоторых слов, для которых надо составить минимальную идеальную хеш-функцию. Пусть это будут некоторые ключевые слова языка С++. Пусть это будет какая-то функция, которая зависит от некоего численного кода каждого символа, его позиции и длины. Тогда задача создания функции сведется к созданию таблицы кодов символов, таких, чтобы функция была минимальной и идеальной. Алгоритм очень прост, но занимает очень много времени для работы. Производится полный перебор всех значений в таблице с откатом назад в случае необходимости, с целью подобрать все значения так, чтобы не было коллизий. Если взять для простоты функцию, которая складывает коды первого и последнего символа с длиной слова (да, среди слов умышленно нет таких, которые дают коллизию), то алгоритм дает следующий результат:
Буква |
Код |
Буква |
Код |
Буква |
Код |
Буква |
Код |
Буква |
Код |
A |
-5 |
E |
4 |
I |
2 |
N |
-1 |
T |
10 |
B |
-8 |
F |
12 |
K |
31 |
O |
22 |
U |
26 |
C |
-7 |
G |
-7 |
L |
29 |
R |
5 |
V |
19 |
D |
-10 |
H |
4 |
M |
-4 |
S |
7 |
W |
2 |
Слово |
Хеш |
Слово |
Хеш |
Слово |
Хеш |
Слово |
Хеш |
Auto |
21 |
Double |
0 |
Int |
15 |
Struct |
23 |
Break |
28 |
Else |
12 |
Long |
26 |
Switch |
17 |
Case |
1 |
Enum |
4 |
Register |
18 |
Typedef |
29 |
Char |
2 |
Extern |
9 |
Return |
10 |
Union |
30 |
Const |
8 |
Float |
27 |
Short |
22 |
Unsigned |
24 |
Continue |
5 |
For |
20 |
Signed |
3 |
Void |
13 |
Default |
7 |
Goto |
19 |
Sizeof |
25 |
Volatile |
31 |
Do |
14 |
If |
16 |
Static |
6 |
While |
11 |
Подробный анализ алгоритма, а также реализацию на С++ можно найти по адресу [12]. Там же описываются методы разрешения коллизий. К сожалению, эта тема выходит за рамки этой работы.
Похожие статьи
-
Введение - Динамическое хеширование
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь),...
-
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ - Программирование, ориентированное на объекты
Связанная организация памяти. - Ассоциативные структуры. - Списки. - Очереди. - Рекурсивные структуры. - Наборы. - Деревья. Связанная организация памяти...
-
Физические модели БД - Банки и базы данных. Системы управления базами данных
Под физической моделью БД понимается способ размещения данных на устройствах внешней памяти и способ доступа к этим данным. Каждая СУБД по-разному...
-
Система мониторинга социальных сетей предоставляет исследователю возможность собрать интересующие его упоминания в социальных сетях по какой-либо...
-
Заключение - Обзор проблематики и теоретических основ электронного документооборота
В современном динамично развивающемся мире рынок электронного документооборота не только занял прочную позицию, но и растет с каждым годом, потому что...
-
Собственными называют периодические колебания консервативной системы, совершающиеся исключительно под воздействием инерционных и упругих сил. Для...
-
Построение модели предметной области с помощью описания структур данных и программного кода является классическим подходом в разработке ИС. Зачастую...
-
Анализ принципа работы БП адаптера связи ОП - Работка буферной памяти адаптера связи
Буферная память этопамять для промежуточного хранения данных. Применяется при обмене данными между двумя устройствами, обладающими различной скоростью...
-
Составление семантического ядра интернет-сайта для улучшения позиции в поисковой выдаче
Введение Интернет - неотъемлемая часть современного бизнеса. Это среда, в которой любая компания или индивид, находящиеся в любой точке экономической...
-
Поисковые системы - Глобальная вычислительная сеть Internet
Основная задача Internet -- предоставление необходимой ин-формации. Чтобы найти нужную информацию необходимо знать адрес Web-страницы, на которой эта...
-
Цель Работы - изучить приемы создания и использования шаблонов классов. - Теоретические сведения Достаточно часто встречаются классы, объекты которых...
-
Объект ориентированный класс программирование Цель Работы - изучить методику создания одномерных динамических символьных массивов при помощи...
-
В микросхемах памяти динамического типа функции ЭП выполняет электрический конденсатор, образованный внутри МДП структуры. Информация представляется в...
-
Для третьего способа мне понадобился способ под названием "Стемминг". Данное понятие очень популярно во всемирной паутине, так как оно применяется в...
-
В Internet есть компьютеры которые позволяют вашему компьютеру действовать как терминал. Этот процесс называется удаленным входом (Telnetting). Tермин...
-
Описание модулей программы Проект приложения содержит следующие модули. Модуль UnitCollection. pas содержит описание классов для работы с коллекцией и...
-
Кодированием называется представление символов одного алфавита средствами другого алфавита. Алфавит содержащий два символа называется двоичным (часто их...
-
Анализ архитектуры и структуры компьютера Структура компьютера будет проанализирована, начиная с истории. В настоящее время известно пять поколений...
-
Взаимодействие задач с PVM - Администрирование параллельных процессов
В системе PVM каждая задача, запущенная на некотором процессоре, идентифицируется целым числом, которое называется идентификатором задачи (TID) и по...
-
В последнее время можно заметить стремительный рост значимости различных интернет-порталов, мобильных приложений, сервисов и IT-систем, существенно...
-
Выводы - Создание таблиц в Microsoft Excel
Итак, в ходе работы мною были изучены необходимые учебные материалы, а также были отработаны навыки работы с табличным процессором MS Excel 2010. Я...
-
Расширим построенную в предыдущей главе статичную модель за счет кросс-временных взаимозависимостей из пункта 2.3. Для этого построим системы правил...
-
Для разделения действительной и мнимой частей передаточной функции умножим числитель и знаменатель передаточной функции на комплексно сопряженное число...
-
Формы - Разработка информационной системы "Гостиница"
Главное предназначение формы в состоит в том, чтобы организовать удобную работу с данными (с понятным и приятным интерфейсом), чего нельзя добиться при...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
Завершив выбор схемы работы системы и общего принципа работы ее частей и выбрав тип базы данных, следует перейти к выбору языка программирования....
-
Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...
-
Составление частотного уравнения методом последовательного расщепления Рисунок 3.1 - Исходная модель. Расщепим ее на массе 2 Рисунок 3.2 - Расщепление на...
-
Механизмы обеспечения безопасности, Криптография - Защита информации в компьютерных сетях
Криптография Для обеспечения секретности применяется шифрование, или криптография, позволяющая трансформировать данные в зашифрованную форму, из которой...
-
Описание классов и методов - Обзор проблематики и теоретических основ электронного документооборота
В данной работе реализован один публичный класс Form1, в котором и происходит основной функционал программы, посредством выполнения методов по кнопкам....
-
Любое предприятие сталкивается с проблемой автоматизации работы отдельных сотрудников и подразделений в целом. Первая проблема при этом как выбрать...
-
В работе возникает необходимость выбора предметной области, в которой будет тестироваться каскадный классификатор. Главными вопросами на данном этапе...
-
Введение, Теоретические основы - Разработка консольного приложения на языке С++
Данная работа посвящена созданию своего рода базы данных на языке программирования С++. База данных содержит информацию о сотрудниках этого предприятия,...
-
В данном разделе выпускной квалификационной работы описывается процесс разработки программы извлечения КП текста, а также производится оценка качества ее...
-
Базы данных - это определенная совокупность информационных данных, отображающих в максимально возможной полноте состояние тех или иных объектов или...
-
Процесс декомпозиции - Администрирование параллельных процессов
Распараллеливание программ сводится к процессу декомпозиции задачи на независимые процессы, которые не требуют последовательного исполнения и могут,...
-
Оптимизатор - Разработка программного средства, позволяющего оптимизировать SQL-скрипты
Задача оптимизатора в рамках данной дипломной работы - исправлять части SQL-кода, которые могут приводить к дополнительным тратам памяти и ресурсов. На...
-
В выпускной квалификационной работе предметом исследования является деятельность по учету и управлению доставкой корреспонденции. Для того, чтобы...
-
Основные понятия систем базы данных - Основные понятия систем базы данных
База данных - совокупность данных, хранимых в соответствии со схемой данных, манипулирование которых осуществляется в соответствии с правилами средств...
-
Реализация поиска, Критерии оценки поиска - Осуществление хранения и поиска документов
Что обычно ищут в Интернете: персональные данные об индивидуумах и организациях; различные адресные данные; конкретные материалы (статьи, книги,...
Расширяемое хеширование (extendible hashing) - Динамическое хеширование