{"id":312,"date":"2014-02-01T23:42:11","date_gmt":"2014-02-01T23:42:11","guid":{"rendered":"http:\/\/www.smr.co.uk\/?p=312"},"modified":"2014-02-01T23:42:11","modified_gmt":"2014-02-01T23:42:11","slug":"java-data-structures","status":"publish","type":"post","link":"http:\/\/www.smr.co.uk\/?p=312","title":{"rendered":"Java Data Structures"},"content":{"rendered":"

\t\t\t\tHere are list Java 7 data structures and their thread model and expected performance. (See\u00a0<\/span>BigO Cheat Sheet<\/a> for more algorithm speeds):-<\/span><\/p>\n\n\n\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Name<\/strong><\/td>\nOveriew<\/strong><\/td>\nThreading Method<\/strong><\/td>\nSorted<\/strong><\/td>\nIndex<\/strong><\/td>\nSearch \/ Contiains or Get<\/strong><\/td>\nInsert<\/strong><\/td>\nDelete<\/strong><\/td>\nWho<\/strong><\/td>\n<\/tr>\n
Maps<\/strong><\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
HashMap<\/td>\nHashtable<\/td>\nNot thread safe<\/td>\nNo<\/td>\nn\/a<\/td>\nO(1)<\/td>\nO(1)<\/td>\nO(1)<\/td>\nJava<\/td>\n<\/tr>\n
ConcurrentHashMap<\/td>\nSegmented hashtable<\/td>\nNon blocking<\/td>\nNo<\/td>\nn\/a<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
Hashtable<\/td>\nOld School, don\u2019t use<\/td>\nIntrinsic blocks<\/td>\n<\/td>\nn\/a<\/td>\nO(1)<\/td>\nO(1)<\/td>\nO(1)<\/td>\nJava<\/td>\n<\/tr>\n
ConcurrentSkipListMap<\/td>\nTree like skipped list<\/td>\nLock free CAS<\/td>\nYes<\/td>\nn\/a<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nJava<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
Lists<\/strong><\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
ArrayList<\/td>\nResizable array<\/td>\nNot thread safe<\/td>\nNo<\/td>\nO(1)<\/td>\nO(N)<\/td>\nO(N)<\/td>\nO(N)<\/td>\nJava<\/td>\n<\/tr>\n
LinkedList<\/td>\nDouble linked list<\/td>\nNot thread safe<\/td>\nNo<\/td>\nO(N)<\/td>\nO(N)<\/td>\nO(1)<\/td>\nO(1)<\/td>\nJava<\/td>\n<\/tr>\n
Vector<\/td>\nOld School, don\u2019t use<\/td>\nIntrinsic blocks<\/td>\nNo<\/td>\nO(N)<\/td>\nO(N)<\/td>\nO(1)<\/td>\nO(1)<\/td>\nJava<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
Sets<\/strong><\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
HashSet<\/td>\nHashMap backed<\/td>\nNot thread safe<\/td>\nNo<\/td>\nn\/a<\/td>\nO(1)<\/td>\nO(1)<\/td>\nO(1)<\/td>\nJava<\/td>\n<\/tr>\n
TresSet<\/td>\nTree backed<\/td>\nNot thread safe<\/td>\nYes<\/td>\nn\/a<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nJava<\/td>\n<\/tr>\n
ConcurrentSkipListSet<\/td>\nAs ConcurrentSkipListMap<\/td>\nAs ConcurrentSkipListMap<\/td>\nyes<\/td>\nn\/a<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nJava<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
Queue\u00a0 \/ FIFO<\/strong><\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
ConcurrentLinkedQueue<\/td>\n<\/td>\nNon blocking<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
PriorityQueue<\/td>\nBalanced binary heap<\/td>\nNot thread safe<\/td>\nYes<\/td>\nn\/a<\/td>\nO(N)<\/td>\nO(log(N))<\/td>\nO(log(N))<\/td>\nJava<\/td>\n<\/tr>\n
ArrayBlockingQueue<\/td>\nBounded array<\/td>\nReentrant lock<\/td>\nNo<\/td>\nO(1)<\/td>\nO(N)<\/td>\nO(1)<\/td>\nO(N)<\/td>\nJava<\/td>\n<\/tr>\n
PriorityBlockingQueue<\/td>\nArray based binary heap<\/td>\nReentrant lock<\/td>\nYes<\/td>\nn\/a<\/td>\nO(N)<\/td>\nO(log(N)) ?<\/td>\nO(log(N)) ?<\/td>\nJava<\/td>\n<\/tr>\n
LinkedBlockingQueue<\/td>\nTypically greater throughput than array backed<\/td>\nReentrant lock<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
LinkedTransferQueue<\/td>\nProducer waits for consumer<\/td>\nShort spin then park\/unpark<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
SynchronousQueue<\/td>\nInsert waits for remove<\/td>\nShort spin then park\/unpark<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
DelayQueue<\/td>\nBacked by PriorityQueue<\/td>\nReentrant lock<\/td>\nYes<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
ForwardingBlockingQueue<\/td>\nBlocking queue to another Blocking queue<\/td>\nNot thread safe<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nGoogle<\/td>\n<\/tr>\n
EvictingQueue<\/td>\nEvicts from head<\/td>\nNot thread safe<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nGoogle<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
Dequeue \/ FIFO or LIFO<\/strong><\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
LinkedList<\/td>\nList, double linked list<\/td>\nNot thread safe<\/td>\nNo<\/td>\nO(N)<\/td>\nO(N)<\/td>\nO(1)<\/td>\nO(1)<\/td>\nJava<\/td>\n<\/tr>\n
LinkedBlockingDeque<\/td>\nLinked list<\/td>\nReentrant lock<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
ArrayDeque<\/td>\nArray backed<\/td>\nNot thread safe<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
ConcurrentLinkedDeque<\/td>\n<\/td>\nNon blocking<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nJava<\/td>\n<\/tr>\n
ForwardingDeque<\/td>\nAbstract<\/td>\nNot thread safe<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nGoogle<\/td>\n<\/tr>\n
ForwardingBlockingDeque<\/td>\nAbstract<\/td>\nNot thread safe<\/td>\nNo<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\nGoogle<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"excerpt":{"rendered":"

Here are list Java 7 data structures and their thread model and expected performance. (See\u00a0BigO Cheat Sheet for more algorithm speeds):- Name Overiew Threading Method Sorted Index Search \/ Contiains or Get Insert Delete Who Maps HashMap Hashtable Not thread … Continue reading →<\/span><\/a> Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[8,11],"tags":[],"class_list":["post-312","post","type-post","status-publish","format-standard","hentry","category-java","category-technology"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=\/wp\/v2\/posts\/312","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=312"}],"version-history":[{"count":0,"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=\/wp\/v2\/posts\/312\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=312"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=312"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.smr.co.uk\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=312"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}