🚀 СТУДЕНТ СЛУЧАЙНО ОПРОВЕРГ ГИПОТЕЗУ, В КОТОРУЮ ВЕРИЛИ 40 ЛЕТ

С 1985 года считалось: чем ближе хеш-таблица к заполнению, тем неизбежнее замедляются поиск и вставка. В худшем случае требовалось порядка x проверок, где x показывает, насколько таблица близка к 100%.

Эндрю Крапивин придумал новую структуру, снизив сложность до O((logx)*2).

Более того, среднее время поиска может оставаться константным независимо от заполненности таблицы. Авторы также доказали, что найденная граница оптимальна.

Самое невероятное — Крапивин не знал о гипотезе Яо и пришёл к решению, экспериментируя с «крошечными указателями» ещё во время учёбы в Rutgers.

Иногда незнание общепринятых ограничений действительно помогает их разрушить.