Невероятно, но факт: студент доказал, что скорость поиска не зависит от заполненности хэш-таблицы

Студент Ратгерского университета Эндрю Крапивин не ожидал, что одна статья изменит его жизнь. Читая научные работы, он наткнулся на идею, которая привела к созданию совершенно нового типа хэш-таблицы.

Фото: flickr.com by r. nial bradshaw, https://creativecommons.org/licenses/by/2.0/

интернет

Его инновационный метод миниатюризации указателей позволил пересмотреть саму природу поиска в хэш-таблицах. Совместно с соавторами, Мартином Фарах-Колтоном и Уильямом Кушмаулем, Крапивин смог опровергнуть гипотезу, выдвинутую известным ученым Эндрю Яо.

Ранее считалось, что скорость поиска в хэш-таблицах зависит от их наполненности. Однако новая модель показала, что время поиска пропорционально (log⁡x)2(log x)^2, что значительно быстрее, чем предполагалось. Более того, ученые доказали, что определенные типы хэш-таблиц могут обеспечивать постоянное среднее время поиска, независимо от их заполненности.

Эти результаты оказались неожиданными даже для самих авторов. Хотя их работа не приведет к немедленным технологическим изменениям, она открывает новые горизонты в изучении структур данных. В будущем это может стать основой для инновационных приложений в компьютерных науках.

Уточнения

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

Э́ндрю Я́о Цичжи́ (англ. Andrew Chi-Chih Yao, 24 декабря 1946 года, Шанхай, Китай) — китайский и прежде американский учёный в области теории информатики. Профессор университета Цинхуа (Пекин). 

Ратгерский университет (Рутгерский университет; англ. Rutgers University (Rutgers, The State University of New Jersey) — университет штата, крупнейшее высшее учебное заведение Нью-Джерси.