0

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.

Stuart Marks
  • 127,867
  • 37
  • 205
  • 259
ip696
  • 6,574
  • 12
  • 65
  • 128
  • https://www.quora.com/Java-Why-does-get-take-O-1-time-on-HashMap – Amit Jan 18 '19 at 09:30
  • 1
    Honestly, I have no idea what these numbers without any unit are supposed to tell me. They do not even look consistent. Further, `HashMap`, and `TreeMap` have fundamentally different time complexities, so there’s no sense in asking for them in one go. – Holger Jan 18 '19 at 15:24

1 Answers1

3

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.

Eugene
  • 117,005
  • 15
  • 201
  • 306
  • `HashMap`’s resize operation will double the number of buckets, which in turn will reduce the likelihood of needing trees in particular buckets, not raise it. Converting a bucket’s list to a tree may rather happen in `put` operations independently to resize operations. – Holger Jan 18 '19 at 15:22
  • @Holger `resize` will double until the threshold of both `TREEIFY_THRESHOLD` and `MIN_TREEIFY_CAPACITY` is reached, after that, that particular bucket is transformed to a tree and kept that way (unless entries are removed to a certain point); that was my point vs resize of `ArrayList`, where it will always increase the size. I am also a bit confused about your second point ("independently" is what confuses me), as `resize` will be called from within `put` – Eugene Jan 21 '19 at 11:03
  • when the capacity is doubled, the items of each old bucket are transferred to two new buckets, depending on their actual hash code. So, inside each new bucket, there will be *at most* the same number of items as in an old bucked, but likely less. So raising the capacity may cause the number of items in a result bucket to fall below the `UNTREEIFY_THRESHOLD`, but not to raise above `TREEIFY_THRESHOLD` when it wasn’t above it before. You seem to be too much concerned with what happens with small maps, but when discussing asymptotic time complexity, small maps are irrelevant. – Holger Jan 21 '19 at 11:32
  • @Holger ah! now I understand what you meant, thank you for the comments – Eugene Jan 21 '19 at 12:08