Expected O(1) map get versus worst O(n)
Updated
Get is expected O(1) because a good hash plus a low load factor keeps each chain tiny, often 0 or 1 pair. If every key collides into one bucket, get walks n pairs and is O(n). The ADT name does not forbid that worst case.
What to focus on
Do not write 'get is O(1)' without 'expected'. Adversarial hashes, a table that never resizes, or hashing a huge object poorly are how you get the linear walk.
Worked examples
short chain
a = [4, 1, 9] as {4:2,1:8,9:3}, get 1, well mixed- hash 1, chain length about 1
Result: expected O(1)
one bucket
a = [4, 1, 9] all chained together, get 9- walk 4, then 1, then 9
Result: O(n) this call
empty
a = [], get 4- empty bucket / no pairs
Result: O(1) miss
Try it
Write getCost(m, k). m is the hash map. k is the key. Return a cost label for that get: expected O(1) when the chain is short, O(n) when every key shares one chain. a = [4, 1, 9] as {4:2,1:8,9:3}, get 1, well mixed → expected O(1). a = [4, 1, 9] all chained together, get 9 → O(n) this call. a = [], get 4 → O(1) miss.
keys are integers. Empty is in the cases.