You're like the 4th person I've seen that read (some) of this article and pulled this tree vs. hash thing out of it. It's a throwaway point. Binary trees provide comparable performance to hash tables, but also provide efficient access to ranges of keys. Binary trees support more operations efficiently than hash tables.
The article isn't about some war I've declared on hash tables.
For average lookup time, which is a reasonable context to assume in the preceding comment, yes they are.
If you had read more than (some) of my comment you might have gathered that was my entire point. The first page of your post was a throwaway point... nothing to do with your actual point, which seemed to be Radix Tries. It would've been nice to dispense with the distraction was all I was saying.
I know that given a lot of collisions that hash tables degenerate into linear insertion and lookup... and I did point out that binary trees are better for several things, but I still maintain that you can't just outright claim one is better than the other for every situation.
Oh, and as for failing the job interview... not really sure why that was necessary. You don't make a stronger point by being a dick about it.
With a good hash function (collision resistant), the amortized cost of lookup is O(1), even if you need to resize the table.
tptacek, what do you think they are?
Worst case search for a radix trie is always O(k); radix tries don't require balancing.
Where did you go to school?
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.
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).