Search code examples
data-structureshashtabletime-complexityb-tree

What is faster in average, btree or hash table?

I try compare b-tree and hash table look up time complexity.

B-tree needs log_b(n) operations and log_b(n) <= b if n <= b^b so for b = 10 it is 10^10 at any case and I have 10 operations for look up. Hash table needs 1 operation for look up in average. But if I have a 10^10 keys and size of my hash table is 10^10/10 then it will be 10 operation for look up in average case (for separate chaining), or not?

I think it is a lot theoretical. I want know, what is better in practice? why?

Solution

  • what is better in practice?

    It depends.

    A b-tree is always O(log n) performance.

    A hash table is O(1) (much better than the b-tree) with

    1. A good hash function for your data.
    2. Enough hash buckets.

    If those criteria are not met then the hash table will tend towards O(n) (ie. much worse than the b-tree).

    Summary: good hash function: hash table will usually be better. A b-tree is consistent without needing a hash function.

    In practice n is not large, and even a generic hash will be good enough to achieve close enough to O(1) that spending time on the question is a pointless optimisation.

    Real answer: until you measure performance and determine that data structure lookup times are significant put your optimisation effort where your users will see a significant difference.