4 ms·
That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees, by constructing an unordered tree on the hash values of t
by fmap 15y ago
That's a very good point. One way to circumvent this problem is to combine hashing and crit-bit trees,
by constructing an unordered tree on the hash values of the set elements. The nice thing here is that if the
hash function behaves like a uniform random variable the resulting tree will be balanced. Furthermore,
without ordering the implementation is trivial.
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.
- ot 15y agoThat 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.
- fmap 15y agoThe 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.
- jbapple 15y agoThe string b-tree also does trie-like search without sacrificing balance: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.5939 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.59...