2017-10-20 113 views
5

这是java.util.stream.Collectors类的toSet()方法的实现:使用Java 8 Streams API时,可以在调用Collectors.toSet()时依赖于sort()吗?

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

我们可以看到,它采用了HashSet并调用add。从HashSetdocumentation,“它不保证为向集合的迭代顺序;特别是它不保证该顺序将随着时间保持不变。”

在下面的代码,的String一个List被流传输,分类收集到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()时不能依赖?

此外,究竟是什么“它不保证该顺序将随着时间保持不变”呢? (我想addremove,底层数组的大小调整?)

+2

“调用Collectors.toSet()时可以依赖于排序吗()?”没有[例如](https://ideone.com/NPVQT8)。 –

+5

如果需要在不同的JVM实例(和/或不同的JVM发布周期)内维护任何顺序,则必须使用'LinkedHashSet'或类似的类来确保**确定性的**顺序。原因已在答案中给出。 – Zabuza

回答

7

答案是否定的。将项目添加到Set后,您不能依赖任何订单。从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集合的主要部分的人)的一次演讲,他说他们已经将随机添加到集合的迭代顺序(由new在Java 9中设置工厂)。如果您想听到会话,那么他谈论的部分将启动here - 良好的谈话,强烈推荐的方式!

所以,即使你用来计算集合的迭代顺序,一旦你移动到Java 9,你应该停止这样做。

所有这一切说,如果你需要为了你应该考虑使用SortedSetLinkedHashSetTreeSet

+4

Stuart在* JavaOne 16 *中提到的随机化只适用于'JEP 269'集合,这些集合是新工厂'Map.of(...)'等返回的集合,而不是'HashSet'或' HashMap'保持不变。然而,你是正确的,没有人应该**依赖当前的行为。它在一些JDK发布周期之间已经发生了变化,并且从Java 8开始它在使用它时也很少发生变化(达到碰撞阈值时,它通过使用平衡树来重新组织它自己)。 – Zabuza

+0

@Zabuza你是对的,随机化只添加到新工厂(现在)。 – alfasin

+1

'SortedSet'不保留插入顺序,只有'LinkedHashSet'。 – the8472

7

要回答这个问题,你必须知道一点HashSet是如何实现的。顾名思义,HashSet使用散列表实现。基本上,哈希表是一个由元素散列索引的数组。散列函数(在Java中,对象的哈希被object.hashCode()计算)基本符合几个标准的函数:

  • 是(相对)快速计算给定元素
  • 两个对象.equals()彼此有相同的哈希值
  • 有一个低概率,不同的项目具有相同的哈希

所以,当你MEED一个HashSet是“排序”(如“迭代器保留了自然秩序,可以理解元素“),这是由于一对夫妇的巧合:

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

如果你看看StringhashCode()方法,你会看到一个字母串,哈希码对应于字母的Unicode指数(代码点) - 所以在这个特定的情况下,只要散列表足够小,元素将被排序。然而,这是一个巨大的巧合,

  • 将不会持有任何其他排序顺序
  • 不会保持类,它们的散列码不按照自己的自然顺序
  • 将不会举行与碰撞哈希表

此外,这与在流上调用sorted()这一事实无关 - 这仅仅是由于实现了hashCode()的方式,因此也是哈希表的排序。因此,问题的简单答案是“否”。

+0

你说得对,结果顺序似乎与排序的顺序相匹配是纯粹的巧合,但它也值得一提(明确地),这与插入顺序无关,也就是说它是否与插入顺序无关在流链中是否有排序()。顺便说一下,对于“单字母字符串”,哈希码匹配它们的* Unicode Codepoint *,它恰好是仅用于“单ASCII字符串”的ASCII索引。 – Holger

+0

你是对的,修改了答案:) –

相关问题