What are the differences between implementing maps by hashes or trees?
What is the advantage of implementing maps by Table hash instead of binary tree?
1 answers
Doubt should be more the other way around.
If you need the data to be sorted you need the binary tree. If you need order, you need a array, or some trick with the binary tree (or not). If you can disregard order or classification then the spreading table can be useful.
The spread table has complexity O (1), that is, it is constant no matter the volume of data. It is as if it were the access time of a arrya by its index. Not the same time because the hash needs to compute the bucket where the data is before accessing.
The Binary Tree has complexity O (log n) which in many cases is close to constant. In fact, because it does not have to calculate with low data volume it is possible that it is faster than hash, even if log n gives something greater than 1. In large volumes it will be slower, but it is not such a big difference. To get an idea 1 billion elements can be accessed in just 30 steps. Although volume influences access time, it is derisory, and in some cases makes no difference.