News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.