✖️ Как молодой математик бросил вызов 40-летней теории и ускорил интернет

Сегодня у нас для вас история, которая доказывает: математика поддаётся смелым.

❓Что случилось
Зимой 2025 года Эндрю Крапивин, аспирант Кембриджского университета, опубликовал статью о новом подходе к хеш-таблицам. В ней он сумел опровергнуть гипотезу Эндрю Яо и придумал, как ускорить интернет. Самое удивительное: о существовании гипотезы Эндрю не знал. А статья его стала настоящей сенсацией, и вот почему.

🗂️Что такое хеш-таблицы
Каждый раз, когда вы ищете товар в онлайн-магазине или приложение в сторе, в дело вступают хеш-таблицы. Это структуры данных, которые хранят пары «ключ-значение» и помогают находить информацию.

Представьте библиотеку, где у каждой книги есть уникальный номер (ключ), а каталог (хеш-функция) указывает точное место книги на полке. Примерно так это и работает.

📝 Гипотеза Яо
У хеш-таблиц есть ограничения. По мере заполнения таблицы увеличивается вероятность коллизий — ситуаций, когда разные ключи указывают на одну ячейку.

В 1985 году Эндрю Яо предположил, что при высокой заполненности таблицы поиск свободной ячейки требует времени, пропорционального степени заполнения. Например, при заполненности на 99% придется проверить около 100 позиций, чтобы добавить новый элемент, а при заполненности на 99,9 — 1000 позиций.

🚀 Что придумал Крапивин
В коротком посте объяснить будет нелегко. Если сильно упрощать, Крапивин придумал новый тип хеш-таблиц. Он предложил разбивать таблицу на сегменты так, что при заполненности одного сегмента можно сразу начать искать в другом.

Этот метод позволяет находить свободные ячейки намного быстрее, даже если таблица сильно заполнена. А в некоторых случаях — искать данные за постоянное время независимо от того, насколько полна таблица. Метод опровергает теорию, которой четыре десятка лет!

🌐 Влияние на будущее интернета
Теперь благодаря Крапивину разработчики смогут создавать более быстрые и эффективные структуры данных. Веб-страницы начнут быстрее загружаться, а онлайн-сервисы — лучше работать. Иными словами, нам с вами ускорят интернет, чтобы смотреть мемы и картинки с котами было ещё проще.

Возможно, Крапивин сделал открытие, потому что не слышал о теории Яо и не знал, что его что-то ограничивает?

#история