4 ms·
This is a bad idea, since double hashing with open addressing has the same benefits but is much faster. The indices are already in the cache and there's need fo
by rurban 10y ago
This is a bad idea, since double hashing with open addressing has the same benefits but is much faster. The indices are already in the cache and there's need for an additional hash table setup overhead.
Usually you go for a variant of robin-hood, cuckoo or even quadratic hashing, with the same benefits but vastly better performance. (all open addressing schemes).
And if the collision rate ("load factor"/"fill rate") is too high for your use case, you go for lower load factors, down from 90% to 50%. It's still much faster than using a complete separate 2nd data structure.
And if you need something better than a hash table, (pointers, fixed size keys, ordered, ...) you usually go for patricia/crit-bit trees.
One popular database tried a RB-tree as second data structure once (forgot the name and link. starts with R but not redis). Also see http://programmers.stackexchange.com/a/281785/27031 http://programmers.stackexchange.com/a/281785/27031, DMDScript used that also.