Sunday, 6 November 2011

Java Collections – Performance (Time Complexity)


Many developers I came across in my career as a software developer are only familiar with the most basic data structures, typically, Array, Map and Linked List. These are fundamental data structures and one could argue that they are generic enough to fit most of the commercial software requirements. But what worries me most is that even seasoned developers are not familiar with the vast repertoire of available data structures and their time complexity. In this post the ADTs (Abstract Data Types) present in the Java Collections (JDK 1.6) are enlisted and the performance of the various data structures, in terms of time, is assessed.

Before we start it is helpful to understand the so-called “Big O” notation. This notation approximately describes how the time to do a given task grows with the size of the input. Roughly speaking, on one end we have O(1) which is “constant time” and on the opposite end we have O(xn) which is “exponential time”. The following chart summarizes the growth in complexity due to growth of input (n). In our data structure walk-through we sometimes use the symbol h to signify the Hash Table capacity.


List

A list is an ordered collection of elements.


Add
Remove
Get
Contains
Data  Structure
ArrayList
 O(1)
O(n)
O(1)
O(n)
Array
LinkedList
 O(1)
O(1)
O(n)
O(n)
Linked List
CopyonWriteArrayList
 O(n)
O(n)
O(1)
O(n)
Array

Set

A collection that contains no duplicate elements.


Add
Contains
Next
Data Structure
HashSet
O(1)
O(1)
O(h/n)
Hash Table
LinkedHashSet
O(1)
O(1)
O(1)
Hash Table + Linked List
EnumSet
O(1)
O(1)
O(1)
Bit Vector
TreeSet
O(log n)
O(log n)
O(log n)
Red-black tree
CopyonWriteArraySet
O(n)
O(n)
O(1)
Array
ConcurrentSkipList
O(log n)
O(log n)
O(1)
Skip List

Queue

A collection designed for holding elements prior to processing.


Offer
Peak
Poll
Size
Data Structure
PriorityQueue
O(log n )
O(1)
O(log n)
O(1)
Priority Heap
LinkedList
 O(1)
O(1)
O(1)
O(1)
Array
ArrayDequeue
 O(1)
O(1)
O(1)
O(1)
Linked List
ConcurrentLinkedQueue
 O(1)
O(1)
O(1)
O(n)
Linked List
ArrayBlockingQueue
 O(1)
O(1)
O(1)
O(1)
Array
PriorirityBlockingQueue
O(log n)
O(1)
O(log n)
O(1)
Priority Heap
SynchronousQueue
O(1)
O(1)
O(1)
O(1)
None!
DelayQueue
O(log n)
O(1)
O(log n)
O(1)
Priority Heap
LinkedBlockingQueue
O(1)
O(1)
O(1)
O(1)
Linked List

Map

An object that maps keys to values. A map cannot duplicate keys; each key can map to at most one value.


Get
ContainsKey
Next
Data Structure
HashMap
O(1)
O(1)
O(h / n)
Hash Table
LinkedHashMap
O(1)
O(1)
O(1)
Hash Table + Linked List
IdentityHashMap
O(1)
O(1)
O(h / n)
Array
WeakHashMap
O(1)
O(1)
O(h / n)
Hash Table
EnumMap
O(1)
O(1)
O(1)
Array
TreeMap
O(log n)
O(log n)
O(log n)
Red-black tree
ConcurrentHashMap
O(1)
O(1)
O(h / n)
Hash Tables
ConcurrentSkipListMap
O(log n)
O(log n)
O(1)
Skip List

