🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: How Hashing Works: all 13 questions

Quiz: How Hashing Works · Question 8 of 13

Why is inserting into a hash map still O(1) on average even though resizing costs O(n)?

Why is inserting into a hash map still O(1) on average even though resizing costs O(n)?

  1. A.Resizing never happens
  2. B.Resizes are rare (the size doubles each time), so their cost spread over all inserts is O(1) each
  3. C.Resizing runs in a separate thread
  4. D.The O(n) is ignored by convention
Answer & explanation

Correct answer: Resizes are rare (the size doubles each time), so their cost spread over all inserts is O(1) each

Doubling means n inserts cause only O(n) total rehashing work — amortised O(1) per insert.

Can you get the rest right without peeking?

Take the timed Quiz: How Hashing Works quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →