3 ms·
potential offtopic question here: i always wondered about multi-layered hashtables, i.e. instead of a linked list for resolving collisions use a second hashtab
by stefs 10y ago
potential offtopic question here: i always wondered about multi-layered hashtables, i.e. instead of a linked list for resolving collisions use a second hashtable with a different hash function (and then maybe a linked list on the 3rd level).
i guess this might bring some potential improvements in case of a hashtable with too many collisions but a prohibitively expensive overhead in all other cases. i.e. it might alleviate a hashtable that was already broken.
- rurban 10y agoThis 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.