Сложность времени между Jash's HashMap и TreeMap?

Question

Из моего понимания

TreeMap :
1. Insert O( logN )
2. Delete O( logN )
3. Retrieve O( logN )
HashMap :
1. Insert O( 1 ) -> O( N )
2. Delete O( 1 ) -> O( N )
3. Retrieve O( 1 ) -> O( N )

Я знаю, что TreeMap использует красно-черное дерево как внутреннюю структуру данных. Однако я не уверен в внутренней структуре данных HashMap.

1. Реализован ли HaspMap с использованием Хеш-таблица?
2. Если ответ «Да», то используется ли реализация массива или реализация базы ссылок?
3. А если он использовал базу массива, то сортируется или не сортируется?

Я работаю над небольшим проектом, использующим Java, чтобы продемонстрировать сложность выполнения всех операций (вставка, удаление, получение) между HashMap и TreeMap, но я не знаю, как связать формулу теории с реальным результатом запустить программу. Например, от запуска быстрого теста: 1. Вставьте 10000 элементов 2. Удалить 100 элементов 3. Получить 100 элементов

Я получил эту информацию:

     HashMap
Create time : 6348015 nano seconds.
Remove time : 98458 nano seconds.
Retrieve Found time : 59762 nano seconds.
Retrieve Not Found time : 39097 nano seconds.
 --- end ---

     TreeMap
Create time : 20518163 nano seconds.
Remove time : 274221 nano seconds.
Retrieve Found time : 112072 nano seconds.
Retrieve Not Found time : 168442 nano seconds.
 --- end ---

Я хотел бы знать, как я могу найти связь в эти времена с теоретической временной сложностью, такой как O (N) или O (logN)? И этот результат меня удивил, так как я всегда думаю, что TreeMap сильно побьет HashMap. Кто-нибудь может дать мне краткое объяснение этих вещей? Заранее спасибо.

Answer 1

Если вы хотите показать сложность какой-либо операции, вы не можете просто использовать одну точку данных, вы должны показать, как изменяется время при изменении N.

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

Еще одна вещь, о которой стоит подумать, это иметь репрезентативные значения.Например, если вы вставляете значения 1, 2, 3, … в дерево RB, это худший сценарий (я думаю), потому что он должен часто перебалансировать.Вставка случайных значений, вероятно, даст другой результат.

Answer 2

Я видел видео на YouTube, которые объясняют различные алгоритмы сортировки как с помощью анимации, так и графиков.Также обратите внимание, что Big-Oh - это наихудший случай времени работы, поэтому вам может понадобиться настроить его так, чтобы наихудший случай был выбран, чтобы выделить различия.

Я думаю, что простой график будетлучше всего со временем по оси Y и количеством элементов по оси X.