为什么这个 HashSet 在打印时看起来是排序的？

Question

Set<Integer> s = new HashSet<Integer>();
s.add(77);
s.add(0);
s.add(1);
 
System.out.println(s);
 
TreeSet<Integer> s1 = new TreeSet<Integer>();
s1.add(77);
s1.add(0);
s1.add(1);
 
System.out.println(s1);

输出：

s = [0, 1, 77]
s1= [0, 1, 77]

根据教程点页面上的定义

A Set is a generic set of values with no duplicate elements. A TreeSet is a set where the elements are sorted.

为什么 s 和 s1 的输出都排序了？我只希望 s1 的输出被排序。

Answer 1

TreeSet 实现了 SortedSet，这就是为什么您添加到其中的所有元素都会在实际添加之前进行排序。

在您的情况下，您正在使用 Integer。它实现了 Comparable，它具有默认的比较机制。你 TreeSet 使用这个整数的 Comparable 实现来比较你的整数，然后再将它们添加到集合中。

因此，通常在使用 TreeSet 时，您有两种可能的解决方案：

您的 TreeSet 应该只适用于实现 Comparable 接口的对象，因为它们需要有 compareTo 实现。 TreeSet 将使用此实现来执行排序。
如果您的 class 没有实现 Comparable，您可以在创建 TreeSet.

Comparator

HashSet里面不做任何排序，这里只是随机排序。元素根据其哈希码进入不同的存储桶，在您的情况下，它们是匹配的。

UPD：HashSet这不是随机的，我的回答可能会令人困惑，如果有兴趣请看一下。

Answer 2

s1 排序是对的，因为它是 TreeSet，但 s 并没有真正排序。如果您向 s 添加更多元素，您会看到一些奇怪的事情发生。

After adding 32, 12, 13, and 14
[0, 32, 1, 12, 77, 13, 14]

所以现在您看到它有点有序，但实际上并非如此。原因是 HashSet 默认容量为 16，以后会根据需要增加。因此，当你向它添加一个元素时，想象它采用该元素的哈希码，对 16 取模，以便它适合 16 个桶的内部“列表”。由于 Integer 的哈希码是它代表的 int，我们可以假装它所做的只是 (the element to be added) % 16.

所以当你添加 0、1 和 77 时，它在内部可能看起来像这样：

Bucket   Elements
0        0
1        1
2
3
4
5
...
13       77 (77 % 16 is 13, so it's placed here)
14
15
16

然后我们加上 32。32 % 16 是 0，但是我们在第一个桶中已经有 0。幸运的是，为了防止像这样的冲突，HashSets 使用链表而不是单个元素，所以我们只需将 32 添加到包含 0 的链表中。

Bucket   Elements
0        0 -> 32
1        1  
2
3
4
5
...
13       77
14
15
16

12、13 和 14 的工作方式相同：

Bucket   Elements
0        0 -> 32
1        1
2
3
4
5
...
12       12
13       77 -> 13
14       14
15
16

如果您按顺序遍历存储桶，打印该存储桶中的每个链表，您会得到 [0, 32, 1, 12, 77, 13, 14]

看到了run

Answer 3

Why is the Set interface returning an ordered list?

Set Interface in Java, or a Set概念，一般来说，可以认为是一个抽象数据类型，作为一个契约的行为规范，声明一个不包含重复元素的集合。

因此，Set<E> 接口本身不 return 做任何事情；但是，它可以实现 in different ways.

TreeSet<E>定义says, that:

The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

HashSet<E> 定义，另一方面，says, that:

it does not guarantee that the order will remain constant over time.

Answer 4

这只是偶然发生的。

HashSets 是 HashMap 的特殊实现，但它们仍然使用哈希码将对象放入桶中。

Integer 的标准 hashCode 是 int 值本身。

指定如此低的值加上负载因子和桶算法会导致它们根据该代码放置在不同的桶中，但桶恰好是顺序的。如果您将值更改为更大的值，它们将不会被排序，因为该算法仅使用部分 hashCode 到 select 存储桶，因此它们被顺序排列的机会减少了。对于更大的随机分布数字集也是如此。

Set<Integer> s = new HashSet<Integer>();

s.add(57999999);
s.add(67999999);
s.add(77999999);

System.out.println(s);

TreeSet<Integer> s1 = new TreeSet<Integer>();

s1.add(57999999);
s1.add(67999999);
s1.add(77999999);


System.out.println(s1);

在我的机器上运行 Windows 和 Java 14，它们打印如下：

[67999999, 77999999, 57999999]
[57999999, 67999999, 77999999]

为什么这个 HashSet 在打印时看起来是排序的？

Why does this HashSet look sorted when printed?

java

collections

hashset