Hacker News Reader

Comment by chris_st | Hacker News Reader

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 experience, I'm doing either (A) using them as associative memory (I want the value for a key) and I don't ever iterate, or (B) I don't care about order when I iterate (I'm summing values, say) or (C) I want the keys in some sorted order, that probably has nothing whatsoever to do with insertion order (counting keywords, then showing them in alphabetical order).

So I'm curious why the insertion order is preferred, in your experience.

View on HN

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 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.

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.

I don't think compact dictionaries are necessarily vulnerable to this issue. You could randomize the hash seed without affecting the iteration order.

It definitely depends on the implementation and I do imagine you're right you could make it secure pretty easily without affecting it. But switching from non-compact, non-guaranteed would have resulted in API changes internal to perl that would have been far more difficult to do. This is because of some design decisions in the past that result in perl having to be rather conservative about internal interpreter changes.

Perl uses a system called XS to write C code that interacts with the perl interpreter. XS doesn't have a defined API other than "what the perl internals do", this is because it's not really a C api but in fact a way to extend the interpreter itself (you can replace parts of the parser and do some other shenanigans) and it exposes basically all of the fields, structures, and functions that are used inside the interpreter to all C extensions to the language. There are some nice modern alternatives to doing things this way, but the end result is that unless we want to break just about every library on CPAN that uses any native code some care has to be applied to not change too much of the API at any given time. That's also why there's Devel::PPPort that tries to wrap both new and old APIs/structures in a way to provide some amount of compatibility between perl versions where there is otherwise no compatibility.

> 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 Simple stuff like making golden output files for your tests becomes easier.

Relying on this type of behavior when it isn't required is somewhat of an anti-pattern. And can often lead to mindlessly copying the results of an implementation in tests.

A quick aside: any sort of generic ordered container that supports O(n) iteration must necessarily require O(n log n) work to construct in the average case. So the asymptotic complexity is necessarily the same as sorting the keys of a hash map with undefined iteration order to artificially create a defined order.

It isn't too hard to simulate the behavior of insertion order iteration by maintaining an array alongside the hash map. And surprisingly enough, space and runtime complexity is practically identical to containers that implement insertion order iteration ;-)

> any sort of generic ordered container that supports O(n) iteration must necessarily require O(n log n) work to construct in the average case

This doesn't apply if the order you want is insertion order.

These hash maps are constructed in O(n) on average, just like any other hash maps.

Java's LinkedHashMap is also constructed in O(n).

"ordered container" meaning that the container is ordered based on the objects it contains.

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/1... shows how in Python this useful property also comes as a side effect of an optimization

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

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.

> 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)]

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”

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

CPython has insertion ordered maps as of 3.6 after a memory usage optimization, & didn't before. 3.7 made it spec

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.)

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.

> 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.

Throwing Rust under the bus...?

I don't think that anyone really could do that. I am chuckling as I am writing this.

> 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.

The nice thing is the compact dictionary doesn't use extra memory, so why not make it the default?

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.

With that reasoning a sorted list would need more memory than an unsorted list.

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.

You were stating that "[...] it definitely is using memory it wouldn't need if it didn't preserve order.".

There is no reason for that. A sorted list doesn't need more memory than an unsorted list. And an insertion-sorted map doesn't need to use more memory than a map that doesn't keep the order.

Independently, some properties we deem valuable are often side-products of the way the data-structure works. For example, an efficient binary search tree will naturally tend to be balanced. In the case of efficient hash maps, it is now common to add the key/value pair at the end of an internal vector. Maintaining the insertion order this way doesn't add any cost.

It actually does have a cost. In fact I'm pretty sure it has two separate types of cost, so let's talk about both of them.

Firstly, and this is orthogonal to my original point, whenever people say "Cost" they actually silently mean "... that I care about" and so we're involuntarily obliged to agree to stop caring about anything else. Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections.

But my main point is that the requirement for ordering forces you to dispose of otherwise permissible optimisations which could destroy the order. You actually ran head first into this in the article, when repeatedly removing and adding elements blows up by clogging your data structure with tombstones.

