Why map put is expected O(1)
Updated
Put hashes the key to a bucket and writes the pair there. With a good hash and a load factor under the resize threshold, that bucket is tiny, so put is expected O(1). Resize is occasional O(n) amortized.
What to focus on
Expected is not a worst-case promise. Adversarial keys or a broken hash can chain n entries in one bucket. Do not say put is O(1) without expected or amortized.
Worked examples
fresh key
a = [4, 1, 9] already stored, put 7→5- hash 7, empty-ish bucket, write
Result: expected O(1)
overwrite
a = [4, 1, 9], put 1→0- hash 1, find 1, replace value
Result: expected O(1), not O(n) scan of all keys
resize
a = [4, 1, 9, 7, 8] filling the table- one put may copy every pair
Result: that put is O(n), amortized still ~O(1)
Try it
Write putCost(m, k, v). m is the hash map. k is the key. v is the value. Return expected O(1) for a new key or an overwrite. Name one put that is O(n) because of resize. a = [4, 1, 9] already stored, put 7→5 → expected O(1). a = [4, 1, 9], put 1→0 → expected O(1), not O(n) scan of all keys. a = [4, 1, 9, 7, 8] filling the table → that put is O(n), amortized still ~O(1).
keys are integers. The table is non-empty. Resize may fire on a put.