Предположим, что хеш-функция h(x) равна h(x) = x, и каждый сегмент может содержать в себе две вещи.
Я также буду использовать младшие значащие биты хеш-кода, как в индексе, в хеш-каталоге,в отличие от самых значимых битов.
По сути, чтобы получить пустую корзину, мы хотим вызвать удвоение хеш-таблицы, пытаясь поместить что-то в корзину, в которой нет места, но мы хотим, чтобы это удвоениеfail.
Итак, давайте начнем вставлять вещи.
Сначала вставьте 0. Это должно идти в первом сегменте, начиная с h(0) = 0 и 0 % 2 = 0.
Затем вставьте 4. Это также должно идти в первом сегменте, начиная с h(4) = 4 и 4 % 2 = 0.
Теперь вставка 8 завершается неудачно, поскольку корзина может содержать только две вещи, поэтому размер таблицы должен быть удвоен.Следовательно, глобальный уровень хеша увеличивается с 1 до 2.Другие изменения включают новый третий сегмент и четвертый хэш-индекс, указывающий на второй сегмент.
К сожалению, поскольку процесс перефразирования занимает h(x) % 4 и все наши числа (намеренно) кратны 4, первый сегментостается слишком полным, а третье ведро пусто.Это решается с еще одним удвоением хэш-таблицы.