История изменений

Это способ разруливать коллизии так, чтобы поиск работал почти с идеальной скоростью. Это как я понимаю.

Если бы ключ лежал всегда строго в своей уникальной ячейке, коллизий бы не было. Пришел ключ, посчитали хэш, получили номер ячейки, хоп все. Взяли О(1). А у нас в ячейке может лежать чужой ключ! Вот это поворот, а?! Поэтому нельзя просто взять значение из ячейки, надо проверить - а это точно мой ключ? А не ошибаюсь ли я? Зачем вообще вот это все? Для чего мы живем? А не идиоты ли те, кто на мне пишет все эти программульки? (это уже со стороны ЯП)

И начинается глубинный поиск смыслов. Смотрим первую ячейку по хэшу. Не совпало? Смотрим следущую по правилам пробирования. Снова сравниваем. Итд, пока не найдем пустую ячейку.

Без вариации Брента цепочки коллизий могли быть линными, чтоы найти ключ, приходилось бы перебирать раз за разом. А с его вариацией цепочки укорачиваются искусственно. Алгоритм такой, что чаще всего ключ лежит в своей главной ячейке или в следущей за ней. Все. Скорость остается О(1), но это усредненное О(1) - за счет минимизации последвательных сравнений.

Ну круто же.

Это способ разруливать коллизии так, чтобы поиск работал почти с идеальной скоростью. Это как я понимаю.

Если бы ключ лежал всегда строго в своей уникальной ячейке, коллизий бы не было. Пришел ключ, посчитали хэш, получили номер ячейки, хоп все. Взяли О(1). А у нас в ячейке может лежать чужой ключ! Вот это поворот, а?! Поэтому нельзя просто взять значение из ячейки, надо проверить - а это точно мой ключ? А не ошибаюсь ли я? Зачем вообще вот это все? Для чего мы живем? А не идиоты ли те, кто на мне пишет все эти программульки? (это уже со стороны ЯП)

И начинается глубинный поиск смыслов. Смотрим первую ячейку по хэшу. Не совпало? Смотрим следущую по правилам пробирования. Снова сравниваем. Итд, пока не найдем пустую ячейку.

Без вариации Брента цепочки коллизий могли быть линными, чтоы найти ключ, приходилось бы перебирать раз за разом. А с его вариацией цепочки укорачиваются искусственно. Алгоритм такой, что чаще всего ключ лежит в своей главной ячейке или в следущей за ней. Все. Скорость остается О(1), но это усредненное О(1) - за счет минимизации последвательных сравнений.