Thursday, January 12, 2017

Episode 3 - Rolling Hashes and Bloom Filters

For this week, you should try this problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1370

In Episode 3, I will cover the natural marriage of two ideas: rolling hashes and bloom filters. I'll be covering the idea behind the rolling hash technique, how Rabin-Karp works using this technique, and how the hashes can be stored in a bloom filter. I'll also show how a bloom filter is faster in practice than using the usual hash table when storing string hashes.

See you live! (time, stream, channel)

2 comments: