I might be missing something here, but even if we were saying the dictionary or set can only provide an iterator over its element in some order rather than being a collection of elements in some order itself wouldn't solve all problems, would it?
The underlying conflict of these unordered collections vending an iterator and their Equatable conformance would remain. And I really can't think of a realistic way to solve this problem: Iterating over unordered collections has to happen in some order. And the moment this order is nondeterministic or depends on things other than the value of such a collection, i.e. the order in which the elements were inserted, we have this fundamental conflict with Equatable: suddenly these instances are not substitutable any more!