67 comments:

  1. Please, correct the description for LinkedList remove operation. It is two-step operation and the complexity is O(n), not O(1).

    ReplyDelete
    Replies
    1. I second that. The element should be found in the list before it can be removed by changing the pointers so it is O(n).

      Delete
    2. It is common to just write how long removal itself will take without actual search. You have to take it as: if you have pointer to object o in linked list then removal will take O(1).
      It is done this way, so you can see difference between different collections:
      ArrayList has remove O(n) + search, while LinkedList have O(1)+ search. Removal would have O(n) complexity for both even though LinkedList removal is way faster.

      Delete
    3. I agree with Robin but the problem is that it is kind of misleading. If a less "seasoned" programmer sees the chart then he will immediately assume that removing an element in LinkedList will just be O(1). An extra column needs to be put or a simple explanation should be given in the opening paragraphs.
      Otherwise, great post!

      Delete
    4. I third that. Seasoned programmers wouldn't even say that the remove method runs in constant time because no seasoned programmer only cares about the singular action the method makes. They care about everything that lead up to the action and that proceeded it. If you only cared about the main action of a method, everything would operate in constant time.

      Delete
    5. Also, add() is only constant time if it's added to the beginning or end of a list. This post is super inaccurate.

      Delete
  2. every queue implementation has O(N) on contains() method?

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. Array and LinkedList has O(n) on contains() method for sure. If element is not in array or list you have to traverse all elements just to be sure. In Priority Heap as name suggest use some kind of heap (couldn't find exactly which, so I will assume it is binary heap), which is data structure similar to binary tree, with special rules. Contains() on binary heap takes O(log n).

      Delete
  3. Linked List not use Array Data Structure

    ReplyDelete
  4. How come LinkedList use Arrays ????

    Big question. Please correct...

    ReplyDelete
  5. Thanks for providing this informative information. it is very useful you may also refer- http://www.s4techno.com/blog/2016/07/12/exception-handling/

    ReplyDelete
  6. perfect explanation about java programming .its very useful.thanks for your valuable information.java training in chennai | java training in velachery

    ReplyDelete
  7. For niit projects, assignments, cycle tests, lab@homes, c#, html, java, java script, sql, oracle and much more visit http://gniithelp.blogspot.in or https://mkniit.blogspot.in

    ReplyDelete
  8. Being new to the blogging world I feel like there is still so much to learn. Your tips helped to clarify a few things for me as well as giving..
    Android App Development Company
    Android App Development Company

    ReplyDelete
  9. Really useful. Thanks for sharing.

    ReplyDelete
  10. Really useful. Thanks for sharing.

    ReplyDelete
  11. I just want to say that all the information you have given here is awesome...great and nice blog thanks sharing..Thank you very much for this one. And i hope this will be useful for many people.. and i am waiting for your next post keep on updating these kinds of knowledgeable things...
    Web Design Development Company
    Web design Company in Chennai
    Web development Company in Chennai

    ReplyDelete
  12. Free easy & simple way to learn java online and much more.. go to =>> http://foundjava.blogspot.in

    ReplyDelete
  13. it is really amazing...thanks for sharing....provide more useful information...
    Mobile app development company

    ReplyDelete
  14. Thank you for nice article but I just want some more explanation because I am prepring this for my interview, like reason for each data structure complexity.good explained for arraylist and linkedlist but I need this type of explanation for each is it possible here??

    ReplyDelete
  15. This article is very much helpful and i hope this will be an useful information for the needed one.Keep on updating these kinds of informative things...
    iOS App Development Company

    ReplyDelete
  16. Many of this runtimes are not correct. One should distinguish between per-operation, amortized and (stochastic) expected worst-case runtimes. The runtimes here are mixed up and always choose the beset of the three.

    E.g. ArrayList#add has a worst case complexity of O(n) (array size doubling), but the amortized complexity over a series of operations is in O(1). HashSet#contains has a worst case complexity of O(n) (<= Java 7) and O(log n) otherwise, but the expected complexity is in O(1).

    ReplyDelete
    Replies
    1. In most of the cases here, amortized time complexity is mentioned.

      Delete
  17. Thanks a lot! You made a new blog entry to answer my question; I really appreciate your time and effort.
    java training in chennai |
    java training institute in chennai

    ReplyDelete
  18. Thanks for sharing with us the information on Java collections and I have learned a lot of new programming information from the article that has helped me to improve my basic programming skills. I Will be recommending this site to clients who access our Papers Reviewing Services so that they can read the article.

    ReplyDelete
  19. A easy and exciting blog about java learning. Please comment your opinions and share..
    http://foundjava.blogspot.in

    ReplyDelete
  20. Good Article
    One Correction, HashSet internal uses data structure HashMap not Hash Table.
    For More Technical Blog visit http://www.prabhatkashyap.com/

    ReplyDelete
  21. Good post and I like it very much. By the way, anybody try this increase app downloads? I do not how to use.

    ReplyDelete
  22. Java is very good blog,it's highly professional course.Thanks for sharing
    java online Training

    ReplyDelete
  23. It is amazing and wonderful to visit your site. Thanks for sharing this information; this is useful to everyone..
    Read more about Java training in delhi, java programming in delhi

    ReplyDelete
  24. What does “Next” mean for Set and Map? There is no such operation. If you mean the next() method of their Iterators, then the complexities are dead wrong. Iterators keep a reference to the current node, so it’s always O(1) for the hash maps instead of O(h / n).

    ReplyDelete
  25. This comment has been removed by the author.

    ReplyDelete
  26. [url=http://kataku.pw]berita terkeren seindonesia[/url]

    ReplyDelete
  27. This is not clear at all.
    You have to specify that all of Big-O you are mentioning is the best case.
    For example: get in HashMap in Java
    + best case: O(1)
    + worst case: O(n) or O(logn) - depends on Java SDK version.

    ReplyDelete
  28. Greetings. I know this is somewhat off-topic, but I was wondering if you knew where I could get a captcha plugin for my comment form? I’m using the same blog platform like yours, and I’m having difficulty finding one? Thanks a lot.
    Click here:
    angularjs training in online

    ReplyDelete
  29. This comment has been removed by the author.

    ReplyDelete
  30. Your new valuable key points imply much a person like me and extremely more to my office workers. With thanks from every one of us.

    Best AWS Training in Chennai | Amazon Web Services Training in Chennai

    AWS Training in Bangalore | Amazon Web Services Training in Bangalore

    ReplyDelete
  31. I would assume that we use more than the eyes to gauge a person's feelings. Mouth. Body language. Even voice. You could at least have given us a face in this test.
    java training in annanagar | java training in chennai

    java training in marathahalli | java training in btm layout

    java training in rajaji nagar | java training in jayanagar

    java training in chennai

    ReplyDelete
  32. I ‘d mention that most of us visitors are endowed to exist in a fabulous place with very many wonderful individuals with very helpful things.
    nebosh course in chennai

    ReplyDelete
  33. Nice tutorial. Thanks for sharing the valuable information. it’s really helpful. Who want to learn this blog most helpful. Keep sharing on updated tutorials…

    angularjs Training in bangalore

    angularjs Training in btm

    angularjs Training in electronic-city

    angularjs Training in online

    angularjs Training in marathahalli

    ReplyDelete
  34. Greetings. I know this is somewhat off-topic, but I was wondering if you knew where I could get a captcha plugin for my comment form? I’m using the same blog platform like yours, and I’m having difficulty finding one? Thanks a lot.

    AWS Training in Bangalore | Amazon Web Services Training in Bangalore

    Amazon Web Services Training in Pune | Best AWS Training in Pune

    AWS Online Training | Online AWS Certification Course - Gangboard

    ReplyDelete
  35. I would assume that we use more than the eyes to gauge a person's feelings. Mouth. Body language. Even voice. You could at least have given us a face in this test.
    python training in velachery
    python training institute in chennai

    ReplyDelete
  36. Really very nice blog information for this one and more technical skills are improve,i like that kind of post.
    Devops training in sholinganallur
    Devops training in velachery
    Devops training in annanagar
    Devops training in tambaram

    ReplyDelete
  37. I have read your blog its very attractive and impressive. I like your blog core Java online course

    ReplyDelete
  38. That was a great message in my carrier, and It's wonderful commands like mind relaxes with understand words of knowledge by information's.
    python interview questions and answers | python tutorials

    ReplyDelete
  39. Really you have done great job,There are may person searching about that now they will find enough resources by your post
    Devops Training courses
    Devops Training in Bangalore
    Best Devops Training in pune
    Devops interview questions and answers

    ReplyDelete
  40. Nice tips. Very innovative... Your post shows all your effort and great experience towards your work Your Information is Great if mastered very well.

    Java interview questions and answers | Core Java interview questions and answers

    ReplyDelete
  41. Wow it is really wonderful and awesome thus it is very much useful for me to understand many concepts and helped me a lot. it is really explainable very well and i got more information from your blog.

    rpa interview questions and answers
    automation anywhere interview questions and answers
    blueprism interview questions and answers
    uipath interview questions and answers
    rpa training in chennai

    ReplyDelete
  42. Wow it is really wonderful and awesome thus it is very much useful for me to understand many concepts and helped me a lot. it is really explainable very well and i got more information from your blog.

    rpa training in velachery| rpa training in tambaram |rpa training in sholinganallur | rpa training in annanagar| rpa training in kalyannagar

    ReplyDelete