Почему Big O недостаточно для выбора структуры данных в C++

Автор создал hashbrowns, набор тестов для массивов, связных списков и хеш-таблиц. В замерах линейный поиск по массиву обгонял хеш-таблицу до примерно 150 элементов: вычисление хеша съедало выигрыш от быстрого доступа.

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

Разбор устройства hashbrowns показывает, почему перед оптимизацией стоит измерять свою нагрузку: результат зависит от заполнения хеш-таблицы, ключей и удалений.