CODEWITHSUNDEEP
javaalgorithmcollectionshashmaptime-complexity
Techfist
Techfist

Reputation: 4344

HashMap put() api time complexity

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.

Upvotes: 2

Views: 775

Answers (1)

Sunny Garg
Sunny Garg

Reputation: 1073

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.

Upvotes: 1

Related Questions