4 ms·

Having hashmaps be ordered is not always desirable. It's not necessarily meaningful for every application[1]. Also, it can have overhead. If the problem is tha

Having hashmaps be ordered is not always desirable. It's not necessarily meaningful for every application[1]. Also, it can have overhead. If the problem is that the developer doesn't get what they expect, often the solution is to require the developer to be explicit about what they ask for. I think that could work well here. Instead of having map.keys(), the API could have map.orderedKeys() and map.unorderedKeys(). (Or make it okeys() and ukeys() to be more concise.) Yes, it's slightly more typing, but to me that's a small price to pay to ensure you get what you want. --- [1] For example, maybe the order that's meaningful to me has something to do with the values rather than the keys. If the map represents git commits, maybe the order that's meaningful to me is a topological sort, and the map isn't going to provide that.

stickfigure 5y ago
This would be genuinely weird. The in-memory representation will make one or the other approach more efficient. If you want ordered, pick an ordered implementation (eg Java's LinkedHashMap). If you don't care, pick an implementation that doesn't care (eg HashMap). If you want some special ordering, pick something that can use a Comparator (eg TreeMap) or just sort the data when fetching. A Frankenstein LinkedRandomTreeMap would pay the overhead of all approaches for an extremely exotic use case.
- adrianmonk 5y ago
  I suppose these ideas can be combined. An implementation that doesn't support ordering could be of a type that only has an unorderedKeys() and lacks orderedKeys(). Which is more explicit than having a keys() function that behaves differently than other types' keys() functions. Also, I guess you could define unorderedKeys() to mean "I'm not picky about the order" (rather than "it must not be ordered"). Then all types could have an unorderedKeys() function.
  - stickfigure 5y ago
    If unrderedKeys() isn't picky about the order, then there's no reason to have a separate method. Just keys() will do, and different implementations can have different behavior. Also note that relaxing the ordering requirement when obtaining keys does not necessarily improve performance; if you've already done the work of maintaining an ordered list (ie LinkedHashMap), it's actually faster to iterate in order. Furthermore, what exactly does orderedKeys() mean anyway? Insertion order? Does reinsertion change order? If some sort of natural ordering (eg, topological) then how do you configure that? I think the "state of the art" is basically correct here: An abstract Map interface that provides basic operations, and a variety of implementations all with different behaviors and performance profiles. Sorry.

stickfigure 5y ago

This would be genuinely weird. The in-memory representation will make one or the other approach more efficient. If you want ordered, pick an ordered implementation (eg Java's LinkedHashMap). If you don't care, pick an implementation that doesn't care (eg HashMap). If you want some special ordering, pick something that can use a Comparator (eg TreeMap) or just sort the data when fetching. A Frankenstein LinkedRandomTreeMap would pay the overhead of all approaches for an extremely exotic use case.

adrianmonk 5y ago
I suppose these ideas can be combined. An implementation that doesn't support ordering could be of a type that only has an unorderedKeys() and lacks orderedKeys(). Which is more explicit than having a keys() function that behaves differently than other types' keys() functions. Also, I guess you could define unorderedKeys() to mean "I'm not picky about the order" (rather than "it must not be ordered"). Then all types could have an unorderedKeys() function.
- stickfigure 5y ago
  If unrderedKeys() isn't picky about the order, then there's no reason to have a separate method. Just keys() will do, and different implementations can have different behavior. Also note that relaxing the ordering requirement when obtaining keys does not necessarily improve performance; if you've already done the work of maintaining an ordered list (ie LinkedHashMap), it's actually faster to iterate in order. Furthermore, what exactly does orderedKeys() mean anyway? Insertion order? Does reinsertion change order? If some sort of natural ordering (eg, topological) then how do you configure that? I think the "state of the art" is basically correct here: An abstract Map interface that provides basic operations, and a variety of implementations all with different behaviors and performance profiles. Sorry.