Расширяемое хеширование (динамический подход к СУБД)
Расширяемое хеширование - это метод динамического хеширования, в котором каталоги и сегменты используются для хеширования данных. Это агрессивно гибкий метод, в котором хеш-функция также претерпевает динамические изменения.
Основные особенности расширяемого хеширования . Основные особенности этого метода хеширования:
- Каталоги: каталоги хранят адреса сегментов в указателях. Каждому каталогу назначается идентификатор, который может меняться каждый раз при расширении каталога.
- Сегменты: сегменты используются для хеширования фактических данных.
Базовая структура расширяемого хеширования :
Часто используемые термины в расширяемом хешировании :
- Каталоги: в этих контейнерах хранятся указатели на корзины. Каждому каталогу дается уникальный идентификатор, который может меняться каждый раз при расширении. Хеш-функция возвращает этот идентификатор каталога, который используется для перехода к соответствующему сегменту. Количество каталогов = 2 ^ Глобальная глубина.
- Ведра: в них хранятся хешированные ключи. Каталоги указывают на корзины. Бакет может содержать более одного указателя на него, если его локальная глубина меньше глобальной глубины.
- Глобальная глубина: связана с каталогами. Они обозначают количество битов, которые используются хеш-функцией для классификации ключей. Глобальная глубина = количество бит в идентификаторе каталога.
- Локальная глубина: такая же, как и у глобальной глубины, за исключением того факта, что локальная глубина связана с бакетами, а не каталогами. Локальная глубина в соответствии с глобальной глубиной используется для определения действия, которое должно быть выполнено в случае переполнения. Локальная глубина всегда меньше или равна глобальной глубине.
- Разделение сегмента: когда количество элементов в сегменте превышает определенный размер, он разделяется на две части.
- Расширение каталога: расширение каталога происходит при переполнении корзины. Расширение каталога выполняется, когда локальная глубина переполненного сегмента равна глобальной глубине.
Базовая работа расширяемого хеширования :
- Шаг 1 - Анализ элементов данных: элементы данных могут существовать в различных формах, например. Integer, String, Float и т. Д. В настоящее время рассмотрим элементы данных целочисленного типа. например: 49.
- Шаг 2 - Преобразование в двоичный формат: преобразование элемента данных в двоичную форму. Для строковых элементов рассмотрите эквивалентное ASCII целое число начального символа, а затем преобразуйте целое число в двоичную форму. Поскольку у нас 49 в качестве элемента данных, его двоичная форма - 110001.
- Шаг 3 - Проверьте глобальную глубину каталога. Предположим, что глобальная глубина хеш-каталога равна 3.
- Шаг 4 - Идентификация справочника: рассмотрите количество младших битов «глобальной глубины» в двоичном числе и сопоставьте его с идентификатором справочника.
Например. Полученный двоичный файл: 110001, а глобальная глубина равна 3. Таким образом, хеш-функция вернет 3 младших бита из 110 001, а именно. 001. - Шаг 5 - Навигация: Теперь перейдите к сегменту, указанному в каталоге с идентификатором каталога 001.
- Шаг 6 - Проверка вставки и переполнения: вставьте элемент и проверьте, не переполняется ли ведро. Если обнаружено переполнение, перейдите к шагу 7, а затем к шагу 8 , в противном случае перейдите к шагу 9 .
- Шаг 7. Решение проблемы переполнения при вставке данных. Часто при вставке данных в сегменты может случиться так, что сегмент переполнится. В таких случаях нам необходимо выполнить соответствующую процедуру, чтобы избежать неправильной обработки данных.
Во-первых, проверьте, меньше ли локальная глубина глобальной глубине или равна ей. Затем выберите один из следующих случаев.- Случай 1: Если локальная глубина переполненного сегмента равна глобальной глубине, то необходимо выполнить расширение каталога, а также разделение сегмента. Затем увеличьте глобальную глубину и значение локальной глубины на 1. И назначьте соответствующие указатели.
Расширение каталога удвоит количество каталогов, присутствующих в хэш-структуре. - Случай 2: в случае, если локальная глубина меньше глобальной, выполняется только Bucket Split. Затем увеличьте только локальное значение глубины на 1. И назначьте соответствующие указатели.
- Случай 1: Если локальная глубина переполненного сегмента равна глобальной глубине, то необходимо выполнить расширение каталога, а также разделение сегмента. Затем увеличьте глобальную глубину и значение локальной глубины на 1. И назначьте соответствующие указатели.
- Шаг 8 - Повторное хеширование элементов разделенного сегмента: элементы, присутствующие в переполненном сегменте, который разделен, повторно хешируются с учетом новой глобальной глубины каталога.
- Шаг 9 - Элемент успешно хеширован.
Пример, основанный на расширяемом хешировании. Теперь давайте рассмотрим яркий пример хеширования следующих элементов: 16,4,6,22,24,10,31,7,9,20,26.
Размер ведра: 3 (предположить)
Хеш-функция: предположим, что глобальная глубина равна X. Затем хеш-функция возвращает X LSB.
- Решение: сначала вычислите двоичные формы каждого из заданных чисел.
16– 10000
4-00100
6-00110
22-10110
24–11000
10-01010
31–11111
7-00111
9- 01001
20-10100
26-11010 - Первоначально глобальная глубина и локальная глубина всегда равны 1. Таким образом, фрейм хеширования выглядит так:
- Вставка 16:
Двоичный формат 16 - 10000, а глобальная глубина - 1. Хеш-функция возвращает 1 LSB из 1000 0, что равно 0. Следовательно, 16 отображается в каталог с id = 0.
- Вставка 4 и 6:
И 4 (10 0 ), и 6 (11 0 ) имеют в своем младшем разряде 0. Следовательно, они хешируются следующим образом:
- Вставка 22: двоичная форма числа 22 равна 1011 0 . Его младший бит равен 0. Корзина, указанная каталогом 0, уже заполнена. Следовательно, происходит переполнение.
- Как указано в шаге 7 - случай 1 , поскольку локальная глубина = глобальная глубина, сегмент разделяется и происходит расширение каталога. Кроме того, повторное хеширование чисел, присутствующих в переполненном ведре, происходит после разделения. И, поскольку глобальная глубина увеличивается на 1, теперь глобальная глубина равна 2. Следовательно, 16,4,6,22 теперь повторно хешируются относительно 2 младших битов. [16 (100 00 ), 4 (1 00 ), 6 ( 1 10 ), 22 (101 10 )]
*Notice that the bucket which was underflow has remained untouched. But, since the number of directories has doubled, we now have 2 directories 01 and 11 pointing to the same bucket. This is because the local-depth of the bucket has remained 1. And, any bucket having a local depth less than the global depth is pointed-to by more than one directories.
- Вставка 24 и 10:24 (110 00 ) и 10 (10 10 ) может быть хеширован на основе каталогов с идентификаторами 00 и 10. Здесь мы не сталкиваемся с условиями переполнения.
- Вставка 31,7,9: все эти элементы [31 (111 11 ), 7 (1 11 ), 9 (10 01 )] имеют либо 01, либо 11 в своих младших разрядах. Следовательно, они отображаются в сегменте, указанном 01 и 11. Мы не сталкиваемся здесь с каким-либо условием переполнения.
- Вставка 20: Вставка элемента данных 20 (101 00 ) снова вызовет проблему переполнения.
- 20 вставляется в сегмент, обозначенный 00. Как указано в шаге 7 - Случай 1 , поскольку локальная глубина сегмента = глобальная глубина , расширение каталога (удвоение) происходит вместе с разделением сегмента. Элементы, присутствующие в переполненной корзине, перефразируются с новой глобальной глубиной. Теперь новая хеш-таблица выглядит так:
- Вставка 26: общая глубина равна 3. Следовательно, учитываются 3 младших бита из 26 (11 010 ). Следовательно, 26 лучше всего подходят для корзины, указанной в справочнике 010.
- Сегмент переполняется, и, как указано в Шаге 7 - Случай 2, поскольку локальная глубина сегмента <Глобальная глубина (2 <3) , каталоги не удваиваются, а только сегмент разделяется, а элементы повторно хешируются.
Наконец, получается результат хеширования заданного списка чисел.
- На этом завершено хеширование 11 номеров.
Основные наблюдения:
- Bucket будет иметь более одного указателя, указывающего на него, если его локальная глубина меньше глобальной глубины.
- Когда в бакете возникает условие переполнения, все записи в бакете повторно хешируются с новой локальной глубиной.
- Если локальная глубина переполненного ведра
- Размер сегмента не может быть изменен после начала процесса вставки данных.
Преимущества:
- Получение данных менее затратно (с точки зрения вычислений).
- Нет проблем с потерей данных, поскольку емкость хранилища динамически увеличивается.
- При динамических изменениях в хэш-функции связанные старые значения повторно хешируются с помощью новой хеш-функции.
Ограничения расширяемого хеширования:
- Размер каталога может значительно увеличиться, если несколько записей хешируются в одном каталоге, сохраняя при этом неравномерное распределение записей.
- Размер каждого ведра фиксированный.
- Память тратится на указатели, когда разница между глобальной и локальной глубиной становится значительной.
- Этот метод сложно кодировать.
Структуры данных, используемые для реализации:
- B + Деревья
- Множество
- Связанный список
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.