Математик українського походження здійснив науковий прорив, який може змінити комп'ютери та гаджети по всьому світу

Хеш-таблиці забезпечують швидкий доступ до даних, коли ви шукаєте контакти, товари чи перевіряєте пошту. Вважалося, що їхня швидкість має межі. Проте випадкове відкриття аспіранта Ендрю Крапівіна змінило ці виявлення.

Що таке хеш-таблиці

Хеш-таблиця — це структура даних, яка зберігає пари «ключ-значення» та дозволяє швидко додавати, видаляти й шукати інформацію за ключем.

Хеш-таблиці виконують хеш-функції, які обчислюють індекс для швидкого доступу до даних у масиві. Завдяки цьому пошуку можна отримати миттєво, без перебору всього набору інформації. Хеш-таблицю можна порівняти з бібліотекою: книги зберігаються на конкретних поліцях за номерами (ключами), а каталог (хеш-функція) вказує їх точне місце без довгих пошуків.

Чому до відкриття Крапівіна вважали, що можливості прискорення хеш-таблиці вичерпані?

У той час відомий вчений Ендрю Яо висунув теорію, яка стверджувала, що максимальна швидкість пошуку в хеш-таблицях обмежена випадковим вибором позицій. Відповідно до цієї теорії, із заповненням таблиці час пошуку не зменшується.

Яо припускав, що у гіршому випадку для пошуку останнього вільного осередку в хеш-таблиці необхідно перевірити час, пропорційний кількості. Якщо таблиця заповнена на 99%, можна знадобитися перевірити близько 100 позицій. Протягом 40 років ця гіпотеза вважалася незаперечною. Однак у січні 2025 року аспірант Кембриджського університету Ендрю Крапівін разом із цими колегами спростував теорію, показавши, що хеш-таблиці можуть працювати ефективніше.

Що довів Крапівін

Наприкінці 2021 року студент Ратгерського університету Ендрю Крапівін випадково натрапив на статтю про зменшення розмірів покажчиків у пам'яті. Через декілька років він повернувся до цієї теми й зрозумів, що можна оптимізувати хеш-таблиці, зробивши їх швидкими та ефективнішими. Крапівін створив новий тип хеш-таблиці, яка дозволяла швидше знайти елементи навіть при майже повному заповненні.

Спочатку його ідею скептично сприйняв професор Мартін Фарах-Колтон, але після перевірки Вільямом Кузмалом з Університету Карнегі — Меллона стало ясно, що це справжній прорив. Разом із колегами він підготував статтю, де описав метод, що дозволяє шукати дані за постійний час незалежно від заповненості таблиці.

• Відомо, що цей талановитий юнак родом із Сєвєродонецька, і колись він навіть випускав подкаст зі своїм дідом, де розповідав про своє походження.
• Читати також: Skype закривається: що буде з відомим додатком для спілкування та як зберегти свої контакти