[xxs]

>Is (non-)determinism really the right concern here?

A massive one - there is a lot of code that implicitly depends on the order of iteration (think configurations/initialization). The issue might be invisible, and reproduce rarely in production only. The iteration order depends on the hash of the keys, plus the capacity of the underlying array.

In Java I advise to never use the standard HashMap in favor of LinkedHashMap. In cases where data density is important both are a terrible fit having nodes instead of a plain object array (and linear probe/search).