3 ms·
If you do O(N) work every time the hashmap is "full" and double the size of the hashmap, it's still O(N). Hand-wavy proof: If your last insert caused a rehash
by aidenn0 7y ago
If you do O(N) work every time the hashmap is "full" and double the size of the hashmap, it's still O(N).
Hand-wavy proof:
If your last insert caused a rehash, then you have done O(N) work plus O(N/2) plus O(N/4)... the limit of which is equal to O(2N), and thus only a constant factor more.