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

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

Заранее спасибо. 

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

  

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

  

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