如果我将所有 [1, 2, 3, ..., n] 放入具有任何随机顺序的 HashSet 并迭代 HashSet，为什么我会得到有保证的排序顺序？

Question

PS: How is this HashSet producing sorted output? 这个 post 没有回答我的问题。我知道如果我将任何数字放入哈希集中，我将不会得到排序。

但是，我发现，如果我将所有 [1, 2, 3, ..., n] 放入一个 HashSet 中，并以任何打乱顺序 并迭代 HashSet，我将获得 保证排序。我不明白为什么它总是会发生。任何n < 10000 我已经测试了很多次，它总是正确的，因此这应该不是巧合，应该有一些原因！尽管我不应该依赖这个实现细节，但请告诉我为什么它总是发生。

PS：我知道如果我插入 [0,1,2, ..., n-1]，或者 [1+k, 2+k, .., n+k] (k != 0) 到 HashSet 中，迭代顺序是未排序的，我已经测试过了。 HashSet 的迭代顺序未排序是正常的。但是，为什么 [1,2,3,4,..,n] 的任何插入顺序总是意外地为真？我检查了实施细节。如果我跟踪路径，整个过程将包括调整桶数组的大小，以及从链表到红黑树的转换。如果我以打乱顺序插入整个 [1-n]，则 HashSet 的中间状态是未排序的。然而它如果我完成所有插入，将会意外地排序。

我使用 JDK 1.8 做了以下测试。

public class Test {

    public static void main(String[] args) throws IOException {
        List<Integer> res = printUnsortedCase(10000);
        System.out.println(res);
    }


    private static List<Integer> printUnsortedCase(int n){
        List<Integer> res = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (!checkSize(i)) {
                res.add(i);
            }
        }
        return res;
    }

    private static boolean checkSize(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
 
        // here I've shuffled the list of [1,2,3,4, ...n]        
        Collections.shuffle(list);

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(list.get(i)); // I insert the set in an unsorted order of [1,2,3,..,n]
        }

        list = new ArrayList<>(set);// iterate over the HashSet and insert into ArrayList
        return isSorted(list);
    }

    private static boolean isSorted(List<Integer> list) {
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1) > list.get(i)) return false;
        }
        return true;
    }
}

我已经写了上面的检查代码，它似乎是真的。

Answer 1

您将两个相关概念混为一谈：

保证顺序：规范说您将按特定顺序取回元素，所有符合该规范的实现都会这样做。
可重现的顺序：特定的实现returns所有元素按特定的顺序返回。

保证顺序必然意味着可重现的顺序（否则你会遇到错误）。

可重现的顺序并不意味着有保证的顺序。可重现的顺序可能只是某些实现细节的副作用，这些实现细节恰好对齐，因此在某些情况下您可以获得相同顺序的元素，但这并不能保证。

在这种特定情况下，有几个因素共同导致了可重现的顺序：

Integer 具有高度可重复性和可预测性 hashCode（它只是数字本身）
HashMap 对该哈希码进行了一些小的操作，以通过简单的哈希码实现来减少冲突的机会，这在这种情况下无关紧要（因为它只是 hash ^ (hash >>> 16) 保持number <= 2¹⁶ 均等).
您使用非常一致且可重现的方式来构建您的 HashMap。生成的哈希图将始终经历相同的成长阶段。

如果不是

        list.add(i);

你做到了

        list.add(i + 65000);

（即使用数字 65000 到 65000+n 而不是 0 到 n）然后你会看到未排序的结果出现。

事实上，您获得的“可重现顺序”非常脆弱，以至于仅添加 10 就已经导致一些列表未排序。

如果我将所有 [1, 2, 3, ..., n] 放入具有任何随机顺序的 HashSet 并迭代 HashSet，为什么我会得到有保证的排序顺序？

why I will get a guranteed sorted order, if I put all [1, 2, 3, ..., n] into a HashSet with any shuffled order and iterate the HashSet?

java

hashmap

hashset