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