Not always better, but for most cases where people typically use a hash table it frequently is, assuming the radix tree design and implementation is excellent. There are still a few cases where well-designed hash tables are a better choice e.g. fixed size cache maps with unique keys. But to agree with the OP, there are very few hash tables in my software these days.
The downside of radix trees is the space of algorithm designs is pretty exotic, especially high-performance implementations. It is much easier to write a good hash table implementation than a good radix tree implementation.
Not always, but take a look at this recent comparison between modern radix trees and hash maps [1].
[1] https://bigdata.uni-saarland.de/publications/ARCD15.pdf
Not always better, but for most cases where people typically use a hash table it frequently is, assuming the radix tree design and implementation is excellent. There are still a few cases where well-designed hash tables are a better choice e.g. fixed size cache maps with unique keys. But to agree with the OP, there are very few hash tables in my software these days.
The downside of radix trees is the space of algorithm designs is pretty exotic, especially high-performance implementations. It is much easier to write a good hash table implementation than a good radix tree implementation.
Depending on implementation and usage, radix trees can get extremely segmented, slowing down significantly over time.
Would you mind elaborating? I'm not quite sure what you mean by segmented here.
I'm not thecompilr, but if I understand them correctly:
In the worst case, the cache behaviour of a radix tree could be awful, if each node lives in a different cache-line, no?
I imagine this problem can be ameliorated with a custom allocator, though.
Been a while since I've studied hash-maps in depth, but with a good hash function, that wouldn't be a big worry, would it?
8 replies →
Try these string keys:
(also great for breaking string sorts)