Re:Crit-bit Trees: the best way to store sets
by ot on Tuesday September 20, 2011 @10:20AM
(#3017639)
That is true but you lose some of the most important properties of crit-bit trees, ordered operations.
If the data structure is unordered, I don't see any reason why it should be better than a normal hash table.
Re:Crit-bit Trees: the best way to store sets
by fmap on Tuesday September 20, 2011 @11:53AM
(#3018039)
The data structure is not better than a normal hash table. It is a different trade-off.
For instance, you don't have to do a rehashing step, which is important for real time applications. Memory usage is also very deterministic at 2*(n-1) words in an n element table (with 2 words per node).
If none of this matters to you and you merely want a map with fast lookups then a simple hash table is probably a better choice.
Re:Crit-bit Trees: the best way to store sets
by jbapple on Wednesday September 21, 2011 @02:35AM
(#3021030)
The string b-tree also does trie-like search without sacrificing balance:
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.59...
At the same time you will not need rehashing once the table "fills up" and since you use don't discard bits from the hash function the expected number of collisions after inserting n elements with a 32 bit hash is n / 2^32 - or 0 for reasonable values of n.
Additionally you can use clustering (e.g. build a crit-nibble tree, with 16 pointers per node - one 64 byte cache line) to reduce the number of cache misses. This can backfire spectacularly unless the data is essentially random, so the hashing step remains important.
It may not be a silver bullet, but there are some interesting trade-offs.