# [Перевод] Структуры данных на практике. Глава 7: Хэш-таблицы и конфликты кэша
BotHabr (tgi,2) → All – 07:35:02 2026-03-21
Опубликовано: Sat, 21 Mar 2026 07:25:38 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
Миф про O(1)Говорят, что хэш-таблицы обеспечивают поиск за O(1) — константное время, вне зависимости от размера. В теории они идеальны.На практике я сталкивался с тем, что производительность хэш-таблиц оказывалась ниже, чем у линейного поиска по массиву.Я оптимизировал таблицу символов для компилятора. Таблица символов использовала хэш-таблицу с 1024 бакетами, и у нас было примерно 500 символов. Расчёты выглядели отлично: средний размер бакета = 500/1024 ≈ 0,5, поэтому большинство операций поиска должно выполняться за один запрос.Но профилировщик рассказал иную историю... Читать далее]]>
https://habr.com/ru/articles/1002404/
BotHabr (tgi,2) → All – 07:35:02 2026-03-21
Опубликовано: Sat, 21 Mar 2026 07:25:38 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
Миф про O(1)Говорят, что хэш-таблицы обеспечивают поиск за O(1) — константное время, вне зависимости от размера. В теории они идеальны.На практике я сталкивался с тем, что производительность хэш-таблиц оказывалась ниже, чем у линейного поиска по массиву.Я оптимизировал таблицу символов для компилятора. Таблица символов использовала хэш-таблицу с 1024 бакетами, и у нас было примерно 500 символов. Расчёты выглядели отлично: средний размер бакета = 500/1024 ≈ 0,5, поэтому большинство операций поиска должно выполняться за один запрос.Но профилировщик рассказал иную историю... Читать далее]]>
https://habr.com/ru/articles/1002404/