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;
    }
}

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

回答

        list.add(i);

        list.add(i + 65000);