<p>Anyone have a good rule of thumb for choosing between different implementations of Java Collection interfaces like List, Map, or Set?</p>

<p>For example, generally why or in what cases would I prefer to use a Vector or an ArrayList, a Hashtable or a HashMap?</p>

[{'answer_id': 48451, 'author': 'Zizzencs', 'author_id': 686, 'author_profile': 'https://Stackoverflow.com/users/686', 'pm_score': 3, 'selected': False, 'text': '<p>About your first question...</p>\n\n<p>List, Map and Set serve different purposes. I suggest reading about the Java Collections Framework at <a href="http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html" rel="noreferrer">http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html</a>.</p>\n\n<p>To be a bit more concrete:</p>\n\n<ul>\n<li>use List if you need an array-like data structure and you need to iterate over the elements</li>\n<li>use Map if you need something like a dictionary</li>\n<li>use a Set if you only need to decide if something belongs to the set or not.</li>\n</ul>\n\n<p>About your second question...</p>\n\n<p>The main difference between Vector and ArrayList is that the former is synchronized, the latter is not synchronized. You can read more about synchronization in <a href="https://rads.stackoverflow.com/amzn/click/com/0321349601" rel="noreferrer" rel="nofollow noreferrer">Java Concurrency in Practice</a>.</p>\n\n<p>The difference between Hashtable (note that the T is not a capital letter) and HashMap is similiar, the former is synchronized, the latter is not synchronized.</p>\n\n<p>I would say that there are no rule of thumb for preferring one implementation or another, it really depends on your needs.</p>\n'}, {'answer_id': 48452, 'author': 'Stu Thompson', 'author_id': 2961, 'author_profile': 'https://Stackoverflow.com/users/2961', 'pm_score': 5, 'selected': True, 'text': "<p>I've always made those decisions on a case by case basis, depending on the use case, such as:</p>\n\n<ul>\n<li>Do I need the ordering to remain?</li>\n<li>Will I have null key/values?  Dups?</li>\n<li>Will it be accessed by multiple threads</li>\n<li>Do I need a key/value pair</li>\n<li>Will I need random access?</li>\n</ul>\n\n<p>And then I break out my handy 5th edition <strong>Java in a Nutshell</strong> and compare the ~20 or so options.  It has nice little tables in Chapter five to help one figure out what is appropriate.  </p>\n\n<p>Ok, maybe if I know off the cuff that a simple ArrayList or HashSet will do the trick I won't look it all up.  ;)  but if there is anything remotely complex about my indended use, you bet I'm in the book.  BTW, I though Vector is supposed to be 'old hat'--I've not used on in years.</p>\n"}, {'answer_id': 48457, 'author': 'Joe Liversedge', 'author_id': 4552, 'author_profile': 'https://Stackoverflow.com/users/4552', 'pm_score': 2, 'selected': False, 'text': '<p>Lists allow duplicate items, while Sets allow only one instance.</p>\n\n<p>I\'ll use a Map whenever I\'ll need to perform a lookup.</p>\n\n<p>For the specific implementations, there are order-preserving variations of Maps and Sets but largely it comes down to speed. I\'ll tend to use ArrayList for reasonably small Lists and HashSet for reasonably small sets, but there are many implementations (including any that you write yourself). HashMap is pretty common for Maps. Anything more than \'reasonably small\' and you have to start worrying about memory so that\'ll be way more specific algorithmically.</p>\n\n<p><a href="http://www.roseindia.net/javatutorials/linkedlistvsarraylist.shtml" rel="nofollow noreferrer">This page</a> has <strong>lots</strong> of animated images along with sample code testing LinkedList vs. ArrayList if you\'re interested in hard numbers.</p>\n\n<p><strong>EDIT:</strong> I hope the following links demonstrate how these things are really just items in a toolbox, you just have to think about what your needs are: See Commons-Collections versions of <a href="http://commons.apache.org/collections/api-release/org/apache/commons/collections/map/package-summary.html" rel="nofollow noreferrer">Map</a>, <a href="http://commons.apache.org/collections/api-release/org/apache/commons/collections/list/package-summary.html" rel="nofollow noreferrer">List</a> and <a href="http://commons.apache.org/collections/api-release/org/apache/commons/collections/set/package-summary.html" rel="nofollow noreferrer">Set</a>.</p>\n'}, {'answer_id': 48462, 'author': 'Jonathan', 'author_id': 1772, 'author_profile': 'https://Stackoverflow.com/users/1772', 'pm_score': 5, 'selected': False, 'text': "<p>I'll assume you know the difference between a List, Set and Map from the above answers. Why you would choose between their implementing classes is another thing. For example:</p>\n\n<p><strong>List</strong>:</p>\n\n<ol>\n<li><strong>ArrayList</strong> is quick on retrieving, but slow on inserting. It's good for an implementation that reads a lot but doesn't insert/remove a lot. It keeps its data in one continuous block of memory, so every time it needs to expand, it copies the whole array.</li>\n<li><strong>LinkedList</strong> is slow on retrieving, but quick on inserting. It's good for an implementation that inserts/removes a lot but doesn't read a lot. It doesn't keep the entire array in one continuous block of memory.</li>\n</ol>\n\n<p><strong>Set:</strong></p>\n\n<ol>\n<li><strong>HashSet</strong> doesn't guarantee the order of iteration, and therefore is fastest of the sets. It has high overhead and is slower than ArrayList, so you shouldn't use it except for a large amount of data when its hashing speed becomes a factor.</li>\n<li><strong>TreeSet</strong> keeps the data ordered, therefore is slower than HashSet.</li>\n</ol>\n\n<p><strong>Map:</strong> The performance and behavior of HashMap and TreeMap are parallel to the Set implementations.</p>\n\n<p>Vector and Hashtable should not be used. They are synchronized implementations, before the release of the new Collection hierarchy, thus slow. If synchronization is needed, use Collections.synchronizedCollection().</p>\n"}, {'answer_id': 48471, 'author': 'user5044', 'author_id': 5044, 'author_profile': 'https://Stackoverflow.com/users/5044', 'pm_score': 1, 'selected': False, 'text': "<p>I found Bruce Eckel's Thinking in Java to be very helpful.  He compares the different collections very well.  I used to keep a diagram he published showing the inheritance heirachy on my cube wall as a quick reference.  One thing I suggest you do is keep in mind thread safety.  Performance usually means not thread safe.  </p>\n"}, {'answer_id': 48520, 'author': 'Tom Hawtin - tackline', 'author_id': 4725, 'author_profile': 'https://Stackoverflow.com/users/4725', 'pm_score': 3, 'selected': False, 'text': "<p>For non-sorted the best choice, more than nine times out of ten, will be: ArrayList, HashMap, HashSet.</p>\n\n<p>Vector and Hashtable are synchronised and therefore might be a bit slower. It's rare that you would want synchronised implementations, and when you do their interfaces are not sufficiently rich for thier synchronisation to be useful. In the case of Map, ConcurrentMap adds extra operations to make the interface useful. ConcurrentHashMap is a good implementation of ConcurrentMap.</p>\n\n<p>LinkedList is almost never a good idea. Even if you are doing a lot of insertions and removal, if you are using an index to indicate position then that requires iterating through the list to find the correct node. ArrayList is almost always faster.</p>\n\n<p>For Map and Set, the hash variants will be faster than tree/sorted. Hash algortihms tend to have O(1) performance, whereas trees will be O(log n).</p>\n"}, {'answer_id': 48525, 'author': 'Jason Cohen', 'author_id': 4926, 'author_profile': 'https://Stackoverflow.com/users/4926', 'pm_score': 4, 'selected': False, 'text': '<p>Theoretically there are useful <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">Big-Oh</a> tradeoffs, but in practice these almost never matter.</p>\n\n<p>In real-world benchmarks, <code>ArrayList</code> out-performs <code>LinkedList</code> even with big lists and with operations like "lots of insertions near the front."  Academics ignore the fact that real algorithms have constant factors that can overwhelm the asymptotic curve.  For example, linked-lists require an additional object allocation for every node, meaning slower to create a node and vastly worse memory-access characteristics.</p>\n\n<p>My rule is:</p>\n\n<ol>\n<li>Always start with ArrayList and HashSet and HashMap  (i.e. not LinkedList or TreeMap).</li>\n<li>Type declarations should always be an interface (i.e. List, Set, Map) so if a profiler or code review proves otherwise you can change the implementation without breaking anything.</li>\n</ol>\n'}, {'answer_id': 17420706, 'author': 'ChrLipp', 'author_id': 734687, 'author_profile': 'https://Stackoverflow.com/users/734687', 'pm_score': 7, 'selected': False, 'text': '<p>I really like this cheat sheet from Sergiy Kovalchuk\'s blog entry, but unfortunately it is offline. However, the Wayback Machine has a <a href="https://web.archive.org/web/20200802192003/http://www.sergiy.ca/guide-to-selecting-appropriate-map-collection-in-java/" rel="noreferrer">historical copy</a>:</p>\n<p><img src="https://i.stack.imgur.com/EmzXy.gif" alt="Java Map/Collection Cheat Sheet" /></p>\n<p>More detailed was Alexander Zagniotov\'s flowchart, also offline therefor also a historical <a href="https://web.archive.org/web/20130424223516/http://initbinder.com/articles/cheat-sheet-for-selecting-maplistset-in-java.html" rel="noreferrer">copy of the blog</a>:</p>\n<p><a href="https://i.stack.imgur.com/GfpyN.png" rel="noreferrer"><img src="https://i.stack.imgur.com/GfpyN.png" alt="Alexander Zaniotov\'s flowchart for choosing Collection implementations" /></a></p>\n<p>Excerpt from the blog on concerns raised in comments:\n&quot;This cheat sheet doesn\'t include rarely used classes like WeakHashMap, LinkedList, etc. because they are designed for very specific or exotic tasks and shouldn\'t be chosen in 99% cases.&quot;</p>\n'}, {'answer_id': 44682154, 'author': 'Vikas', 'author_id': 3864917, 'author_profile': 'https://Stackoverflow.com/users/3864917', 'pm_score': 2, 'selected': False, 'text': '<p>As suggested in other answers, there are different scenarios to use correct collection depending on use case. I am listing few points,</p>\n<p><strong>ArrayList:</strong></p>\n<ul>\n<li>Most cases where you just need to store or iterate through a &quot;bunch of things&quot; and later iterate through them. Iterating is faster as its index based.</li>\n<li>Whenever you create an ArrayList, a fixed amount of memory is allocated to it and once exceeded, it copies the whole array</li>\n</ul>\n<p><strong>LinkedList:</strong></p>\n<ul>\n<li>It uses doubly linked list so insertion and deletion operation will be fast as it will only add or remove a node.</li>\n<li>Retrieving is slow as it will have to iterate through the nodes.</li>\n</ul>\n<p><strong>HashSet:</strong></p>\n<ul>\n<li><p>Making other yes-no decisions about an item, e.g. &quot;is the item a word of English&quot;, &quot;is the item in the database?&quot; , &quot;is the item in this category?&quot; etc.</p>\n</li>\n<li><p>Remembering &quot;which items you\'ve already processed&quot;, e.g. when doing a web crawl;</p>\n</li>\n</ul>\n<p><strong>HashMap:</strong></p>\n<ul>\n<li>Used in cases where you need to say &quot;for a given X, what is the Y&quot;? It is often useful for implementing in-memory caches or indexes i.e key value pairs  For example:\nFor a given user ID, what is their cached name/User object?.</li>\n<li>Always go with HashMap to perform a lookup.</li>\n</ul>\n<p>Vector and Hashtable are synchronized and therefore bit slower and  If synchronization is needed, use Collections.synchronizedCollection().\nCheck <a href="https://stackoverflow.com/questions/18760752/difference-between-collections-sort-and-getting-a-sorted-collection-by-adding">This</a> for sorted collections.\nHope this hepled.</p>\n'}, {'answer_id': 56374160, 'author': 'Johnny', 'author_id': 2811258, 'author_profile': 'https://Stackoverflow.com/users/2811258', 'pm_score': 2, 'selected': False, 'text': '<p>Well, it depends on what you need. The general guidelines are:</p>\n\n<p><strong>List</strong> is a collection where data is kept in order of insertion and each element got index.</p>\n\n<p><strong>Set</strong> is a bag of elements without duplication (if you reinsert the same element, it won\'t be added). Data doesn\'t have the notion of order.</p>\n\n<p><strong>Map</strong> You access and write your data elements by their key, which could be any possible object.</p>\n\n<p><a href="https://i.stack.imgur.com/0g5VZ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/0g5VZ.png" alt="enter image description here"></a>\nAttribution: <a href="https://stackoverflow.com/a/21974362/2811258">https://stackoverflow.com/a/21974362/2811258</a></p>\n\n<p>For more information about Java Collections, <a href="https://javatutorial.net/java-collection-tutorial" rel="nofollow noreferrer">check out this article</a>.</p>\n'}, {'answer_id': 59806362, 'author': 'Basil Bourque', 'author_id': 642706, 'author_profile': 'https://Stackoverflow.com/users/642706', 'pm_score': 1, 'selected': False, 'text': '<h1>Use <code>Map</code> for key-value pairing</h1>\n\n<p>For <a href="https://en.wikipedia.org/wiki/Attribute%E2%80%93value_pair" rel="nofollow noreferrer">key-value</a> tracking, use <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Map.html" rel="nofollow noreferrer"><code>Map</code></a> implementation.</p>\n\n<p>For example, tracking which person is covering which day of the weekend. So we want to map a <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/time/DayOfWeek.html" rel="nofollow noreferrer"><code>DayOfWeek</code></a> object to an <code>Employee</code> object.</p>\n\n<pre><code>Map &lt; DayOfWeek , Employee &gt; weekendWorker = \n    Map.of( \n        DayOfWeek.SATURDAY , alice ,\n        DayOfWeek.SUNDAY , bob\n    )\n;\n</code></pre>\n\n<p>When choosing one of the <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Map.html" rel="nofollow noreferrer"><code>Map</code></a> implementations, there are several aspects to consider. These include: concurrency, tolerance for NULL values in key and/or value, order when iterating keys, tracking by reference versus content, and convenience of literals syntax.</p>\n\n<p>Here is a chart I made showing the various aspects of each of the ten <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Map.html" rel="nofollow noreferrer"><code>Map</code></a> implementations bundled with Java 11.</p>\n\n<p><a href="https://i.stack.imgur.com/ThFKw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ThFKw.png" alt="Table of map implementations in Java 11, comparing their features"></a></p>\n'}]
['https://Stackoverflow.com/questions/48442', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1294/']