Post

Hash tables, or how to leverage the sinking feeling of loneliness you get when you look at the sky

If I didn't already know what a hash table was, I think I would hate this intro, because it's promising something (a perfect hash) that we're not actually going to get. So already I'm thinking about how we're going to get something like that and how impossible it seems.

Whether I will be able to continue following the rest of the presentation or not is up in the air, because every subsequent sentence is going to be tested against this bar and I'm going to get more and more confused about how this is getting us where we were supposed to be going.

The fact that the original paragraph is memorable is actually going to work against you here, because it makes it less likely that I'll just forget about it and go along with the bait and switch.

I see your point. (I disagree, but see your point.) Please have a look, tell me what you think! ccanonne.github.io/files/compx2...

Looking at the notes, this seems to be for a senior-/ grad-level class, so I guess this is meant for someone who already knows perfectly well what a hash table is and you're just briefly reviewing the subject? I guess in that case it doesn't matter very much.

That said, it seems like this could use some proofreading -- it looks like m is used inconsistently for both |X| and for log_2 |X|, alternating between the two; what's called a "dictionary" here would normally be called a "set" (although of course the difference under the hood is minimal); etc.

Also the statement of theorem 32 comes close -- it says to fix integers m and m', which are then never referenced again, but then we have integers M and N in the statement which are numbers of bits.

"If we currently store 5 $m$-bit strings, we would rather avoid using $\Theta(2^m)$ bits of memory... (there are 2^m distinct $m$-bit strings.) $m$ is subsequently used in the same paragraph to denote what had been $2^m$ in the previous sentence.