@Ruzark

В чем суть алгоритма Линейного хеширования с частичным расширением?

Добрый вечер, может быть кто-то сталкивался с данным алгоритмом и сможет объяснить, в чем он заключается. Много материала есть на английском языке, но, к сожалению, я не владею им на таком уровне, чтобы уловить все механики и нюансы. Если кто-то захочет помочь, дайте знать в комментариях, я прикреплю pdf документ с объяснением на английском языке.
Заранее спасибо.
  • Вопрос задан
  • 74 просмотра
Решения вопроса 1
longclaps
@longclaps
Это старая идея о том, чтобы разбивать те корзины в хэш-таблице, население которых превышает заданый лимит, и напротив сливать в одну две, которые достаточно маленькие и составляют пару. Такой подход вынуждал при операциях на таблице пробовать разные варианты хэш-функции до (не)достижения попадания.

Сейчас мейнстрим-подход иной - при превышении размером таблицы некоего лимита (размера в элементах, не в корзинах) она переразбивается, скажем, на вдвое большее число корзин, а лимит удваивается. И наоборот. Хэш-функция едина для всех корзин, так проще, быстрее.

ЛХЧР был ценен тем, что его изобретатель дал строгую аналитическую оценку скорости операций, для прочих алгоритмов этого не было. С тех пор были посчитаны амортизированные оценки остальных способов, они столь же хорошие асимптотически, а на практике всё у них гораздо быстрее. Хэши научились готовить правильно, в целом поумнели.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
18 мая 2021, в 01:31
3000 руб./за проект
17 мая 2021, в 23:39
50000 руб./за проект
17 мая 2021, в 23:10
100000 руб./за проект