Search code examples
algorithmbinary-search-treehashtable

O(log n) vs O(1)


For practical purposes, is hashing significantly better than using a BST? I don't like the fact that hash tables have a lot of things going on under the hood. In practice is log(n) so significantly worse than O(1) that I should avoid using a BST in place of a hash table where possible?


Solution

  • On the one hand, a hash table is (asymptotically) O(1) (IFF you have a O(1) hash algorithm for your data), but potentially O(n) for the occasional write. That is, if you have a suitable hash algorithm. And no adversarial data. Worst-case, someone will feed you data that all hash to the same slot, so both your reads and writes become O(n) (again, with a O(1) hash algorithm).

    On the other hand, a BST should be log(n) for reads, and log(n) (although slightly variable) for writes.

    In the general case, I'd pick whichever is more convenient to use. In specific cases, I would benchmark, using realistic data.