3 ms·
There are no good constant-time data structures
- deleted 12y ago[deleted]
- TheLoneWolfling 12y agoCoocoo hashing with a cryptographic hash (+ salt, potentially) doesn't leak any useful information, contrary to what this says. The only information you get with a lookup in a coocoo map if if either of the cache lines containing the two slots are in cache or not. Which is irrelevant, as to get anything useful you'd have to reverse the hash. Not to mention if cache is really a problem just use a non-temporal read on both lookups (and always do both lookups, and make sure the hashmap is locked into physical memory). This is pretty close to data-independent time.
- MichaelCrawford 12y agothe title is somewhat misleading; he's discussing crytography. I'm a huge fan of lookup tables, which can transform any algorithm whose input is sufficiently small into a constant-time operation.