How Full Is Too Full
Last timeWhen Two Keys Collide
The cost of a lookup depends on one number: how full the table is. Keeping that number low means rebuilding the table bigger before it fills, and the rebuild is cheaper than it looks.
Everything in the last lesson came down to one number: how full the table is.
That number is not given by the problem. It is chosen, and it is maintained.
The curve the choice is made from
The flat part runs out somewhere around two thirds. That is where the table
is grown, and real libraries use thresholds in that region.
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