8 ms·

The surprising/interesting thing about this article is the notion that insertion order is the order that you want to iterate through a hash map. In my experien

• macspoofing 5y ago
  >So I'm curious why the insertion order is preferred, in your experience. It's a little bit like asking what's the use of a linked list. A map which can iterate through keys in insertion order is just a data structure. A recent use-case for me was using timestamps as keys that map to captured state at that time.
  • recursive 5y ago
    > A recent use-case for me was using timestamps as keys that map to captured state at that time. That sounds like sorted key order would suffice just fine.
  • chris_st 5y ago
    > * It's a little bit like asking what's the use of a linked list.* Well, no, it's more like asking why you'd use data structure X instead of Y. I was asking why you'd want that property as part of your data structure, and pointing out that (AFAIR) I've never needed it. For your use case, I guess you wanted to be able to retrieve the data for specific time stamps? Otherwise I'd think you'd just put it into an array.
• __s 5y ago
  A result of insertion order is that when I print {b:2,a:1} I get "{b:2,a:1}". This can be nice for being able to store something like an HTML element's attributes as a dictionary while still serializing it back to the order it was declared with Sorted order also requires sortable keys-- not something that's required when hash maps only require hashing & equality A stable ordering is nice, without the ability to sort insertion order meets this ask. https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... shows how in Python this useful property also comes as a side effect of an optimization
  • uyt 5y ago
    Compact dict which preserves insertion order are now the default implementation of dicts in python 3.7. They gave a talk about it in https://www.youtube.com/watch?v=npw4s1QTmPg https://www.youtube.com/watch?v=npw4s1QTmPg
  • dheera 5y ago
    There are also some use of dictionaries where the ordering matters (e.g. some mongoDB commands) and you can't use JSON or BSON and you have to use goddamn SON.
  • cabalamat 5y ago
    > A result of insertion order is that when I print {b:2,a:1} I get "{b:2,a:1}". This implies that {b:2,a:1} is a different data structure than {a:1,b:2}, which disagrees with my intuitions about how associative arrays ought to work. If I wanted a data structure that cares about order, I could use [(b,2),(a,1)] and [(a,1),(b,2)]
    • OskarS 5y ago
      This is for, like, debug purposes. Makes logs and things like JSON requests easier to read because the output matches the source. Logically though, they are still unordered for things like equivalence checks, so those two examples you had there still compare equal. Since order is unspecified, but when serializing the hash table you have to pick one, you might as well go for insertion order and make it easier for the programmer to read. Especially since this kind of hash table gets that “for free”
      • rurban 5y ago
        For debug purposes you throw away security and define a fixed seed, which implies the ordering. Equivalence checks on unordered containers are different, and any framework which cannot check equivalence of unordered containers are worthless. Forcing ordering on inherently unordered containers does have it's price, it's certainly not free. You can pay that price at serialization, or for testing, but it makes not much sense elsewhere. Unordered maps don't hate you, you are just not equipped to deal with it. Insertion ordered maps were a thing in the 80s with lisp property lists, which did hold your environment of symbols properly. But since then everyone switched over to proper hashmaps already. Just some not yet: Emacs, python, PHP, ... You cannot get rid of old sins easily
