LinkedHashMap的实现与HashMap有何不同?

如果LinkedHashMap的时间复杂度与HashMap的复杂度相同,为什么我们需要HashMap?与Java中的HashMap相比,LinkedHashMap的所有额外开销是什么?


答案 1

LinkedHashMap将占用更多内存。正常中的每个条目只有键和值。每个条目都有这些引用和对下一个和上一个条目的引用。还有更多的内务管理工作要做,尽管这通常是无关紧要的。HashMapLinkedHashMap


答案 2

如果LinkedHashMap的时间复杂度与HashMap的复杂度相同,为什么我们需要HashMap?

您不应将复杂性与性能混淆。两种算法可以具有相同的复杂性,但一种算法可以始终如一地比另一种算法表现得更好。

请记住,这意味着:f(N) is O(N)

limit(f(N), N -> infinity) <= C*N  

其中 是一个常量。复杂性并不能说明值的大小。对于两种不同的算法,常量很可能是不同的CCC

(请记住,big-O复杂性与行为/性能有关,因为行为/性能变得非常大。它不会告诉您有关较小值的行为/性能的任何信息。NN


话虽如此:

  • 在等效用例中,性能与操作之间的差异相对较小。HashMapLinkedHashMap

  • A 使用更多内存。例如,Java 11 实现在每个映射条目中都有两个附加引用字段来表示之前/之后的列表。在没有压缩 OOP 的 64 位平台上,额外的开销是每个条目 16 个字节。LinkedHashMap

  • 性能和/或内存使用率方面相对较小的差异实际上对具有性能或内存关键型应用程序的人来说非常重要1.

1 - ...以及那些不必要地痴迷于这些事情的人。