Hacker News Reader

Comment by chojeen | Hacker News Reader

> Engineers irrationally avoid hash tables...

Really? That seems about as likely as the statement 'carpenters irrationally avoid using screws'.

Language affects matters here, I think. I haven't met a Python programmer who doesn't love dictionaries, but I've seen C programmers (and to an extent, C++ programmers where 'std::map' is a red black tree) that avoid them because they have to roll their own or find and trust (and learn how to use) someone else's. Java programmers are more mixed. When the language forces you if you want to have nested hash tables to write "Map<String, Map<String, Map<String, Map<String, String>>> > meta_data = new HashMap<String, Map<String, Map<String, Map<String, String>>> >();" instead of "meta_data = {}", it's a pretty strong incentive to not use these things.

To be fair to the C++ programmers, there are several legitimate reasons to avoid std::map<> - for instance, if your project doesn't use exceptions.

So you don't use std::string or dynamic_cast<>() either?

It's typical in game development to disable both exceptions and RTTI entirely. dynamic_cast is out on either of those counts. std::almost_everything is out due to exceptions.

EA released a GPL'd "EASTL" library a few years ago for those and other reasons, you can read all about it here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...

I think we've had this conversation before :-)

I've posted that link once or twice before (once or twice literally, not sarcastically), it wouldn't surprise me if I was replying to you in one of those instances :)

Here, I found it, we both posted in this thread, but not to each other: http://news.ycombinator.com/item?id=3560158

Perhaps I saw that link on Reddit?

Indeed, I find academia is averse to hashtables (because of the poor worst-case performance) but engineers think they are the best thing since sliced bread.

Agreed! And taken to the logical extreme often times they are used as an excuse for lazy thinking. One example is stream processing where you're processing lots of messages per second and typically have some sort of originating request ID. Keeping a map of request ID's -> handlers gets very expensive if your goal is low latency (because you perform the map lookup on every operation).

This "worst-case" issue seems silly to me.

If all your elements magically hash to the same bucket somehow and you end up having to make a list or a tree out of them, you're still no worse off than if you used a list or a tree in the first place.

Most hash-table implementations either re-hash or use an O(n) lookup structure. And replace "magically" with "a malicious attacker" and you see it does come up more often.

Though in general, you are right that academics tend to be over-obsessed with worst-case performance; see e.g. heap-sort.

I agree, it's a straw man. Also, who ever implements their own data structures anymore? These days people use native-language maps freely, which may be implemented as trees or hash tables.

Reply on news.ycombinator.com