С 1985 года считалось: чем ближе хеш-таблица к заполнению, тем неизбежнее замедляются поиск и вставка. В худшем случае требовалось порядка x проверок, где x показывает, насколько таблица близка к 100%.
Эндрю Крапивин придумал новую структуру, снизив сложность до
O((logx)*2).Более того, среднее время поиска может оставаться константным независимо от заполненности таблицы. Авторы также доказали, что найденная граница оптимальна.
Самое невероятное — Крапивин не знал о гипотезе Яо и пришёл к решению, экспериментируя с «крошечными указателями» ещё во время учёбы в Rutgers.
Иногда незнание общепринятых ограничений действительно помогает их разрушить.
