0
What is the advantage of implementing maps by table hash instead of the binary tree?
1 answer
3
The doubt should be more reversed.
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 scattering table may be useful.
The scattering 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 need to calculate 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 by not having 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 that big a difference. To get an idea 1 billion elements can be accessed in just 30 steps. Although the volume influences the access time, it is derisory, and in some cases makes no difference.
Browser other questions tagged hash
You are not signed in. Login or sign up in order to post.
Here’s a link I believe will help you: Lists, trees and table hash
– Ricardo Pontual
I think I understood what I was looking for,.
– Felipe Machado
Answer :It is more appropriate to implement the Hash table in a census when you have a large volume of data, so its great advantage is the performance, while the binary search has complexity $ O( log N)? , the search time in the hash table is practically independent of the number of keys stored in the table, that is, it has time complexity $ O(1)$. Summarizing: .
– Felipe Machado