java - 通过将排序的集合添加到SortedSet来重排序的集合有多昂贵

这更多是出于好奇，因为我从未注意到性能问题。假定设置的大小在1-1000之间。这是一种情况：

private static SortedSet<GrantedAuthority> sortAuthorities(
    final Collection<? extends GrantedAuthority> authorities ) {
    return authorities.stream()
        .filter( Objects::nonNull )
        .sorted( Comparator.nullsFirst( Comparator.comparing( GrantedAuthority::getAuthority ) ) )
        .collect( Collectors.toCollection( TreeSet::new ) );
}

但是我遇到的更常见的情况是从已经排序的“ SQL查询”中获取有序列表，然后将其放入SortedSet中。显然，如果我从未发现问题，这是过早的优化，我只是好奇这会在微观层面上造成哪种开销（请注意：通常我为此使用TreeSet）。

最佳答案

当您将n个项目添加到TreeSet时，即使项目是有序的，您也不能假设时间复杂度会超过O（n * log2n）。更大的开销来自常量因子，因为集合需要分配n个树节点来容纳您的数据。

如果您的收藏是预先排序的，则最好不要将其存储在简单列表中，前提是您无需修改​​结果。在排序列表os O（log2n）上进行二进制搜索，而在读取时存储它实际上没有开销。读入TreeSet的唯一好处是O（log2n）插入和删除的可能性。