[krka]

True, if the lookup actually implemented this, it would be more divisions. This might partly be why it did not get implemented at all. With a sparse index (25% empty capacity) we should quickly run into empty slots anyway in most cases, and if we mostly expect hits the check would not be useful anyway.

For deletions, neighbour entries would bubble up into their correct slots to preserve that property.

[krka]

Now when I'm at an actual computer, I see that it was implemented, at least in the Java version. Removing that made for a 30% speed increase: https://github.com/spotify/sparkey-java/pull/65