• ErikCorry 5y ago
  The most important thing is that there is some defined order. This makes it easier to debug, and reproducibility is just a very nice property. See https://en.wikipedia.org/wiki/Reproducible_builds https://en.wikipedia.org/wiki/Reproducible_builds Simple stuff like making golden output files for your tests becomes easier. Certainly, having an ordering on the keys themselves (eg. alphabetical order) is an alternative to insertion order. I'm fine with that. But eg. the built-in maps in Go, Perl or JS don't support that. So often you end up getting the keys, and then immediately sorting them before iterating. That's taking something that should be O(n) and making it O(n log n). I remember doing this all the time in Perl. And often there's no order, so you have to create one for your key type. That's extra work, and it's just easier to use a data structure that doesn't require it. I would be interested to see performance comparisons for maps where the keys are ordered without having to sort on each iteration. Often they have tree structures internally, which means cache-unfriendly pointer chasing, but probably you can remove most of this (and the log-n access time) with wider trees like B-trees.
  • simcop2387 5y ago
    For perl yoy can get this but you have to explicitly ask for it outside the perl interpreter. This is dome by setting up the hash seed and tell it not to add turbulence during runtime. export PERL_HASH_SEED=0; export PERL_PERTURB_KEYS=0; The article doesn't mention why python and perl made the choice to add more randomness but ti's because there were attacks out there where people could determine which bucket keys would be put in ahead of time and calculate a set of keys to cause pathological behavior in anything that made a hash from user input, this was commonly url parameters or POST requests. This meant that a simple web request with the right information in it could cause your application to continually reallocate memory and expand the hash size to accomadate the inputs. Usually this just burned cpu time and made other requests time out but it could also result in excessive memory usage and the OOM killer ccoming into play. The above environment variables work to set a known seed and then not mix any new randomness in, this doesn't get you an jnsertion order but it will make the hash itself as reproducible as possible (if you don't put the keys in in the same order your results will vary still). I uwe this in a now defunct (because of second/third/fourth system syndrome) fuzzer I had going to detect problems in the prerelease versions of perl.
• _old_dude_ 5y ago
  When you want to output values in the same order as the user give it to you e.g. when you read then write JSON or TOML files and those files can be written by a real human. Changing the order feel arbitrary. When you have a language that support keyword arguments (kwargs) like Ruby or Python more recently.
• foobarian 5y ago
  While we can sort the keys before iterating a plain hashmap, getting insertion order is particularly cumbersome because we need to keep some extra information about the original ordering of the elements. So I guess I'm kinda glad that this is the default implementation, and getting other sort orders is easy with just having access to the keys.
• paavohtl 5y ago
  I've relied on the order of keys for URL routing in JavaScript / TypeScript. Each route of the web application is unique, and the order matters - it's surprisingly easy to end up with otherwise ambiguous routes like /products/:ean and /products/all in real world applications. One benefit of using an object and not just an array is that I can validate at compile time with TypeScript that each route has exactly one handler. An insertion-ordered hashmap works really well for this without requiring any extra syntax or data beyond object literals.
