[Перевод] Структуры данных на практике. Глава 7: Хэш-таблицы и конфликты кэша
Миф про O(1)
Говорят, что хэш-таблицы обеспечивают поиск за O(1) — константное время, вне зависимости от размера. В теории они идеальны.
На практике я сталкивался с тем, что производительность хэш-таблиц оказывалась ниже, чем у линейного поиска по массиву.
Я оптимизировал таблицу символов для компилятора. Таблица символов использовала хэш-таблицу с 1024 бакетами, и у нас было примерно 500 символов. Расчёты выглядели отлично: средний размер бакета = 500/1024 ≈ 0,5, поэтому большинство операций поиска должно выполняться за один запрос.
Но профилировщик рассказал иную историю...
Читать далее