9 ms·
> Is there a good, general, incremental rehashing scheme? Trees.
by throwawayish 10y ago
> Is there a good, general, incremental rehashing scheme?
Trees.
- gpderetta 10y agoAs a C++ programmer, my default dictionary is usually an std::map (which is just an RB-tree), so, yes agree 100%. But the amortized O(1) lookup of hash tables is hard to beat. edit: s/bass/beat/
- throwawayish 10y ago> But the amortized O(1) lookup of hash tables is hard to beat. On the other hand: the performance characteristics of trees are much easier to predict. And in many cases a HT lookup isn't distinguishable from a tree lookup, at least if it's a dedicated application data structure, like some index or so. I feel like HTs are very good for smaller structures (excellent example: dictionary/hashtable-based interpreters), but for larger data structures (e.g.: indices) ... not so much.