21
правка
Изменения
Нет описания правки
** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.
* Заголовок помещяется в памяти
[[Файл:Index_Hash_Simple.jpgpng|мини|Простой хеш-индекс]]
Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками.
[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]
=== Расширяемое хеширование===
* Большое количество корзин, сильно больше чем требуется* Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу
** Обычно - последовательных
** Разделение корзин при переполнении страницы
* Не работает при плохой хеш-функции, но у нас хорошая
При переполнении страницы мы:
* разделяем ее на несколько страниц
* разделим страницы, которые на нее ссылались, на несколько групп
* Каждой такой группе выделим по странице
Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)
[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]
=== Побитное расширяемое хеширование
*Глубина хеша $n$
** Создадим $2^n$ корзин
* Для каждой страницы хранится ее локальная глубина $k$
** Это значит что она хранит $2^{n−k} последовательных корзин на странице
** Может быть разной для разных страниц
* При переполнении происходит разделение корзин
** Страница глубины $k$ разделяется на две глубины $k+1$
