tgoop.com/practicum_math/588
Last Update:
Сегодня у нас для вас история, которая доказывает: математика поддаётся смелым.
Зимой 2025 года Эндрю Крапивин, аспирант Кембриджского университета, опубликовал статью о новом подходе к хеш-таблицам. В ней он сумел опровергнуть гипотезу Эндрю Яо и придумал, как ускорить интернет. Самое удивительное: о существовании гипотезы Эндрю не знал. А статья его стала настоящей сенсацией, и вот почему.
🗂️Что такое хеш-таблицы
Каждый раз, когда вы ищете товар в онлайн-магазине или приложение в сторе, в дело вступают хеш-таблицы. Это структуры данных, которые хранят пары «ключ-значение» и помогают находить информацию.
Представьте библиотеку, где у каждой книги есть уникальный номер (ключ), а каталог (хеш-функция) указывает точное место книги на полке. Примерно так это и работает.
У хеш-таблиц есть ограничения. По мере заполнения таблицы увеличивается вероятность коллизий — ситуаций, когда разные ключи указывают на одну ячейку.
В 1985 году Эндрю Яо предположил, что при высокой заполненности таблицы поиск свободной ячейки требует времени, пропорционального степени заполнения. Например, при заполненности на 99% придется проверить около 100 позиций, чтобы добавить новый элемент, а при заполненности на 99,9 — 1000 позиций.
В коротком посте объяснить будет нелегко. Если сильно упрощать, Крапивин придумал новый тип хеш-таблиц. Он предложил разбивать таблицу на сегменты так, что при заполненности одного сегмента можно сразу начать искать в другом.
Этот метод позволяет находить свободные ячейки намного быстрее, даже если таблица сильно заполнена. А в некоторых случаях — искать данные за постоянное время независимо от того, насколько полна таблица. Метод опровергает теорию, которой четыре десятка лет!
🌐 Влияние на будущее интернета
Теперь благодаря Крапивину разработчики смогут создавать более быстрые и эффективные структуры данных. Веб-страницы начнут быстрее загружаться, а онлайн-сервисы — лучше работать. Иными словами, нам с вами ускорят интернет,
Возможно, Крапивин сделал открытие, потому что не слышал о теории Яо и не знал, что его что-то ограничивает?
#история
