4 ms·

As a programmer, I always use an ordered map (Java TreeMap) in preference to hash tables. My reasons: - It is much easier to write a transparently correct comp

As a programmer, I always use an ordered map (Java TreeMap) in preference to hash tables. My reasons: - It is much easier to write a transparently correct comparison method for a new object that I want to use as a key. With hash tables you need to worry that your hash function might not be properly distributed. - With hash tables you have to worry that your language's under-the-hood resize/reallocate algorithm works well, or you need to make sure you choose the capacity and load factor numbers correctly. Even if things work as expected, you might end up paying a penalty because, for example, the array backing the hashtable was auto-resized to 128 million elements when you only need 70 million. - Java TreeMap has lots of cool utility methods like pollFirstEntry (pull off the first K/V pair), higherMap (view of map that only includes pairs with higher key), etc. - TreeMap key traversal is deterministic!! The worst bug I encountered in years of programming work was caused by non-determinism in HashMap traversal (you could blame Java's implementation here, I suppose). - The O(1) vs O(log N) performance difference is minor to the point of being undetectable in every case I've ever encountered. - When you do something with the data in the map, you often want to sort by key anyway: might as well have the sort taken care of by the data structure.

kodablah 7y ago
You should reach for the best tool for the job instead of giving job-specific reasons for your general choice. Without going into detail explaining how your bullets either don't apply to most uses, prematurely code for a future case that may not exist, dismiss performance, reference other languages as if language implementation is not a factor in the choice, etc... suffice to say they both have their place and in general you probably shouldn't reach for an ordered map over a unordered one without reason. I.e. it shouldn't be your default choice in most languages and it'd be bad advice to give other programmers.
- naniwaduni 7y ago
  The problem with choosing "the best tool for the job" for every job is that now you have a lot more unknown unknowns and they don't generalize when you find them.
- ummonk 7y ago
  An ordered map is much better as a default simply because it can do everything that an unordered map can. Choosing to use an unordered map instead is a premature optimization that is nearly always unnecessary.
  - GeneralMayhem 7y ago
    That argument works both ways, though. An unordered map has the narrower interface and generally better performance, so it's much better as the default. Choosing to use an ordered map instead is YAGNI interface bloat that is nearly always unnecessary.
    - deleted 7y ago
      [deleted]
  - mantap 7y ago
    IMO, premature optimization doesn't apply to cases where you are making general decisions about policy or defaults, otherwise you can get into a "death by a thousand cuts" situation where none of your functions are slow individually but the whole program is slow (i.e. big overheads). To me, premature optimization means don't optimize a specific function unless you know it is slow. I'd also say that premature optimization doesn't apply in cases where both alternatives are equally easy to write.
    - mlyle 7y ago
      On the other hand, if you pick a TreeMap--- odds are it will be a non-issue either way. If it does show up on your profiles, it's easy to reconsider and say "I don't think I'll ever access this in order, after all..." and change it and see if you see a benefit.
    - JadeNB 7y ago
      > I'd also say that premature optimization doesn't apply in cases where both alternatives are equally easy to write. I think that premature optimisation applies not only to ease of writing, but even more to ease of debugging.
- loeg 7y ago
  Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.
  - kccqzy 7y ago
    Cache locality issues can be fixed by using a good allocator (or a good compacting GC).
    - AstralStorm 7y ago
      How can an allocator optimize the layout of a dynamically sized structure that's being changed without compacting? Now, compacting is an O(n) memory move plus additional calculation to figure out optimal-ish layout. (Can be amortized, but it's same as amortizing hash table resizing. Optimal layout cannot be decided without profiling, and that's expensive.)
dajohnson89 7y ago
doesn't this force you to define a comparator for everything though?
- _greim_ 7y ago
  As opposed to defining a hash code for everything, yes. Parent asserts that writing obviously-correct comparators is easier.
  - 91aintprime 7y ago
    funny enough, a hash code defines an order on a set
    - tempguy9999 7y ago
      Is it in any sense a useful order though? You can assign any order to any set of objects, but you'd want it to be useful. A hash - the more hash-ey it is, the less the order means AFAICS.
      - n3k5 7y ago
        For the purpose of making a tree data structure, all linear orderings would be equally useful. Hashing only provides a partial order, so it's important to choose a hash function that won't assign the same hash to large batches of items. But it only needs to have this property for hashes of one particular size, whereas a hash map requires a function that behaves well for a variety of hash sizes. So there's an opportunity for using a cheaper hash function.
  - LgWoodenBadger 7y ago
    IDEs have had good equals/hashcode auto-generation mechanisms for years. Java itself introduced Objects.hash(Object...) in 1.7 https://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash(java.lang.Object...) https://docs.oracle.com/javase/7/docs/api/java/util/Objects.... It's never really been an issue at all to implement equals/hashcode, which you're required to do for effectively all Collections-based usage anyway.

