•Each
insert gives us 3 tokens
–1
token for that insert
–1
token for rehashing this item the first time
–1 token for rehashing another item that already got rehashed once
or more
(since we rehash on double the size,
# of items never hashed = # of items already
hashed once or more)