Английский там простой. Даже чересчур простой (что не удивительно, учитывая, что это писали французы) - и в результате этого упрощения существенные детали скрылись или потерялись.
Общая идея понятна: мы вычисляем номер корзины при хешировании как K=C%N (где C - значение hash key), а когда корзина переполняется, увеличиваем для неё N в 2 раза, и перекидываем часть элементов (для которых C%(2*N)!=K) в корзину с номером K+N. У корзины как-то запоминаем актуальное для неё значение N=N0*2^j (точнее, запоминаем j).
Дьяволы, как обычно, прячутся в деталях, и эти детали при первом прочтении мне понять не удалось:
- до переполнения в корзине может храниться более одного элемента. Где они хранятся? Для них сразу зарезервировано место, или где-то есть место для хранения списка?
- Что они делают при увеличении N? Неужели удваивают размер всей таблицы? Или каким-то образом отводят место только для новых корзин - потомков переполнившихся?
Не знаю, какая у Вас цель, но я бы в этот момент придумал какую-нибудь схему, рещающую эти вопросы (вероятно, представил бы корзины в виде бинарного дерева, где пути влево-вправо определяются битами в последовательности остатков C%(N*2^j)), не пытаясь разобраться в статье дальше. Но если нужно разобраться именно в этом алгоритме - придётся его читать.
Кстати, какого года статья? По общему впечатлению (и по датам цитируемых работ), это где-то 1979-1985 гг. Не забывайте, что тогда "640 КБ хватало всем"!
Простой
Средний
Сложный
