9. Table Doubling, Karp-Rabin

https://www.youtube.com/watch?v=BRO7mVIFt08

Lecture Notes: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec09.pdf


1. in hashing, suppose n is the number of keys and m is the number of slots in the hash table. We want m to similar size to n. But n may grow or shrink, so we need to grow and shrink table to get better performance (and rehash). When grow, double the size. When shrink, wait until n is m/4 and then decrease m by half.

Amortized cost, like paying rent $1500/month = $50/day

2. Karp-Rabin algorithm: rolling hash. Lots of common bits between two hash. Easy to append one bit and remove the first bit.