3 ms·
But you could do some hybrid, where you do greedy fill for a while and then switch to this fancier fill once your table is approaching full (using some heuristi
by SiempreViernes 2y ago
But you could do some hybrid, where you do greedy fill for a while and then switch to this fancier fill once your table is approaching full (using some heuristic)?
- gizmo 2y agoNot really because you have to use the same algorithms during subsequent lookups. Imagine you add a bunch of items with insert algorithm A, then you cross some threshold and you insert some more items with Algorithm B. Then you delete (tombstone) a bunch of items. Now you look up an item, and the slot is filled, and you're stuck. You have to proceed your lookup with both algorithms to find what you're looking for (thereby giving up any performance benefits) because the current occupancy doesn't tell you anything about the occupancy at the time when the item you were looking for was inserted.
- layer8 2y agoI would assume that you need to start early to be able to reap the benefits once the table is almost full.
- DevelopingElk 2y agoNo, it has to do with the coupon collectors problem. The key idea behind this algorithm is to do more looking for an empty spot up front.