Thread: hash tables

Originally Posted by bithub

For a good balanced binary tree implementation (If you want to go this route), I suggest using a Red-Black tree. This is the same tree implementation used by gcc to implement std::map.

While it's true that any tree with constant branching factor can perform insertion/lookup in O(n log n) (EDIT: Oops, meant O(log n) ) there is still a constant factor hiding there which isn't really negligible in practice. For evenly distributed sparse sets of integers it can be better to use a tree of higher branching factor, i.e. radix tree or some other.

EDIT: Eh, radix tree wasn't exactly what I meant. My point is a tree can be a good alternative to a hash but it doesn't necessarily have to be a binary tree.