kodablah 7y ago

You should reach for the best tool for the job instead of giving job-specific reasons for your general choice. Without going into detail explaining how your bullets either don't apply to most uses, prematurely code for a future case that may not exist, dismiss performance, reference other languages as if language implementation is not a factor in the choice, etc... suffice to say they both have their place and in general you probably shouldn't reach for an ordered map over a unordered one without reason. I.e. it shouldn't be your default choice in most languages and it'd be bad advice to give other programmers.

naniwaduni 7y ago
The problem with choosing "the best tool for the job" for every job is that now you have a lot more unknown unknowns and they don't generalize when you find them.
ummonk 7y ago
An ordered map is much better as a default simply because it can do everything that an unordered map can. Choosing to use an unordered map instead is a premature optimization that is nearly always unnecessary.
- GeneralMayhem 7y ago
  That argument works both ways, though. An unordered map has the narrower interface and generally better performance, so it's much better as the default. Choosing to use an ordered map instead is YAGNI interface bloat that is nearly always unnecessary.
  - deleted 7y ago
    [deleted]
- mantap 7y ago
  IMO, premature optimization doesn't apply to cases where you are making general decisions about policy or defaults, otherwise you can get into a "death by a thousand cuts" situation where none of your functions are slow individually but the whole program is slow (i.e. big overheads). To me, premature optimization means don't optimize a specific function unless you know it is slow. I'd also say that premature optimization doesn't apply in cases where both alternatives are equally easy to write.
  - mlyle 7y ago
    On the other hand, if you pick a TreeMap--- odds are it will be a non-issue either way. If it does show up on your profiles, it's easy to reconsider and say "I don't think I'll ever access this in order, after all..." and change it and see if you see a benefit.
  - JadeNB 7y ago
    > I'd also say that premature optimization doesn't apply in cases where both alternatives are equally easy to write. I think that premature optimisation applies not only to ease of writing, but even more to ease of debugging.
loeg 7y ago
Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.
- kccqzy 7y ago
  Cache locality issues can be fixed by using a good allocator (or a good compacting GC).
  - AstralStorm 7y ago
    How can an allocator optimize the layout of a dynamically sized structure that's being changed without compacting? Now, compacting is an O(n) memory move plus additional calculation to figure out optimal-ish layout. (Can be amortized, but it's same as amortizing hash table resizing. Optimal layout cannot be decided without profiling, and that's expensive.)

dajohnson89 7y ago

doesn't this force you to define a comparator for everything though?

_greim_ 7y ago
As opposed to defining a hash code for everything, yes. Parent asserts that writing obviously-correct comparators is easier.
- 91aintprime 7y ago
  funny enough, a hash code defines an order on a set
  - tempguy9999 7y ago
    Is it in any sense a useful order though? You can assign any order to any set of objects, but you'd want it to be useful. A hash - the more hash-ey it is, the less the order means AFAICS.
    - n3k5 7y ago
      For the purpose of making a tree data structure, all linear orderings would be equally useful. Hashing only provides a partial order, so it's important to choose a hash function that won't assign the same hash to large batches of items. But it only needs to have this property for hashes of one particular size, whereas a hash map requires a function that behaves well for a variety of hash sizes. So there's an opportunity for using a cheaper hash function.
- LgWoodenBadger 7y ago
  IDEs have had good equals/hashcode auto-generation mechanisms for years. Java itself introduced Objects.hash(Object...) in 1.7 https://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash(java.lang.Object...) https://docs.oracle.com/javase/7/docs/api/java/util/Objects.... It's never really been an issue at all to implement equals/hashcode, which you're required to do for effectively all Collections-based usage anyway.