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

Студент Ратгерского университета Эндрю Крапивин не ожидал, что одна статья изменит его жизнь. Читая научные работы, он наткнулся на идею, которая привела к созданию совершенно нового типа хэш-таблицы. Его инновационный метод миниатюризации указателей позволил пересмотреть саму природу поиска в хэш-таблицах. Совместно с соавторами, Мартином Фарах-Колтоном и Уильямом Кушмаулем, Крапивин смог опровергнуть гипотезу, выдвинутую известным ученым Эндрю Яо. Ранее считалось, что скорость поиска в хэш-таблицах зависит от их наполненности. Однако новая модель показала, что время поиска пропорционально (log⁡x)2(log x)^2, что значительно быстрее, чем предполагалось. Более того, ученые доказали, что определенные типы хэш-таблиц могут обеспечивать постоянное среднее время поиска, независимо от их заполненности.  

Правда.Ру