What is faster in average, btree or hash table? [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this question

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?

Answer 1

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.

Answer 2

You cannot easily compare them because they provide different functionality. The hash table is a key-value store while the tree also allows lookup based on order (previous/next, etc).

Rule of thumb: If you want to use them for a specific task, just measure which one is better.

Note: those numbers are huge, does it even fit into the memory of your machine?