Seems somewhat vague, I think it could be a lot more accurate. I'm a bit surprised to see it here.
It claims that it's a myth that "trees are better" than hash tables and just describes trees as better for "finding inexact matches", as in the example "finding all names that begin with B". That's too vague. It's misleading because:
1. Trees can't just answer any random vague questions, such as "Find all names that have a P anywhere". That doesn't really describe the advantages of trees. I think a more accurate formulation would be "iterating over a range of values" or "finding values based on some ordering" (eg. find the smallest element bigger than X). Or for walking the entire contents in some predefined order. Sure, this is not an article about trees, but it doesn't take more than two sentences to describe that in a much better manner.
2. For any of the former query patterns, trees are actually much better than hash tables. That's definitely not a myth, which this article would sorta have you believe.
> Chained hash tables are a very good idea. Problem solved.
Wrong. If you don't resize your hash table, the complexity of accesses will degrade linearly as it exceeds its size. If your hash uses, say, 100 buckets each with a linked lists and stores N > 100 values, an access has complexity O(N) (sure, O(N/100) in the best case (assuming perfect spread of hash keys), but that's really O(N)).
Finally, "The worst case is terrible" myth part seems somewhat naive. I think it should at least mention the idea of hash table collision DOS attacks. "This doesn't happen in practice" unless there's some attacker out to get you by triggering that. There's plenty of examples of that happening in practice, of systems vulnerable to that. See example presentation here:
http://www.youtube.com/watch?v=R2Cq3CLI6H8&lr=1 Sure, that's not a reason to switch away from hash tables, but it's definitely something to consider when using them. I get a bad flavor from this simplification of "yeah, this doesn't happen in practice, at least as long as you know what your keys are".
It claims that it's a myth that "trees are better" than hash tables and just describes trees as better for "finding inexact matches", as in the example "finding all names that begin with B". That's too vague. It's misleading because:
1. Trees can't just answer any random vague questions, such as "Find all names that have a P anywhere". That doesn't really describe the advantages of trees. I think a more accurate formulation would be "iterating over a range of values" or "finding values based on some ordering" (eg. find the smallest element bigger than X). Or for walking the entire contents in some predefined order. Sure, this is not an article about trees, but it doesn't take more than two sentences to describe that in a much better manner.
2. For any of the former query patterns, trees are actually much better than hash tables. That's definitely not a myth, which this article would sorta have you believe.
> Chained hash tables are a very good idea. Problem solved.
Wrong. If you don't resize your hash table, the complexity of accesses will degrade linearly as it exceeds its size. If your hash uses, say, 100 buckets each with a linked lists and stores N > 100 values, an access has complexity O(N) (sure, O(N/100) in the best case (assuming perfect spread of hash keys), but that's really O(N)).
Finally, "The worst case is terrible" myth part seems somewhat naive. I think it should at least mention the idea of hash table collision DOS attacks. "This doesn't happen in practice" unless there's some attacker out to get you by triggering that. There's plenty of examples of that happening in practice, of systems vulnerable to that. See example presentation here: http://www.youtube.com/watch?v=R2Cq3CLI6H8&lr=1 Sure, that's not a reason to switch away from hash tables, but it's definitely something to consider when using them. I get a bad flavor from this simplification of "yeah, this doesn't happen in practice, at least as long as you know what your keys are".