使用Java 8 Streams API,在调用Collectors.toSet()时可以依赖sorted()吗？

Question

这是java.util.stream.Collectors类toSet()方法的实现:

public static <T>
Collector<T, ?, Set<T>> toSet() {
    return new CollectorImpl<>((Supplier<Set<T>>) HashSet::new, Set::add,
                               (left, right) -> { left.addAll(right); return left; },
                               CH_UNORDERED_ID);
}

我们可以看到,它使用a HashSet和调用add.从HashSet 文档中可以看出,"它不能保证集合的迭代顺序;特别是,它不能保证订单在一段时间内保持不变."

在以下代码中,a List将String流式传输,排序并收集到Set:

public static void main(String[] args) {
    Set<String> strings = Arrays.asList("c", "a", "b")
            .stream()
            .sorted()
            .collect(Collectors.toSet());
    System.out.println(strings.getClass());
    System.out.println(strings);
}

这提供了输出:

class java.util.HashSet

[a, b, c]

输出已排序.我认为这里发生的事情是,虽然HashSet文档提供的合同规定订单不是它提供的,但实现恰好按顺序添加.我想这可能会在未来版本中发生变化/在JVM之间有所不同,而且更明智的做法是做类似的事情Collectors.toCollection(TreeSet::new).

可以sorted()调用时不能依赖Collectors.toSet()？

此外,"它不能保证订单在一段时间内保持不变"究竟是什么意思？(我想add,remove基础数组的大小调整？)

Answer 1

答案是不.将项目添加到集合后,您不能依赖任何订单.来自JDK源代码(HashSet.java):

/**
 * Returns an iterator over the elements in this set.  The elements
 * are returned in no particular order.
 *
 * @return an Iterator over the elements in this set
 * @see ConcurrentModificationException
 */
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

现在,在JDK的早期版本中,即使订单无法保证,您通常也会以相同的插入顺序hashCode()hashCode()获取项目(除非对象的类实现,然后您将获得由此指定的顺序)).要么是对象的创建顺序,要么是对象的调用顺序hashCode().正如@Holgar在下面的评论中提到的,在HotSpot中它是后者.你甚至不能指望它,因为这也有例外,因为序列号不是hashCode生成器中的唯一成分.

我最近听到了Stuart Marks(负责重写Java 9中Collections主要部分的人)的演讲,他说他们已经将随机化添加到集合的迭代顺序(由新的集合工厂创建)在Java 9中.如果你想听到会话,他谈到的部分就会从这里开始- 好的谈话,强烈推荐的方式!

因此,即使您曾经依赖于集合的迭代顺序,一旦转移到Java 9,您应该停止这样做.

所有这一切,如果你需要订单,你应该考虑使用SortedSet, LinkedHashSet或TreeSet

Answer 2

要回答这个问题,您必须了解一下如何HashSet实施.顾名思义,a HashSet是使用哈希表实现的.基本上,哈希表是由元素哈希索引的数组.散列函数(在Java中,对象的散列计算方式object.hashCode())基本上是满足一些条件的函数:

• 它(相对)快速计算给定元素
• 两个对象.equals()彼此具有相同的哈希值
• 不同项目具有相同散列的概率很小

所以,当你HashSet注意到一个被"排序"(它被理解为"迭代器保留元素的自然顺序")时,这是由于几个巧合:

• 元素的自然顺序尊重他们的自然顺序hashCode小号
• 哈希表足够小,不会发生冲突(两个元素具有相同的哈希码)

如果查看String类hashCode()方法,您将看到对于单字母字符串,哈希代码对应于字母的Unicode索引(代码点) - 因此在这种特定情况下,只要哈希表足够小,元素将被排序.然而,这是一个巨大的巧合

• 不会保留任何其他排序顺序
• 不适用于hashCodes不遵循其自然顺序的类
• 不会持有碰撞的哈希表

而且,这与在sorted()流上调用的事实无关- 它仅仅是由于实现的方式hashCode(),因此是哈希表的排序.因此,问题的简单答案是"不".