为什么在我使用迭代器时 class HashSet<T> 的值已经排序？

Question

我的 main 方法中有以下代码，当我遍历 Set 并打印值时，这些值已经排序。什么原因？

Set<Integer> set = new HashSet<Integer>();
set.add(2);
set.add(7);
set.add(3);
set.add(9);
set.add(6);

for(int i : set) {
    System.out.println(i);
}

输出：

Answer 1

这只是巧合。 A HashSet 不保留或保证任何顺序。

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

Answer 2

这只是个意外。我试过了：

final Set<Integer> set = new HashSet<Integer>();
set.add(2);
set.add(17);
set.add(32);
set.add(92);
set.add(63);

我得到了 17 32 2 92 63。它不在排序顺序中，因为 HashSet 不保留排序顺序或它们的添加顺序。

Answer 3

我不确定称之为巧合是不是正确答案。没有机会参与。这是使用散列函数的结果，您放入 HashSet 的小值以及放入 Set 的少量元素。

对于Integer，hashCode()是Integer的int值。
HashMap（和 HashSet）对 hashCode 返回的值进行额外的哈希处理，但这种额外的哈希处理不会更改您添加到 HashSet 中的小数字的值.
最后，每个整数放入的桶就是修改后的哈希码对HashSet的容量取模。 aHashSet/HashMap的初始容量为16.
因此 2 添加到桶 2，7 添加到桶 7，依此类推...
当您遍历 HashSet 的元素时，将按顺序访问存储桶，并且由于每个存储桶最多只有一个元素，因此您可以对数字进行排序。

桶的计算方式如下：

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

static int hash(int h) { // for the small integers you put in the set, all the values being
                         // xored with h are 0, so hash(h) returns h
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
     return h & (length-1); // table.length is the initial capacity - 16,
                            // so for h <= 15, indexFor(h,table.length)=h
}

因此2,7,3,9,6的桶分别为2,7,3,9,6

用于迭代 HashSet 的增强 for 循环按顺序访问存储桶，并针对每个存储桶迭代其条目（存储在链表中）。因此，对于您的输入，首先访问 2，然后访问 3、6、7 和 9。

如果添加大于 15 的数字，hash 方法和 indexFor 方法（假设您没有更改 HashSet 的默认容量）都会阻止对数字进行排序当被 HashSet 迭代器迭代时。

为什么在我使用迭代器时 class HashSet<T> 的值已经排序？

Why the class HashSet<T> has values already sorted when I use the iterator?

java

iterator

hashset