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?

Would this [performance benchmark](https://github.com/ThreaT/Java-Collections-Benchmark) be of any use? — , Jun 19 '15 at 09:09
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. http://objectissues.blogspot.com/2006/11/big-o-notation-and-java-constant-time.html — Nick, Feb 18 '09 at 04:30
Though not in the public domain, the excellent [Java Generics and Collections](http://oreilly.com/catalog/9780596527754/) by Maurice Naftalin and Philip Wadler lists runtime information overviews in its chapters on the different collection classes. — Fabian Steeg, Feb 18 '09 at 04:30

score 300 · Accepted Answer · edited Jan 27 '18 at 20:28

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.

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. — Popeye, Jul 25 '17 at 19:59
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. — Yashwin Munsadwala, May 25 '20 at 23:38
Extra points for the iterator.remove column which is usually skipped in these kind of reports — RoberMP, Jun 10 '22 at 11:48

score 169 · Answer 2 · edited Nov 28 '17 at 19:47

169

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

edited Nov 28 '17 at 19:47

Iwo Kucharski

3,735
3
50
66

answered Oct 29 '10 at 07:41

Ben J

5,811
2
28
32

1

@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. – Paul Evans Dec 10 '15 at 15:33
1

There is another nice [Runtime Complexity of Java Collections](https://gist.github.com/psayre23/c30a821239f4818b0709) summary in GitHub. – Very Objective Aug 17 '18 at 09:23

score 14 · Answer 3 · answered Feb 18 '09 at 04:31

14

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)

answered Feb 18 '09 at 04:31

matt b

138,234
66
282
345

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)??? – Overflown Feb 18 '09 at 07:03
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. – matt b Feb 18 '09 at 14:11
5

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. – newacct May 02 '09 at 00:46
4

@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. – mikera Sep 12 '10 at 19:37

score 7 · Answer 4 · edited Feb 09 '18 at 12:51

7

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)

edited Feb 09 '18 at 12:51

Sai Kishore

326
1
7
16

answered May 02 '09 at 00:52

newacct

119,665
29
163
224

1

`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)? – WelcomeTo Jun 21 '13 at 17:48
@MyTitle: read it again. "using `ListIterator.add()` or `Iterator.remove()`" We have an iterator. – newacct Jun 21 '13 at 18:24

Big-O summary for Java Collections Framework implementations?

4 Answers4

Linked

Related