1

There are constant number of buckets in the hashmap (let's say b)

We have N elements and assume N is very large and N >> b

Now each bucket contains N/b elements, assuming our hash function is good.

If we store elements in bucket as linked list, then searching in list of N/b elements is still O(N). Even if we assume that the elements in each bucket are stored as a tree, still searching in a tree of N/b elements is O(logN).

I know that b doubles every time the load factor reaches a threshold. Does this make b itself O(N). If that's the case then O(1) is explained. But if b is anything other than O(N) then how do we explain O(1) operations on map?

The word amortized is used to describe the O(1), which I assume means average case rather than worst case. But even in the average case, I don't see how it's O(1).

arahant
  • 2,203
  • 7
  • 38
  • 62
  • 1) The "amortization" refers to cost of expanding `HashMap`'s main array. This does not apply to `get`. 2) On average (assuming non-pathological hashing), the average chain length will be 2 or 3 (depending on the load factor). That makes searching the chain `O(1)`. – Stephen C Nov 17 '19 at 05:11
  • 2
    The javadoc says: *The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed* And the load factor is 0.75 by default. So the number of elements in the ap is always less than 0.75 * b. So your premise that N >> b is a wrong premise. – JB Nizet Nov 17 '19 at 07:57

0 Answers0