Observations
How expensive is an insert?
O(1)
- assuming no collisions.
Say its 1.
How expensive is a rehash?
O(N)
- where N is current size of table.
Say
its N.
When will we need to rehash?
whenever size of table is power of 2
(1,2,4,8,16, )