The article puts forward a tree as a better alternative to hashtables:
"I have become convinced that this strategy should change. The revised strategy is much simpler: there should be one fundamental set-storage type, namely a crit-bit tree. Here's how a crit-bit tree stacks up against the competition:
* A hash table supports insertion, deletion, and exact searches. A crit-bit tree supports insertion, deletion, exact searches, and ordered operations such as finding the minimum. Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data."
Oh, what's the big-O of a lookup in a tree vs lookup in a hash-table again? O(lg N) vs O(1) with bad locality of reference to boot, you say?
He's not arguing that crit-bit trees are better than hash tables, he's arguing that they are a better choice for the fundamental set datatype for languages like python, perl etc etc.
When you write an application, you know the performance requirements of the set representation you choose & can pick the most appropriate for your application. A language designer doesn't have this information: their choice of fundamental datatype affects everyone.
Bernstein is arguing that they should choose a set representation with good performance for as wide a range of features as possible rather than one that performs well for a small set of requirements, and very poorly for others.
I can see arguments both ways here, but FAIL is a bit too strong IMO.
You weaken his rhetoric; he writes like its crit-bit all the way for all purposes.
And since there is not a queue of people complaining that Python's dict is not iterable in order, I'd say he's wrong. Random access in a dict is the most common use-case by a very long chalk.
"I have become convinced that this strategy should change. The revised strategy is much simpler: there should be one fundamental set-storage type, namely a crit-bit tree. Here's how a crit-bit tree stacks up against the competition:
* A hash table supports insertion, deletion, and exact searches. A crit-bit tree supports insertion, deletion, exact searches, and ordered operations such as finding the minimum. Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data."
Oh, what's the big-O of a lookup in a tree vs lookup in a hash-table again? O(lg N) vs O(1) with bad locality of reference to boot, you say?
FAIL.