[mathgeek]

> But I believe that many people resort to using hash tables at the end of the day just because they are the easiest to use.

For me, it's a matter of avoiding premature optimization. When I end up dealing with needing to optimize my code, very rarely is the data structure the primary pain point. Just because something is "easy to use" doesn't necessarily mean that the faster alternative is worth the opportunity costs.

I prefer the Donald Knuth quote:

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."

[nvbhargava]

I totally agree. This question I'd say was more focused towards that 3% of the time. So, if you believe that there is an opportunity to optimize something non-trivial, would you implement a whole new data structure for that?

[mathgeek]

Yes. That's the point of avoiding premature optimization. You only do it when necessary and thus has the best ROI.