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

Question

[Ruzark]

Добрый вечер, может быть кто-то сталкивался с данным алгоритмом и сможет объяснить, в чем он заключается. Много материала есть на английском языке, но, к сожалению, я не владею им на таком уровне, чтобы уловить все механики и нюансы. Если кто-то захочет помочь, дайте знать в комментариях, я прикреплю pdf документ с объяснением на английском языке.
Заранее спасибо.

Answer 1

[longclaps]

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

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

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

Comments

[Ruzark]

Всё понятно, спасибо вам!