Asking Only Whether It Is There
Last timeWhat Makes a Hash Function Good
If the only question is whether something has been seen before, the items need not be stored at all. A few bits each will do, at the cost of a wrong answer that only ever goes one way.
Sometimes the question is not where something is, or what is stored with it,
but only whether it has been seen before. That question is much cheaper to
answer, and the saving is large enough to change what is possible.
The lesson stops here
1 more paragraph to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents