algorithm - JFC 的 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. 如果答案是"is"，那么它是否使用 array-base 的实现或引用基地的实现？
3. 如果它使用 array-base，那么它是排序的还是未排序的？

我正在使用 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 变化时时间如何变化。

此外，对于较小的数据集，理论复杂性较高的算法或数据结构通常运行时间较差。

要考虑的另一件事是具有代表性的值(value)观。例如，如果您将值 1, 2, 3, ... 插入到 RB 树中，那是最坏的情况(我认为)，因为它必须经常重新平衡。插入随机值可能会产生不同的结果。