Re:There are no good constant-time data structures
by Animats on Tuesday December 02, 2014 @08:14PM
(#8691255)
One approach is to use a hash table where each entry has a block of values, not a linear list. The entire block is always tested linearly, even though most of the values are null. Block overflow means an expensive operation to increase the size of the hash table or the blocks, but that's an insertion-time issue, not a lookup-time one.
There's still the problem of cache noise.