|
|
|
|
|
|
by aidenn0
2359 days 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. |
|
|