Unclear documentation around HashMap iteration order

[e00E]

The documentation for HashMap on the methods keys, values, iter, etc is phrased

An iterator visiting all <type> in arbitrary order.

The std::collections module documentation states

For unordered collections like HashMap, the items will be yielded in whatever order the internal representation made most convenient.

To me this makes it clear that I cannot expect any specific iteration order. What is not clear is whether the iteration order is persistent across multiple calls to the same HashMap without modification in between.
Are these two loops guaranteed to iterate in the same order?

for _ in hashmap.iter() {}
for _ in hashmap.iter() {}

Or these?

let iter = hashmap.iter();
for _ in iter.clone() {}
for _ in iter.clone() {}

Erring on the side of caution I would say that no the iteration order is not guaranteed to be the same.

The documentation should clarify this. I don't know whether the iteration order should be guaranteed in this case but either way it should be clarified.

[mjclements]

I can try to read though and see how they are implemented at the moment. But I couldn't find any issue or discussion about this being a guarantee, so maybe just that should be added to the docs?

[cuviper]

In practice, iter and even iter_mut should be stable between successive loops, but future guarantees are harder. Some languages even add extra randomization to map iteration order to deliberately prevent folks from relying on anything.

[jmaargh]

Is this still an issue or can it be closed?

Is there a motivating example as to why this is something we would want to guarantee?

[e00E]

It should be a conscious decision to guarantee or not guarantee this. Until this decision is documented in the collections docs this issue shouldn't be closed.

It is not extremely unusual to write code that depends on iterating through the same hashmap twice yielding items in the same order. I don't have an a snippet ready right now but I made this issue when I encountered this in real world code.

[jmaargh]

I guess my thinking is that it currently is not guaranteed by the documentation, so changing this would introduce a new guarantee that would have to be maintained. I'm also struggling to imagine a good motivating example myself, which means that the cost-benefit tradeoff in my head is purely "cost".

Could the current docs explicitly not guarantee it? Sure. But I don't find them currently ambiguous.

[m-ou-se]

I think it'd be fine to guarantee that the order is persistent between iterations (when the collection isn't modified in between of course). If someone can send a PR that clarifies the documentation, I can start an FCP on that to get consensus from the team.

[the8472]

Have there been any DoS attacks against a library using hashmaps based on their read-only iteration order? That's a reason I can think of for keeping the option to randomize iteration order available.
I vaguely recall reading some blog post about issues that weren't simple "collide everything into a single bucket" attacks but I can't find the details.

[hkBst]

I don't see why iteration order for a HashMap would change unless anything about the HashMap changed, but it still seems wrong to guarantee anything about the order of an unordered map like a HashMap. If you need an ordered map you can use a BTreeMap.

Now that I think about it a bit more, a HashMap might distribute the work of a resize or rehash over the next X calls to guarantee a O(1) complexity. Every call to the HashMap might then change it. And since I went this far already, I migth as well think about a call to HashIter::next to do some house keeping on top of its normal tasks. Crazy perhaps, but not unthinkable.