Коллекции Java: TreeMap.size () и TreeSet.size (): O (1) или O (n)?

Question

Do TreeMap и TreeSet отслеживают, сколько предметов они содержат, или им приходится считать их каждый раз, когда вы звоните size()? Javadocs остаются немыми по этому вопросу.

Answer 1

Взгляните:

http://www.docjar.com/html/api/java/util/TreeMap.java.html

http://www.docjar.com/html/api/java/util/TreeSet.java.html

Для дальнейшего поиска в поиске Google было "древовидная карта исходного кода Java".(Я не говорю, что это должно быть язвительно - не совсем очевидно, что исходный код будет для googlin ').

tl; dr версия в том, что они отслеживают, так что это O (1).

Answer 2

Да, они отслеживают, сколько объектов они содержат, поэтому вызов size() в любом из них приводит к O (1) времени выполнения.