4 ms·
Hash tables are NOT O(1). You just failed the job interview. tptacek, what do you think they are?
by bayareaguy 19y ago
Hash tables are NOT O(1). You just failed the job interview.
tptacek, what do you think they are?
- tptacek 19y agoThe bound on lookup from a hash table is O(n).
- bayareaguy 19y agoAs is the worst case in a binary tree.
- tptacek 19y agoIf you use a simple binary tree, which nobody does, you're right. If you use a red-black tree, like everybody does, you're wrong; worst case search time for a balanced binary tree is O(log n). Worst case search for a radix trie is always O(k); radix tries don't require balancing. Where did you go to school?
- bayareaguy 19y agoWell, nobody I know uses hash tables without periodically "rebalancing" them either. Where I went to school, we were taught not to compare the worst case behavior of one structure to the average of another. We were also taught not to confuse binary trees with red-black trees.
- tptacek 19y agoYour school taught you to "balance" hash tables?
- bayareaguy 19y agoThe quotes were there for a reason.
- ckuehne 19y agoI guess your school sucked. Red-black trees ARE binary search trees. Also: the worst case behavior of a hash table is in fact worse than that of a balanced (red-black tree, b-tree, avl-tree) search tree.
- bayareaguy 19y agoRed-black trees ARE binary search trees. Agreed. However the original poster said binary tree, a specific structure whose worse case behavior is O(n) just like a hash table. They didn't say binary search tree (which as you observe may refer to one of several possible structures).