Incorrect HashSet documentation?

[ryzhyk]

Documentation for HashSet contains the following sentence:

Values will have a predictable order based on the hasher being used. Unless otherwise specified, this will be the standard RandomState hasher.

I don't believe this is accurate. Even when replacing RandomState with a deterministic hasher, the order of values during enumeration is still only predictable assuming there are no collision nodes in the HAMT. In the presence of collisions, the order depends on the order in which values were added to the collision node. Here is a simple repro that generates two sets with identical contents, but different enumeration order.

use im::hashset::HashSet;
use std::collections::hash_map::DefaultHasher;
use std::hash::BuildHasherDefault;

fn main() {
    // Two hashsets with deterministic hashers.
    let mut set1 = HashSet::with_hasher(<BuildHasherDefault<DefaultHasher>>::default());
    let mut set2 = HashSet::with_hasher(<BuildHasherDefault<DefaultHasher>>::default());

    for i in 0..100_001 {
        // Insert elements in ascending order to set1 and in descending order to set2.
        // This ensures that collision nodes, if any, will contain values in different order.
        set1.insert(i);
        set2.insert(100_000 - i);
    }

    // This assertion succeeds: `set1` and `set2` contain the same elements.
    assert_eq!(set1, set2);

    let vec1: Vec<_> = set1.into_iter().collect();
    let vec2: Vec<_> = set2.into_iter().collect();

    // This assertion fails: the order of elements is not exactly the same.
    assert_eq!(vec1, vec2);
}

[ryzhyk]

Here is another passage from the documentation that is inaccurate for the same reason:

Please note that the order is consistent between sets using the same hasher, but no other ordering guarantee is offered. Items will not come out in insertion order or sort order. They will, however, come out in the same order every time for the same set.

[ryzhyk]

It gets worse: Ord and PartialOrd impls for HashSet also rely on consistent ordering and therefore don't work correctly:

use im::hashset::HashSet;
use std::collections::hash_map::DefaultHasher;
use std::hash::BuildHasherDefault;
use std::cmp::Ordering;

fn main() {

    let mut set1 = HashSet::with_hasher(<BuildHasherDefault<DefaultHasher>>::default());
    let mut set2 = HashSet::with_hasher(<BuildHasherDefault<DefaultHasher>>::default());

    for i in 0..15_001 {
        set1.insert(i);
        set2.insert(15_000 - i);
    }

    // The sets are the same according to Eq..
    assert_eq!(set1, set2);
    // ..but not according to Ord causing this assertion to fail.
    assert_eq!(set1.cmp(&set2), Ordering::Equal);
}