• arsome 5y ago
  > The surprising/interesting thing about this article is the notion that insertion order is the order that you want to iterate through a hash map. I agree, this is what java calls a "LinkedHashMap" and what python calls an "OrderedDictionary" - there are times when it's quite useful, but often it's simply not necessary, uses extra memory and shouldn't be the default when you just need a hashmap.
  • ErikCorry 5y ago
    The nice thing is the compact dictionary doesn't use extra memory, so why not make it the default?
    • tialaramex 5y ago
      It may (perhaps, I can't tell) not use "extra memory" compared to the data structure they had before, but it definitely is using memory it wouldn't need if it didn't preserve order. Otherwise it would be more or less a violation of the pigeonhole principle. The insertion order is information, if you don't need to store that anywhere but you promise to give it back anyway that's a hole in your information theory.
      • floitsch 5y ago
        With that reasoning a sorted list would need more memory than an unsorted list.
        • tialaramex 5y ago
          How so? Sorting changes the order of the list, to the extent it's adding information (the sort order) it's also destroying the same amount of information (the previous order). It's easy enough (including by accident) to deliver insertion ordered iterator behaviour for small hash maps that have never had any items removed, but after that things get sticky very quickly.
          • 5y ago
• spuz 5y ago
  Imagine you want to write a JSON parser and prettyfier. Then writing the keys out in the same order as they were inserted would be very important. Yes, it's true that key order doesn't matter to the computers that consume JSON but humans consume JSON too and key order often matters to them.
  • chris_st 5y ago
    You may be able to tell from this reply that I've never built a JSON parser and prettyfier :-) but I'd guess that in this case, I'd never have any reason to ask for a bit of the JSON "out of order", so I'd just use arrays...?
  • nly 5y ago
    It's also important if there are duplicate keys
• sorokod 5y ago
  Other then having a deterministic order without the need to specify additional ordering constraints, it is usefull when you are populating the map while linearly processing some data.
• metalliqaz 5y ago
  When working with data that has been scanned/parsed from a file, it is often very useful to me that I retrieve the data in the order it was found in the file. This gives humans some kind of continuity between the input and the output of the program.
• mypalmike 5y ago
  It's useful for when you are in a job interview and are asked to build an LRU cache. :-)
  • marvy 5y ago
    I think LRU does NOT work with this trick, because there's no easy way to "move-to-front" in O(1) time. The article mentions Java's LinkedHashMap, which actually can do LRU. But as the name implies, they rely on a linked list, where move=to-front is natural. But this superpower does not come for free: a Java-style linked hash map will use more memory than the technique described in the article.
    • ErikCorry 5y ago
      I think you can move to front by removing the entry and then adding it again. This won't be O(1) currently, but with the tombstone trick from my blog post I think it would be.
      • deleted 5y ago
        [deleted]
      • marvy 5y ago
        Ooh nice! I didn't think of that! Since appending to an array is cheap, you can just move-to-end instead of move-to-front, and then iterate in "reverse" order, so from the outside everything seems to Just Work.
• deleted 5y ago
  [deleted]
• eloff 5y ago
  One case where this is useful is where you want determinism. You don't need a particular order, but you do need it to be consistent. This comes up a lot in compilers where you don't want the output code to vary on each run. This is specifically a big problem with Go, because maps use random iteration order so you don't depend on it. I feel that was a mistake. I would rather they took a page from Python and JavaScript and used insertion order. The reason they did not was to avoid painting themselves into a corner with respect to algorithms and options in the future - which is reasonable. Rust uses a randomly seeded hash algorithm on purpose to defend against hash DOS attacks. Hashing doesn't necessarily mean indeterminate, outside of Go and Rust, but it can be tricky to guarantee because it depends on the algorithm and the memory allocator (which is often multithreaded and can introduce non deterministic behavior.)
  • echelon 5y ago
    Maybe it wasn't your intent (I also could be reading this wrong), but I feel like throwing Rust under the bus here is unfair. Rust has a ton of different collections types you can use. You can also replace the hashing and seeding algorithms. It's the most flexible of the lot out of necessity. Systems programming requires fine control over data structures.
    • eloff 5y ago
      > Maybe it wasn't your intent (I also could be reading this wrong), but I feel like throwing Rust under the bus here is unfair. I don't see how that was throwing rust under the bus. I didn't even state my opinion, just the fact that it makes this performance for safety tradeoff (an unusual one since most hash tables do not attempt to protect against hash DOS attacks.) You can replace the hashing algorithm. The rust compiler does this. But most people don't fiddle with the default, which makes it a questionable decision in my books.
    • _nalply 5y ago
      Throwing Rust under the bus...? I don't think that anyone really could do that. I am chuckling as I am writing this.
• nly 5y ago
  Cache with FIFO eviction and O(1) lookup
• kadoban 5y ago
  One thing of note: if you want sorted order, there's no reason to be using a hash table. It would require either worse than O(n) amortized iteration, or worse than O(1) expected insertion (A log n has to go somewhere to satisfy the theoretical lower bound for sorting). If you want sorted, you're going to use a tree based structure. I'm also not sure how you'd even naturally get sorted order into a hash table. I'm sure it's possible, but on the face of it it just seems bizarre.
  • ErikCorry 5y ago
    https://news.ycombinator.com/item?id=27704081 https://news.ycombinator.com/item?id=27704081
• mamcx 5y ago
  People want a table, like in rdbms. Hashmap is what them get. The properties of it (only useful as a direct index) is too narrow for the kind of use that in Langs like python has, where a dictionary is used everywhere (like a vector). How some argue a hash map must be used (only useful to get a direct index) is like saying "vector can be used to only get a positional index") and wonder why people iterate it. In other words: Collection want to be iterated.