On Friday, 22 April 2016 at 21:38:41 UTC, Johan Engelen wrote:
I don't understand exactly what you mean; do you propose to […] do a linear search when the shadow data structure says the item is present?
That's the idea. As long as you can reduce the need to do a full linear search by, say, 1 : 1000, it would be enough to make the quadratic behaviour disappear into the noise.
That being said, I did some estimates, and since the keys are only 8 bytes in size, Bloom filters in particular might not be worth it in this case, unfortunately. Quite sad, actually. I like Bloom filters.
— David
