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

Question

PS：这个 HashSet 是如何产生排序输出的？ 这篇文章没有回答我的问题。我知道如果我将任何数字放入哈希集中，我将不会得到排序顺序。

但是，我发现如果我将所有 [1, 2, 3, ..., n] 放入具有任何混洗顺序的 HashSet 中并迭代 HashSet，我将得到一个guranteed sorted order。我不明白为什么它总是会发生。我已经多次测试过任何 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

您正在混淆两个相关概念：

1. 保证顺序：规范说你将以特定的顺序取回元素，并且所有符合该规范的实现都会这样做。
2. 可重现的顺序：特定的实现以特定的顺序返回所有元素。

保证顺序必然意味着可重复的顺序（否则你会有一个错误）。

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

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

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

如果不是

        list.add(i);

你做到了

        list.add(i + 65000);

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

实际上，您获得的“可重复顺序”非常脆弱，仅添加10就已经导致某些列表未排序。