近期,我惊讶地发现一些Java集合的方法size()并非具有恒定时间操作。
尽管我了解到并发集合实现在获得并发性方面做了一些妥协(如在ConcurrentLinkedQueue、ConcurrentSkipListSet、LinkedTransferQueue等中使size为O(n)),但好消息是这在API文档中得到了充分说明。
令我担忧的是,某些集合方法返回的视图上调用size方法的性能。例如,TreeSet.tailSet 返回一个由其元素大于或等于fromElement的部分组成的视图。令我感到惊讶的是,在返回的SortedSet上调用size方法是线性的,即O(n)。至少这是我从OpenJDK的源代码中挖掘到的信息:TreeSet是在TreeMap上实现的包装器,而在TreeMap内部,存在一个EntrySetView类,其size方法如下:
abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
private transient int size = -1, sizeModCount;
public int size() {
if (fromStart && toEnd)
return m.size();
if (size == -1 || sizeModCount != m.modCount) {
sizeModCount = m.modCount;
size = 0;
Iterator i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
}
....
}
这意味着第一次调用大小是O(n),然后只要支持映射未被修改,它就会被缓存。我无法在API文档中找到这个事实。更高效的实现将是在子树大小缓存方面进行内存交换的O(log n)。由于为了避免代码重复而进行此类权衡(TreeSet作为TreeMap的包装器),我不认为它们不应该出于性能原因而进行。
忽略我对TreeSet OpenJDK实现的(非常简短)分析是否正确,我想知道是否有关于许多此类操作的性能的详细完整文档,特别是那些完全意外的操作?
tailSet()
的行为完全符合直觉。我认为期望每个人都为了边缘用例的更好性能而支付内存代价会更令人惊讶。 - NPE