5 ms·

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

• aidenn0 14y ago
  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.
  • dclusin 14y ago
    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).
  • marshray 14y ago
    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.
    • aidenn0 14y ago
      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.
    • aidenn0 14y ago
      Though in general, you are right that academics tend to be over-obsessed with worst-case performance; see e.g. heap-sort.
• Jach 14y ago
  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.
  • mappu 14y ago
    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.
    • marshray 14y ago
      So you don't use std::string or dynamic_cast<>() either?
      • Ogre 14y ago
        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/n2271.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...
        • marshray 14y ago
          I think we've had this conversation before :-)
          • Ogre 14y ago
• eranki 14y ago
  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.