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