如果LinkedHashMap的时间复杂度与HashMap的复杂度相同,为什么我们需要HashMap?与Java中的HashMap相比,LinkedHashMap有哪些额外的开销?
LinkedHashMap将占用更多内存。普通HashMap
中的每个条目都只有键和值。每个LinkedHashMap
条目都具有对下一个和上一个条目的引用和引用。尽管通常这是无关紧要的,但还需要做更多的内务处理。
如果LinkedHashMap的时间复杂度与HashMap的复杂度相同,为什么我们需要HashMap?
您不应将复杂性与性能混淆。两种算法可以具有相同的复杂度,但是一种算法始终可以比另一种算法表现更好。
请记住,f(N) is O(N)
表示:
limit(f(N), N -> infinity) <= C*N
其中C
是常数。复杂度并不能说明C
值的大小。对于两种不同的算法,常数C
很可能是different。
((请记住,大[0]复杂度与行为/性能有关,因为N
变得非常大。对于较小的N
值,它不会告诉您有关行为/性能。)
说过:
在同等使用情况下,HashMap
和LinkedHashMap
操作之间的性能差异相对较小。
A LinkedHashMap
使用更多的内存。例如,Java 11实现在每个映射条目中都有两个附加的参考字段,以表示之前/之后的列表。在没有压缩OOP的64位平台上,每个条目的额外开销为16个字节。
性能和/或内存使用方面的相对较小的差异实际上对具有性能或内存关键应用程序的人很重要1。
1-...以及对那些不必要地迷恋这些事情的人。
LinkedHashMap是有用的数据结构,当您需要了解Map键的插入顺序时。一种合适的用例是实现LRU缓存。由于LinkedHashMap的顺序维护,因此与HashMap相比,数据结构需要额外的内存。如果不需要插入顺序,则应始终使用HashMap。
HashMap和LinkedHashMap之间还有另一个主要区别:对于LinkedHashMap,迭代效率更高。
因为LinkedHashMap中的元素相互连接,所以迭代需要的时间与地图的大小成正比,而不管其容量如何。但是在HashMap的情况下;由于没有固定顺序,因此对其进行迭代需要的时间与其容量成正比。
我在blog上添加了更多详细信息。
[HashMap
不维护插入顺序,因此不维护任何双向链表。
LinkedHashMap
的最显着特征是它保持键值对的插入顺序。 LinkedHashMap
使用双重链表进行此操作。
LinkedHashMap
的条目看起来像这样:
static class Entry<K, V> {
K key;
V value;
Entry<K,V> next;
Entry<K,V> before, after; //For maintaining insertion order
public Entry(K key, V value, Entry<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
通过使用之前和之后-我们跟踪LinkedHashMap
中新添加的条目,这有助于我们保持插入顺序。
在参考上一个条目之前,之后是指LinkedHashMap
中的下一个条目。
有关图表和逐步说明,请参阅http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html
LinkedHashMap继承了HashMap,这意味着它使用HashMap的现有实现将键和值存储在Node(条目对象)中。除此之外,它还存储一个单独的双链表实现,以保持输入键的插入顺序。
看起来像这样:
头节点节点1 节点2 节点3 节点4 头节点。
因此,额外的重载将保持在此双向链接列表中的插入和删除。好处是:保证迭代顺序为插入顺序,而不是HashMap中的插入顺序。