> While I understand the reason for this (i.e.: to avoid developers relying in a specific iteration order), I still find it weird, and I think this is something unique for Go.
Rust's `HashMap` and `HashSet` also do the same with the default hasher (you can plug your own deterministic hasher though). The reason for this choice, which I think also applies to Go, is to be resistant against HashDOS attacks, which can lead to hashmap lookups becoming O(n) on average. This is especially important for maps that will contain data coming from untrusted sources, like data submitted in a GET/POST request.
I do agree though that an ordered map would nicely solve the issue.
> Rust's `HashMap` and `HashSet` also do the same with the default hasher
Technically no.
Rust does use per-hashmap seeds for its keyed hashes (where many languages use per-process seeds).
Go does that, will also randomise iteration for each iteration (it randomises the start offset of the iteration). This latter operation has nothing to do with hashdos mitigation, and exists exclusively to frustrate accidental reliance on iteration order.
> I do agree though that an ordered map would nicely solve the issue.
To be precise, Rust does provide an ordered map in the standard library, it's std::collections::BTreeMap. However, iteration order is key comparison order, not insertion order.
I personally prefer something like Rust's `indexmap` instead, which is basically a hash table mapping from key to an index into a `Vec` containing the values. AFAIK this is also the approach taken by C#'s Dictionary.
I believe one rewrite of Python's dict was the first mainstream use of this sort of hash map as a default implementation.
I wish they provided a sort method to re-sort and re-index the vector to change the iteration order without the space overhead of creating a and sorting a separate vector/list of keys (or key-value pairs, depending on use case. You might want to change iteration order based on the currently held value).
> I believe one rewrite of Python's dict was the first mainstream use of this sort of hash map as a default implementation.
Technically pypy and I believe php implemented this model first, though it's probably most well known from cpython (for which it had been proposed first, by raymond hettinger).
Ordering generally denotes the preservation of insertion ordering, and possibly the alteration of that order. Sorted iteration is a completely different beast (and generally you’d use a tree-based collection if you need that).
If you're using a central dictionary then it should be worst case O(log n), but the price you pay for that is attacker controlled allocated memory growth.
there are various ways to structure dictionaries. one was to essentially create an array with each entry pointing into a list of values. you hash the key, then add the key/value to the list in that slot. the hash attacks would ensure everything hashed to the same slot, forcing the dict to become effectively become an alist.
it would do similar to implementations that keep jumping X slots mod size looking for an open slot, using the hash as the start slot. since everything hashed to the same value, everything you stuck in the dict would have to walk over every slot that had been stuck in the dict, again effectively making the dict into an overly complex association list for all practical reasons.
Rust's `HashMap` and `HashSet` also do the same with the default hasher (you can plug your own deterministic hasher though). The reason for this choice, which I think also applies to Go, is to be resistant against HashDOS attacks, which can lead to hashmap lookups becoming O(n) on average. This is especially important for maps that will contain data coming from untrusted sources, like data submitted in a GET/POST request.
I do agree though that an ordered map would nicely solve the issue.