If the number of baskets in the unordered map/set is equal to the number of elements to insert, is the constant insertion time of each element guaranteed in the worst case?

  • Is this how it can be guaranteed? It all depends on your hash function. - AnT
  • @ user238463: Misunderstood the question, deleted the answer. - VladD

1 answer 1

No, of course, not guaranteed. Write a "bad" hash function (for example, always returning the same value) - and easily get the linear insertion time, because all the inserted elements will go into one basket.

You get the perfect linear insertion time only if the external hash function (together with the hash value conversions inside the unordered_map ) somehow miraculously formed the ideal hash function . But it is not necessary to count on this in the general case.