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 fear many students would have a hard time believing that the size of the universe, eg all possible grayscale images or 2^(8hw) bits, is an important quantity. They would rightfully say that what matters is the size of one image, because that's what you store and you will never store all possible

images. Space efficiency is not the most intuitive question to ask first, because it is very easily optimized. For n images, you need at least 8hwn bits, and it seems very intuitive that you're not going to need much more than that, anyway much much less than 2^{8hw}. In fact, I bet the majority

of the students can come up with a naive structure that costs exactly o(8hwn) bits of storage. In addition, the very computer they're running their structure on clearly cannot store anything near 2^{8hw} for images with more than 4 pixels, without accounting for data structures. So why would

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.

Mmh... Where am I using m for log |X|? That's probably a typo to be fixed, but I cannot find it.