Обычно вы смотрите на сложности различных операций, и это хорошее руководство: амортизированная O (1) вставка, O (1) поиск, удаление для хэш-карты по сравнению с O (log N), вставка, поиск, удаление для древовидная карта.
Однако, есть определенные ситуации, в которых сложности вводят в заблуждение, поскольку постоянные термины являются экстремальными. Например, предположим, что ваши 10 тыс. Элементов являются ключевыми. Предположим далее, что каждая строка имеет длину 100 000 символов. Предположим, что разные строки обычно отличаются в начале строки (например, если они по существу случайные, пары будут отличаться в первом байте с вероятностью 255/256).
Затем, чтобы выполнить поиск, хэш-карта должна хешировать строку 100 КБ. Это O (1) в размере коллекции, но может занять довольно много времени, так как это, вероятно, O (M) в длине строки. Сбалансированное дерево должно выполнять сравнение log N <= 14, но каждое из них должно рассматривать только несколько байтов. Это может занять совсем немного времени. </p>
С точки зрения доступа к памяти, с размером строки в 64 байта кеша, хэш-карта загружает более 1500 последовательных строк и выполняет 100-килобайтовые операции, тогда как дерево загружает 15 случайных строк (на самом деле, вероятно, 30 из-за косвенного обращения через строку) и выполняет 14 * (некоторое небольшое количество) байтовых операций. Вы можете видеть, что первое вполне может быть медленнее, чем второе. Или это может быть быстрее: насколько хороши пропускная способность FSB вашей архитектуры, время задержки и спекулятивное кэширование чтения?
Если поиск находит совпадение, то, конечно, в дополнение к этому обеим структурам необходимо выполнить одно сравнение строк во всю длину. Также hashmap может выполнить дополнительные неудачные сравнения, если в корзине произошла коллизия.
Если предположить, что неудачные сравнения настолько быстры, что их можно пренебречь, в то время как успешные сравнения и операции хэширования выполняются медленно, дерево может быть примерно в 1,5-2 раза быстрее, чем хеш. Если эти предположения не верны, то не будет.
Конечно, крайний пример, но довольно легко увидеть, что в ваших данных конкретная операция O (log N) может быть значительно быстрее, чем конкретная операция O (1). Вы, конечно, правы, желая провести тестирование, но если ваши тестовые данные не являются репрезентативными для реального мира, то результаты вашего теста также могут быть не репрезентативными. Сравнения структур данных, основанных на сложности, относятся к поведению в пределе, когда N приближается к бесконечности. Но N не приближается к бесконечности. Это 10000.