Hacker News Reader

Comment by SkiFire13 | Hacker News Reader

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

View on HN

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

You would have that frustration anyway during toolchain upgrades if the map implementation changed from one go version to the next.

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

If you want insertion order you need something like a LinkedHashMap.

Java's had that forever, but it's not really a common use case.

first time I know of LinkedHashMap is by reading a JSON library (Jason, iirc).

If you spend any amount of time programming Java, reviewing this list is a big help.

https://www.geeksforgeeks.org/collections-in-java-2/

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

I believe PHP is one of the (much) earlier languages with them.

Tcl was much earlier, in fact.

Since Go 1.23 you can do this: slices.Sorted(maps.Keys(m))

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

> lookups becoming O(n) on average.

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.

Reply on news.ycombinator.com