Swiss Tables wouldn't clog up with tombstones. Since they don't care about ordering they only need tombstones at all in uncommon special cases (specifically, if the entire rest of the group is full or tombstones), in most cases Swiss Tables get to just set removed (key, value) pairs as empty. But this optimisation isn't open to you.

Sticking tombstones in the backing array doesn't actually cost you anything though. The backing array still needs to be the same size. Like maybe you end up having to re-hash more often?

>Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections.

Yes but this cost goes away if you commit to it, and the alternative (like what go does) to force the order to change all the time also comes with a complexity cost vs. doing "nothing" and having the order be arbitrary and sometimes, but not actually, reliable.

It does, though. See the diagram in the article. There's two allocated arrays there: one for the real hash table (on top) and one for the "backing array" which then stores the actual items. The "extra" bit is the indexes in the top allocation: those indexes would be omitted in a normal (unsorted) hash map. (That is, a normal hash map allocates a single array, which is the storage for both the hash table and the items it contains.¹)

(There's also some extra time requirements, too, to chase that additional pointer from the top table to the bottom one.)

¹N.b. in some languages those items will be references, but that doesn't matter for the comparison here.

Note that the bottom array can be densely packed, whereas the top one must have gaps to avoid excessive probing. If you only had one array you would have to put the gaps in that array, and it is at least 2 words per entry (much worse if you are inlining objects). So it's not so clear. If you want to save space you can also omit the hash bits stored in the index and reduce the width of the index entries to 16 or 8 bits on small maps.

In practice the compact dict does very well on space. Much better than Java's unordered bucket-based HashMap for example.

It's true that there's an extra pointer chase.

Ah, that's an excellent point, and it does muddle the water about which would win out.

Deletes could still leave holes in the storage array, but I think I agree (and your article also states it) that the common case is likely fill table with data, and then perform lookups.

(And I had thought bucket-based hashmaps had very much fallen out of favor to the point where they really weren't the choice of standard libraries anymore, precisely because of the additional allocations & pointer chasing they required? I'm not a Java person.)

C++ unordered_map unfortunately forces a bucket-based implementation. I don't know about Java.

The existence of the Map.Entry objects in Java implies a bucket based approach, but I don't think that's how it works these days, except perhaps for LinkedHashMap.

This stack overflow answer implies the Map.Entry objects are reused during iteration which means they don't need to exist the rest of the time and a flat KVKVKV backing array could be used. https://stackoverflow.com/questions/5455824/doesnt-that-iter...

Alternatively, new Entry objects are created for each step of the iteration, then heavy inlining could enable the JIT to eliminate that allocation again.

I don’t think this holds for persistent data structures that use HAMT. Those have great performance along with the benefits of immutability, and I’m perfectly okay with deferring order to a pretty-printer.

It wouldn’t handle insertion order, probably best to do alphabetical by default then. Chrome dec tools does this for js objects (which are map-like) already, and I’ve never had complaints about it.

note: it has been the default on python for some time, then made official (instead of an implementation detail) after some 3.x release. 3.7 maybe?

Turns out it's the default implementation in Ruby as of 2.7 or so as well.

As of 1.9 :) https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-...

Or you could look at it as "relaxed ordering is a performance optimization" and shouldn't be taken prematurely.

In Java, there is no default; you ask for a HashMap or a LinkedHashMap explicitly. In dynamic languages like Python or JS I prefer default insertion ordered maps because if I wanted tightly optimized code, I wouldn't use those languages in the first place.

In Kotlin, calling mapOf() gives you a LinkedHashmap. Which is a weird choice IMHO.

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.

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.

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.

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...?

It's also important if there are duplicate keys

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.

>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.

> 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.

> * 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.

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.

It's useful for when you are in a job interview and are asked to build an LRU cache. :-)

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.

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.

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.

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.

https://news.ycombinator.com/item?id=27704081

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.

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.

Cache with FIFO eviction and O(1) lookup

Reply on news.ycombinator.com