CODEWITHSUNDEEP
javaalgorithmcollectionshashmaptime-complexity
ip696
ip696

Reputation: 7084

Java Map realizations asymptotic complexity (HashMap, LinkedHashMap, TreeMap)

I'm trying to deal with asymptotic complexity of HashMap, LinkedHashMap and TreeMap. On different sites and articles write that on average get = O(1) and at worst - O(n). (if all keys add to one bucket).

But I read book Bruce Eckel thinking in java and there is an example of comparison

enter image description here

If you look at this data, then it goes out O(n)

I am completely confused. Can anyone explain the asymtotic complexity of Map realizations - HashMap, LinkedHashMap and TreeMap, at least for get and put? (maybe there is a good article where everything is clear and put together?)

EDIT

Most interested in the put method. Since when a certain size occurs resize() similarly as in ArrayList.

Upvotes: 1

Views: 544

Answers (1)

Eugene
Eugene

Reputation: 120848

It's called amortized O(1), meaning over some period of time when there are many entries and you often do get. You also seem to lack the understanding of O(1) - it means, it is constant. If I add more entries to a HashMap - the time that it takes to retrieve an entry is the same, be it 10 or 10 million entries in that HashMap and taking into consideration that the hashCode is implemented and does not have a dummy implementation of return 1 (this is when entries will be put into the same bucket for example).

A resize indeed happens in some cases, but it's not even close to how an ArrayList does it. An ArrayList will just make the inner array bigger, always; a HashMap will double the inner buckets up to a certain point (see when exactly here), after which it will transform a certain bucket to a Tree, making the search faster - this was added in java-8.

Upvotes: 4

Related Questions