2

So I was reading about Java collections api's, and was wondering about HashMap put() api, as per doc's it says its an constant time operations, but what confuses me is whether rehashing was taken into considerations as part of time complexity calculation or not.

ArrayList add() api on the other side clearly states its amortised o(n) i.e to add n element it will take n amount of time, why don't it applies to HashMap put then? though HashMap dynamically create bigger buckets upon reaching load factor, and re applies hash to existing entires to determine new bucket location.

any help on explaining above will be highly appreciated, let me know if this questions needed to moved to some other section, before down voting it.

Thanks.

OmG
  • 18,337
  • 10
  • 57
  • 90
Techfist
  • 4,314
  • 6
  • 22
  • 32
  • 3
    Possible duplicate of [HashMap vs. ArrayList insertion performance confusion](http://stackoverflow.com/questions/30066806/hashmap-vs-arraylist-insertion-performance-confusion) – Borre Mosch Jan 03 '17 at 12:12

1 Answers1

1

whenever the table becomes too full, a new table that is bigger by a constant factor (e.g., twice as big) is allocated and all elements are moved from the old table to the new one. Therefore, a single specific call of put() can sometimes run in Θ(n) time, but (starting from an empty table) an entire sequence of n calls of put() will always run in expected O(n) time - which is amortized expected O(1) time per operation.

Sunny Garg
  • 1,073
  • 1
  • 6
  • 13
  • so this means, its not constant O(1), and for higher data loads, performance of HashMap put() will get affected. – Techfist Jan 03 '17 at 12:17
  • If you expect a big amout of data, you can set capacity explicitly: HashMap h = new HashMap(3000), in which case rearrangements will be less frequent or not happen. – cyanide Jan 03 '17 at 12:51
  • @Techfist that's not really how it works. If you have K `put` operations, they will always take a total of O(K) time. Within any single program the average time of `put`s will always be O(1). – Louis Wasserman Jan 03 '17 at 18:38