Расширяемое хеширование (динамический подход к СУБД)

Расширяемое хеширование - это метод динамического хеширования, в котором каталоги и сегменты используются для хеширования данных. Это агрессивно гибкий метод, в котором хеш-функция также претерпевает динамические изменения.

Основные особенности расширяемого хеширования . Основные особенности этого метода хеширования:

• Каталоги: каталоги хранят адреса сегментов в указателях. Каждому каталогу назначается идентификатор, который может меняться каждый раз при расширении каталога.
• Сегменты: сегменты используются для хеширования фактических данных.

Базовая структура расширяемого хеширования :

Часто используемые термины в расширяемом хешировании :

• Каталоги: в этих контейнерах хранятся указатели на корзины. Каждому каталогу дается уникальный идентификатор, который может меняться каждый раз при расширении. Хеш-функция возвращает этот идентификатор каталога, который используется для перехода к соответствующему сегменту. Количество каталогов = 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. И назначьте соответствующие указатели.
    

• Шаг 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 номеров.

Основные наблюдения:

1. Bucket будет иметь более одного указателя, указывающего на него, если его локальная глубина меньше глобальной глубины.
2. Когда в бакете возникает условие переполнения, все записи в бакете повторно хешируются с новой локальной глубиной.
3. Если локальная глубина переполненного ведра
4. Размер сегмента не может быть изменен после начала процесса вставки данных.

Преимущества:

1. Получение данных менее затратно (с точки зрения вычислений).
2. Нет проблем с потерей данных, поскольку емкость хранилища динамически увеличивается.
3. При динамических изменениях в хэш-функции связанные старые значения повторно хешируются с помощью новой хеш-функции.

Ограничения расширяемого хеширования:

1. Размер каталога может значительно увеличиться, если несколько записей хешируются в одном каталоге, сохраняя при этом неравномерное распределение записей.
2. Размер каждого ведра фиксированный.
3. Память тратится на указатели, когда разница между глобальной и локальной глубиной становится значительной.
4. Этот метод сложно кодировать.

Структуры данных, используемые для реализации:

1. B + Деревья
2. Множество
3. Связанный список

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.