据我了解,
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 的内部数据结构。
- HaspMap 是使用 哈希表?
- 如果答案是"is",那么它是否使用 array-base 的实现 或引用基地的实现?
- 如果它使用 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。谁能给我一些关于这些事情的简要解释?提前致谢。
最佳答案
如果你想展示一些操作的复杂性,你不能只使用一个数据点,你必须展示当 N
变化时时间如何变化。
此外,对于较小的数据集,理论复杂性较高的算法或数据结构通常运行时间较差。
要考虑的另一件事是具有代表性的值(value)观。例如,如果您将值 1, 2, 3, ...
插入到 RB 树中,那是最坏的情况(我认为),因为它必须经常重新平衡。插入随机值可能会产生不同的结果。
关于algorithm - JFC 的 HashMap 和 TreeMap 之间的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3648268/