B-trees are an external storage technique; he means balanced binary trees.
The answer to the interview question is another question: "what operations does the container need to support?". It's not "hash tables are O(1)".
A perfect hash table does have O(1) look-ups in the worst case.
There are lots of other constraints that come to mind. Do we do frequent insertions/deletions?
What are the memory constraints?
What is the size of the unhashed key?
And many more... No data structure always wins.
Radix tries on the other hand don't hash. They're always at least O(k), and you can find the next and previous values (lexicographically) in O(k) as well. They're also more compact and you never have to resize your tables.
That's important to keep in mind, particularly for DoS resistance. But isn't it really as much of an oversimplification as saying they're O(1)?
In practice, there are inexpensive ways to consistently avoid that worst case. But you do have to know to do it.
Hmm reminds me of some code I should probably go double check...
No, because big-oh notation implies worst case. It's an asymptotic upper-bound. If you want to talk about average case, then you need to qualify what your assumptions are. So insertion into a hash-table is O(n), but if we assume an even distribution of keys with a sufficiently large table, then insertion is O(1).
This is kind of a silly semantics argument... but, if you interview for a job and look like a deer in the headlights when I said hash tables aren't O(1), NO HIRE.
(I'll assume you're talking about the quicksort algorithm rather than the qsort() function because you're comparing it to hash table accesses in general rather than a specific implementation of them.)
But I'm not sure I agree. The worst case for quicksort is an already-sorted list. I run into this scenario all the time, though usually in a slightly different form. When I iterate through the elements of one of the tree-based containers std::set and std::map they emerge in sorted order. If, inside my loop, I then insert them into a similar container I end up with worst-case performance. The other day I replaced std::set with std::unordered_set and saw a dramatic increase in performance, although it may not have been entirely due to this effect.
On the other hand, a non-crappy hash function should be available to everyone at this point. Personally I like FNV-1a, but haven't found an issue with whatever my C++ standard library is supplying. I have spoken with other programmers though who didn't realize hash tables needed some empty space to perform well or had stumbled into a pathological case with their oversimplified hash function.
This is kind of a silly semantics argument... but, if you interview for a job and look like a deer in the headlights when I said hash tables aren't O(1), NO HIRE.
Gee Ptacek, what do you have against deer? I can just imagine some poor interviewee with a bright desk lamp shining into his eyes...
While there may be a set of textbooks and papers for which the editors would have flagged "worst cast O(..)" as redundant, I think it's relevant to point out that the use of big-oh notation in mathematics predates computer science. So to the extent algorithm analysis is a branch of mathematics, those who use big-oh in this more general way are in fact consistent with the larger body of work.
I find this a bit confusing because it's unclear to me what Knuth actually endorses for use in average case description.
Wikipedia: Although developed as a part of pure mathematics, this notation is now frequently also used in the analysis of algorithms to describe an algorithm's usage of computational resources: the worst case or average case running time or memory usage of an algorithm is often expressed as a function of the length of its input using big O notation. Wikipedia and the web in general have many examples of "worst case O(...)" which would be redundant under your convention.
So clearly one needs to be vigilant about assumptions when discussing average case, but common usage does not agree that big-oh notation implies worst case.
[1] Every database implementation techniques lecture compares the two. See, e.g., http://infolab.stanford.edu/~hyunjung/cs346/.
There is a tradeoff of computation (doing binary search inside the node) and amount of storage (keeping less pointers). In environments where memory access is much more expensive than a CPU instruction, it is preferable to perform these computations than to have to read all the extra pointer data to jump to the right places.
In fact, a breed of cache-friendly data structures are precisely based on the B+Trees but with even less pointers, having the algorithm compute these pointers instead (CSS-, CSB-Trees)
For some reason, binary trees look real cool when you learn about them from a textbook that people sometimes forget about hash tables. But, that might just be my personal experience from candidate interviews.