Big-O summary for Java Collections Framework implementations?

Question

I may be teaching a "Java crash-course" soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the order of the various operations on various collection implementations is.

I could take time to generate a summary matrix myself, but if it's already out there in the public domain somewhere, I'd sure like to reuse it (with proper credit, of course.)

Anyone have any pointers?

Solution 1

This website is pretty good but not specific to Java: http://bigocheatsheet.com/

Solution 2

The book Java Generics and Collections has this information (pages: 188, 211, 222, 240).

List implementations:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Set implementations:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Map implementations:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Queue implementations:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

The bottom of the javadoc for the java.util package contains some good links:

• Collections Overview has a nice summary table.
• Annotated Outline lists all of the implementations on one page.

Solution 3

The Javadocs from Sun for each collection class will generally tell you exactly what you want. HashMap, for example:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

TreeMap:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

TreeSet:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

(emphasis mine)

Solution 4

The guy above gave comparison for HashMap / HashSet vs. TreeMap / TreeSet.

I will talk about ArrayList vs. LinkedList:

ArrayList:

• O(1) get()
• amortized O(1) add()
• if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(n) to shift all the following elements

LinkedList:

• O(n) get()
• O(1) add()
• if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1)

View more solutions

Comments

[Nick]

Here is a link I found to be useful when discussion some very common Java objects and how much their operations cost using Big-O notation. objectissues.blogspot.com/2006/11/…

[Fabian Steeg]

Though not in the public domain, the excellent Java Generics and Collections by Maurice Naftalin and Philip Wadler lists runtime information overviews in its chapters on the different collection classes.

[ThreaT]

Would this performance benchmark be of any use?

[Overflown]

I disagree with the HashMap part. I know Sun's position, but... get for example must call obj.equals(key), which could be linear in the size of the objects contained. Consider that you typically have to read the fields for this comparison. The exceptions would be integers or strings (interned)???

[matt b]

First of all, if they were wrong, it ought to be not too hard for you to create a test case that disproves the constant-time performance? Second, if you look at the source code for HashMap, it does not call equals() against each key in the map - only when the hashcodes are equal.

[newacct]

If you read the quote above, it says it's constant-time "assuming the hash function disperses the elements properly among the buckets". From CS theory, hash tables have constant time operations when the hash function is "good" (which happens on average), but may take linear time in the worst case.

[mikera]

@Overflown - technically, it doesn't matter how long obj.equals() takes from a complexity perspective, as that is just part of the "constant" with relation to the number of items in the collection.

[WelcomeTo]

if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1) why? first we need to find element in the middle, so why it not O(n)?

[newacct]

@MyTitle: read it again. "using ListIterator.add() or Iterator.remove()" We have an iterator.

[Paul Evans]

@AndreaZilio LinkedList.remove(Object) is constant time, assuming you know the neighbor already. If you don't know the neighbor, it's linear time to find it first.

[Popeye]

You have to specify for which case scenario are those figures, for example, delete from Arraylist could take O(n), if you delete element in middle or end of array.

[Very Objective]

There is another nice Runtime Complexity of Java Collections summary in GitHub.

[Yassin Hajaj]

@popeye isn't O usually the worst case?

[Yashwin Munsadwala]

As mentioned by @Popeye, there should be a clear description about what case the answer is about. The case can be either average/ worst for time complexity. It looks like the answer is referring to an "average" case for all the DS.

[Jay Laughlin]

Why is this not a part of the JAVA API?