HashSet是否在内部执行排序工作？

Question

我Set有时会排序,有时候不排序.

这是一个例子:

public class SetOfInteger {
    public static void main(String[] args) {
        Random rand = new Random(47);
        Set<Integer> intset = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            int j = rand.nextInt(30);
            System.out.print(j + " ");
            intset.add(j);
        }
        System.out.println();
        System.out.println(intset);
    }
}

结果显示set未排序.

8 5 13 11 1 29 28 20 12 7 
[1, 20, 5, 7, 8, 11, 12, 29, 28, 13]

当我将终止表达式更改i < 20为for语句时,结果显示set变为已排序.

8 5 13 11 1 29 28 20 12 7 18 18 21 19 29 28 28 1 20 28 
[1, 5, 7, 8, 11, 12, 13, 19, 18, 21, 20, 29, 28]

真奇怪,是吗？我只是不知道如何解释它,我需要一些帮助,非常感谢你.

Answer 1

HashSet不保证排序迭代,但在非常特定的情况下,其内部数据结构可能像桶排序一样.

具体来说,对于[0,65535]范围内的整数键和大于最大键的表大小,存储密钥的桶的索引等于密钥本身,并且因为迭代器按桶顺序迭代,它按排序顺序发出元素.

Answer 2

周围有一些很好的答案,但没有人试图解释在这种特殊情况下究竟发生了什么,所以我将限制我的答案,而不是添加HashSet如何工作的另一个解释.我认为这种理解是理所当然的.

HashSet的默认构造函数创建一个容量为16且加载因子为0.75的集合.这意味着有16个分档,当您插入16*0.75 = 12个独特元素时,此容量会增加.

这就是为什么在第一种情况下,数字按其余数除以16进行排序:集合以表格大小16开始,将每个元素"散列"到一个bin中x % 16.然后当有12个元素时,它会增长表格并进行重新表达(如果不清楚的话,请参阅Javier Martin的答案),可能会将表格增加到32个.(我只能在java 6 doc中找到有关它如何增长的信息,声明桶的数量"近似"加倍,无论这意味着什么.)这使得每个30以下的整数都有自己的bin,所以当集合按顺序迭代每个bin时,它按顺序迭代数字.如果您在64以下插入数字,您可能会发现在迭代出现排序之前需要插入32*0.75 = 24个元素.

另请注意,这种分配箱的方式不是保证行为.其他Java版本/实现中的HashSets可能会对对象的hashCode()值执行更复杂的操作而不是简单地使用余数.(正如评论中的ruakh和蓬松所指出的那样 - 谢谢!)

Answer 3

您的问题指出项目顺序随着集合变大而变化.但是,您不能指望保留的订单.A Set有一个保证:每种元素只有一种.还有其他Set对象可以提供进一步的保证,但简单HashSet不能保证顺序.

您看到的重新排序只是内部重组,因为HashSet在内部存储的方式.在一种非常简化的思维方式中,HashSet有一定数量的"槽"来存储值,如果不是素数则通常是奇数.哈希码getHashCode()用于将对象分配给插槽.当您有哈希代码冲突时,HashSet使用相等运算符equals()来确定对象是否实际上是唯一的.

当您添加项目时,HashSet会发生以下几件事:

• 对象被分配到其内部插槽
  • 然后进一步散列哈希码以找到它所属的插槽
  • 如果存在插槽冲突,那么我们测试是否相等.如果它是同一个对象我们丢弃它,如果不是,我们将它添加到该槽中的列表
• 当对象数超过插槽数时,HashSet需要调整自身大小
  • 它创建了一组更大的插槽,通常仍然是奇数或素数
  • 现有项目将重新映射到新的插槽集合中 - 这是订单可以更改的位置

最重要的是,如果对象神奇地对自己进行排序,那么除非您使用的TreeSet是对设置项目强加排序顺序,否则这不是您可以依赖的实现.

Answer 4

您必须手动对其进行排序，因为不能保证哈希集将被排序。如果你愿意，你也可以使用 TreeSet 它将提供你想要的功能，但如果你想使用 HashSet 无论如何尝试这个：

Set intset = new HashSet();
List sortedIntList = new ArrayList(intset);
Collections.sort(sortedIntList);