CODEWITHSUNDEEP
javaalgorithmlinkedhashmap
Anderson
Anderson

Reputation: 19

Performance of LinkedHashMap: Big O, Memory cost, etc

It's a newbie question: what is the big O for get/put/contains for LinkedHashMap? As I understand for TreeMap it's O(logN), and for LinkedList (to search/add/delete by value), it is O(N). Does that make LinkedHashMap operates on O(logN), or does it perform better? And how does compare with HashMap in terms for performance and memory usage, etc.?

Upvotes: 0

Views: 2731

Answers (4)

Anderson
Anderson

Reputation: 19

By looking at https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html, this is what I understand now:

LinkedHahsMap by it's name, combines HashMap and LinkedList to offer O(1) operations on get/put/contains. I was confused earlier on with TreeMap. In other words, it maintains what HashMap offers with predictable order (insertion order)

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.

This is very similar to LRU: https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

Naturally the implementation of LHM requires additional LinkedList stored for each element.

Upvotes: 0

szatkus
szatkus

Reputation: 1385

Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove)

Performance characterstics are always explained in the Java documentation.

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

Upvotes: 0

amit
amit

Reputation: 178411

LinkedHashMap offers similar performance to those of HashMap (in terms of big O notation), but also allows a deterministic iteration by the order of insertion.

This means, get(), put(), contains(), are all done in O(1) (amortized average).

You can read more in the documentation.

Upvotes: 1

olegarch
olegarch

Reputation: 3891

All 3 times are O(1). By other words, time independent on dataset size. Memory is O(N).

Upvotes: 0

Related Questions