Are ArrayList and HashMap the most used collections?

[Monica Shiralkar]

I have frequently seen cases where a set of elements are to be stored. I have almost always seen an ArrayList being used to store it. Another frequent case I have seen is of storing unique keys and values. I have almost always seen HashMap being used to store this.  This is based on my experience in the codes that I have commonly seen in my career and also the code which I have written over the years. ArrayList and Set seem to me as the most commonly used collection. Although I know that Set is used for cases where one requires unique elements to be stored, I have never seen a code where set is used to store a set of elements. Are ArrayList and HashMap the most used collections and is Set used very less? For what kind of use case would someone use a set? (where unique elements are required to be stored). Thanks

[Campbell Ritchie]

Yes: ArrayList most probably is far and away the most frequently used Collections Framework class.
HashMap is probably the most frequently used type of Map, which stores values linked to unique keys. Remember the “V”s need not be unique.
Use Lists stacks and queues, remembering there are several different types of queue, depending on whether you want to retrieve elements in a particular order. I shall let you tell us what the iteration orders of a list, a (non‑priority) queue and a stack are. Also tell us which types of Collection can have their iteration order changed at runtime by sorting or “randomising” their elements.
Use sets when you want unique elements without linking them to keys. Remember there are HashSet, LinkedHashSet and TreeSet. Please tell us what their iteration orders are.
Please go through the Java™ Tutorials section.

Challenge: If you search my posts, you will find I have a complaint about Stacks. Do you think my complaint is justified?

[Stephan van Hulst]

What does it matter? Just use the appropriate collection for the appropriate use case. Who cares what other people do?

You use a list if you want to keep elements ordered (but not necessarily sorted).

You use a set if you want to prevent duplicate elements and you are not concerned about ordering (or you want to keep elements in encounter order or keep them sorted).

You use a map if you can treat the keys as a set and also want to associate each key with a value.

It's often the case that multiple collections match your requirements. For instance, if you don't care about ordering, but you also don't care about uniqueness, then both lists and sets will work. In this case you pick the collection with the best performance characteristics based on what you want to do with it.

[Monica Shiralkar]

The common scenario that I have seen and come across myself is where we need to store certain elements which we can access later, and neither do we care for ordering (something that List provides), nor do we need uniqueness (something that Set provides). The collection that I have seen to be choosen for such cases is ArrayList.

[Stephan van Hulst]

Monica Shiralkar wrote:we need to store certain elements which we can access later

This is kinda the point of EVERY collection, and doesn't really say much about your use case. Access them how? For what?

[Monica Shiralkar]

Stephan van Hulst wrote:doesn't really say much about your use case. Access them how? For what?

Inside some functionality, I compute some results. All I want is that later these elements should be accessible to me and that's all I care (I dont care about ordering nor do I care about uniqueness). For such cases I use ArrayList.

[Monica Shiralkar]

Campbell Ritchie wrote: I shall let you tell us what the iteration orders of a list, a (non‑priority) queue and a stack are.

I think :

List : insertion order.
Queue: FIFO order
Statck: FILO order

[Monica Shiralkar]

Campbell Ritchie wrote:
Use sets when you want unique elements without linking them to keys.

In my career whatever code I saw and whatever code I wrote, I never came across a case which required unique elements. Always the case I have encountered has been that while doing some functionality I need to store some elements somewhere so that later on I can retrieve them for something. Never did I come across case which required uniqueness or ordering. I always used ArrayList for this although I didnt require the speciality provided by Lists i,e ordering.

[Campbell Ritchie]

Monica Shiralkar wrote:. . .
List : insertion order.
Queue: FIFO order

Is there a difference? Remember priority queues behave differently

Statck: FILO order

Correct

[Monica Shiralkar]

Campbell Ritchie wrote:

Monica Shiralkar wrote:. . .
List : insertion order.
Queue: FIFO order

Is there a difference? Remember priority queues behave differently

Statck: FILO order

Correct

In both, elements will be kept in the order they are inserted. I think the difference is that in case of insertion order elements can be randomly retrieved but in FIFO order only the element which was inserted first can be accessed first.

[Campbell Ritchie]

Correct Remember it is also possible to insert elements into a List at any index. You usually insert elements into queues at their head, or in the case of a dequeue, at both ends.

[Monica Shiralkar]

List provides ordering, insertion at any position, retrieval from any position .Despite this, ironically I never used Lists for any of these. Each of the times I used an ArrayList , it was because from within some functionality I wanted to store some values so that I can retrieve and use them somewhere else.

[Paul Clapham]

Yes, I've done that a lot in the past, just throwing things into an ArrayList so that I can get them out later and do something with them.

But the other day I had a case where I didn't want duplicates in there, and there were duplicates coming in from the source data. So I switched to Set -- I needed a particular implementation, of course, and HashSet seemed okay.

But then I found that "do something with them" involved preserving the order in which I threw the things into the Set. In that case LinkedHashSet turned out to be the right implementation.

[Monica Shiralkar]

Paul Clapham wrote:Yes, I've done that a lot in the past, just throwing things into an ArrayList so that I can get them out later and do something with them.

So I switched to Set -- I needed a particular implementation, of course, and HashSet seemed okay.

.

For what kind of use case?

[Paul Clapham]

I was reading a list of names from a text file, and later I needed to print out some of the names (those with a particular feature). But the main purpose of the code was to do something else with those names, and only afterwards did I need to print out that subset of names. And the subset rules weren't known until the end of the processing. Therefore I needed to store all of the names and print the subset -- in the same order -- later.

[Monica Shiralkar]

Intrestingly, if I am asked:

What is an ArrayList? It is an implementation of List interface, used for storing elements with ordering and gives fast random access.
What have you used it for?   For storing elements from within some functionality so that I can do something with them later.

The above answers look disconnected and inspite using ArrayList numerous times, I am yet to come across a use case which demands random access and ordering.

[Monica Shiralkar]

Paul Clapham wrote:I was reading a list of names from a text file, and later I needed to print out some of the names (those with a particular feature). But the main purpose of the code was to do something else with those names, and only afterwards did I need to print out that subset of names. And the subset rules weren't known until the end of the processing. Therefore I needed to store all of the names and print the subset -- in the same order -- later.

Thanks.

[Monica Shiralkar]

Paul Clapham wrote:Yes, I've done that a lot in the past, just throwing things into an ArrayList so that I can get them out later and do something with them.

Although such kind of use cases require neither the speciality of Lists , i,e Ordering and random access nor the speciality of Set, i,e uniqueness,  arrayList is choosen instead of Set because it will be faster?

[Campbell Ritchie]

No. A list is chosen because it will simply store the elements. A set would do some processing of elements to make them unique. A queue or stack would restrict access, but a list allows access to any element in any order, though you might get slow execution in some circumstances. I shall leave it to you to work out how you might get slow execution.
If you go through one of your threads and write down the names of people posting, you will end up with a list on your paper. You don't need any processing, re‑ordering or anything. You simply record them. That is what lists are good at.

[Paul Clapham]

Campbell Ritchie wrote:If you go through one of your threads and write down the names of people posting, you will end up with a list on your paper. You don't need any processing, re‑ordering or anything. You simply record them. That is what lists are good at.

And the list will have Monica and you repeated several times. If you want the names only once, you would use a Set.

[Monica Shiralkar]

Campbell Ritchie wrote:That is what lists are good at.

I read that arrayList is good at random access.But this is not random access use case.This one is like we are storing all names and then when we use it we will iterate and do something.

[Paul Clapham]

Monica Shiralkar wrote:I read that arrayList is good at random access.But this is not random access use case.This one is like we are storing all names and then when we use it we will iterate and do something.

Well, you know, you can use a class without having to use all of its features in your code. It's perfectly reasonable to use a List without ever accessing it randomly and nobody will criticize you for that.

[Monica Shiralkar]

Paul Clapham wrote:

It's perfectly reasonable to use a List without ever accessing it randomly and nobody will criticize you for that.

Thanks.

without having to use all of its features

I meant without the primary feature (as in this case)

[Campbell Ritchie]

Monica Shiralkar wrote:. . . I meant without the primary feature (as in this case)

Agree with Paul: if you ask me what sort of use case for a List is, I shall say, “normai”.

The primary function of a List is to store object references, and that is what you are doing.

[Monica Shiralkar]

Campbell Ritchie wrote:

The primary function of a List is to store object references, and that is what you are doing.

Thanks, Yes. Thats the primary purpose of a list. I was confusing with primary purpose of ArrayList which is to store elements such that they have random access and ordering. Afterall arrayList is a List, so the primary purpose of List applies to this case also. I think the logic is that just for simply storing elements to be used later, one requires a List and instead of going for LinkedList, the simpler easy choice is ArrayList.

[Paul Clapham]

Monica Shiralkar wrote:I think the logic is that just for simply storing elements to be used later, one requires a List and instead of going for LinkedList, the simpler easy choice is ArrayList.

That's certainly what I do. It's not that choosing ArrayList is easier than choosing LinkedList -- I suppose it's just a habit, actually, so maybe it's easier in that sense.

[Monica Shiralkar]

If I have to draw a pie chart of the usage of various collections in my code during my career and also in the code of others in office that I have come across, ArrayList and HashMap together constitute 100%.  Certainly, the code I have written in my career or which I have come across of other developers, is not the best way to write code.

[Jesse Silverman]

Places like HackerRank and LeetCode and friends are chock-full of problem after problem that cries out for the use of the other data structures, and quite often can't be solved by just relying on those two.

I haven't re-iterated thru them since coming over to focus on Java, but back in C++ I'd go thru six different data structures doing a dozen different problems, including maybe one problem that would only meet time/space requirements using a Deque backed by ArrayDeque and another that would only pass when using one backed by a Doubly-Linked-List.

Then again, they are almost like commercials for a data structures and algorithms course, trying to make those who haven't completed one feel like they are missing out, and justifying the results of having taken them for those who have.

My feeling from years in industry is that there is an awful lot of commercial production enterprise code that would really benefit from better application of data structures, (older code tends to very naively think everything is an array and they are good enough, why use a second data structure) and that tho the aforementioned sites highlight their usefulness with problems that are superficially artificial, that in most cases at least, real problems would have very similar characteristics to the ones they present.

Also, people reflect on the data structures visible in the source code they are responsible for.  They may use message queuing systems literally every second they are at work without ever giving them a thought because they are only using the libraries, never looking at the code implementing them, for instance.

[Paul Clapham]

That's all very well, in a certain context. When you take basic Computer Science courses you spend a lot of time studying data structures and the big-O notation. And for those things you mentioned there, you need to know about data structures.

But the code I've been working on for years, and likewise I'm sure for the people which Monica works with, it's like this: Get a bunch of data from a database (on a hard drive, maybe even over a network), transform it into a user-friendly format, and display it (on a screen or over a network). Only the middle step uses the data structures and it's by far the fastest step. And over the past several years we have faster computers and more memory, so time/space requirements are less and less important.

So you've got a transaction which takes a tenth of a second from when the user clicks "Go" to when the user sees the result. Of that, you might have several milliseconds of processing on your multi-gigahertz server. Even if you optimized that down to nothing it wouldn't make any difference. So there's really very little incentive to spend any time choosing a better data structure. You're much better off reviewing the indexes over your database tables.

I know, it's not all like that. If you want to produce an image of a black hole then you need to optimize your processing of terabytes of data very aggressively, for example. But that's where we're coming from. ArrayList? LinkedList? Who cares, there's more important problems to deal with.

[Monica Shiralkar]

Paul Clapham wrote:If you want to produce an image of a black hole then you need to optimize your processing of terabytes of data very aggressively, for example. But that's where we're coming from. ArrayList? LinkedList? Who cares, there's more important problems to deal with.

Thanks. Got the point.

[Jesse Silverman]

Paul.  Good points.

I guess it all depends on how close you are to your data.

People writing code run by people on adjacent teams will generally always know when they have big data in areas of the application.
For Google, Amazon, Facebook and friends they generally know the data will be immense and almost everything needs to be at "Web Scale".
Other places the data will be small and they know it.

I came from an environment where we were basically writing a platform, so we would "know" that there would be a few dozen or a few hundred of some kinds of data and it was like you said, either half a second or one second, big deal.

Then some of the larger customers would say "What did you do?? This is so slow it isn't even usable, you have to fix this!" or "What did you do?  This takes so much memory that it slows to a crawl" (or crashes on 32-bit when it hit some process size limit).

We would look at it and review our tests and say "it should be fine" then it turned out that they had 18000 of something we were expecting a few dozen, it would turn out to be legitimate, they just had a crazy amount of data in some unexpected place.

They were by definition the largest customers with the largest data (and paid the most of our salaries!) and so we would need to go and re-work areas of the code to reduce in-memory stuff or some place we had O(n^3) complexity because 15^3 was small anyway.  We would have to go in and re-work that stuff.

Some of our snarkier developers would say "We think we are fast because we are all native code then we use dumb data structures and naive algorithms" and they were right in those cases.

I guess I am saying the hard case is when you are writing code for multiple audiences with different data set sizes you can't always accurately predict.

This doesn't happen when you are "close to your data" and you know your test cases will apply.  Premature optimization is a big waste of time.

Even as it was, smaller customers or ones with smaller data sets in those areas of the application would never see a difference, and would prefer new business features or better user interface somewhere -- but one-size-fits-all means that we had to code to satisfy whichever customers had the largest data in whatever areas.

Even for the scalability things, exotic data structures aren't always the solution, it might be not trying to hold more in memory at once than there is a need to, but sometimes it is.

For interviews with the larger Big Data outfits, they say early and often that perfectly valid solutions are often garbage to them because most of their stuff needs to scale in ways "traditional" coding for what we used to think of as normal, reasonable data sets would not.  They tend to place high value on the kind of solutions that don't do any unnecessary work, don't keep more in memory at once than is strictly needed for the most optimal solution, and use the ideal data structures again in ways that never show a difference with small data.

This is slightly different than solving inherently difficult problems which are hard to figure out even for small test cases.

I can say from the HackerRank and LeetCode things, I often had a valid solution after a few minutes that would pass the small test cases, but to get full credit I'd need a whole different approach to pass the larger ones without running out of stack or heap space, or running out of time.  Of those times where the simplest solution would be done in a few minutes, and I took a few hours to pass all the big fat cases, like a third of them were getting just the right flavor of data structure.

My point was there are times you KNOW you don't need to do that, times you KNOW you DO need to do that, and in my prior professional experience, places you KNEW you DIDN'T need to do that but then it turned out you did.  Real life can be frustrating, sometimes.

[Monica Shiralkar]

The bad part is that inspite of ArrayList being the collection most frequently used by me (and other developers),  I am yet to write any code where I used arraylist for its primary purpose, i,e ordered and random access. I will try a simple example for my understanding where ordered or random access is required and arraylist serves the purpose.

[Paul Clapham]

Monica Shiralkar wrote:The bad part is that inspite of ArrayList being the collection most frequently used by me (and other developers),  I am yet to write any code where I used arraylist for its primary purpose, i,e ordered and random access.

You could try this: LinkedList supports random access, but it has O(N) performance instead of ArrayList's O(1) performance. So try using LinkedList instead. Then you won't have to feel so guilty. Just remember, if it turns out you do need to do random access, don't forget to change back to ArrayList.

[Stephan van Hulst]

Paul Clapham wrote:LinkedList supports random access, but it has O(N) performance instead of ArrayList's O(1) performance.

By definition, that's not random access.

Monica Shiralkar wrote:I am yet to write any code where I used arraylist for its primary purpose, i,e ordered and random access.

I wouldn't say that random access is ArrayList's primary purpose. Its primary purpose is to hold an ordered sequence of elements. The fact that it supports random access makes it useful for some use cases that simply don't occur very often. Most of the time when you need constant lookup time, you are better served by hash map.

[Jesse Silverman]

Stephan van Hulst wrote:

Paul Clapham wrote:LinkedList supports random access, but it has O(N) performance instead of ArrayList's O(1) performance.

By definition, that's not random access.

I think what we may mean to say here is that Sun decided to allow one to use the indexed List methods on a LinkedList. I have seen various people grousing that they shouldn't have done so for the reason you highlight -- the performance is poor.  I do see that contrary to my recollection, it does NOT implement the RandomAccess tag Interface, which helps to remind one of that fact.  So I use "random access" in lowercase to indicate I can point to any element or range by index, RandomAccess capitalized in Java to mean that it will be pleasantly fast.

Monica Shiralkar wrote:I am yet to write any code where I used arraylist for its primary purpose, i,e ordered and random access.

I wouldn't say that random access is ArrayList's primary purpose. Its primary purpose is to hold an ordered sequence of elements. The fact that it supports random access makes it useful for some use cases that simply don't occur very often. Most of the time when you need constant lookup time, you are better served by hash map.

Maybe every time I did so I should have just thrown the elements into a TreeSet with an appropriate Comparator, but in the past, in Java and in other languages, I have very often kept an ArrayList or equivalent around and called Collections.sort( ) on it with an appropriate Comparator.  I think I would argue that if you are doing that (maybe you shouldn't, I am trying to improve my habits) then you are definitely making use of the RandomAccess nature of the ArrayList, albeit indirectly, as calling sort() on a list without random access is painful.  I vaguely remember trying to write sorts for linked lists that didn't implement such on exercises/problems and it was like trying to carry a bunch of jello up a hill without a bowl.

I know I often have used indexes or index ranges to get things done both at work and at home,  I consider all of those to be making use of random access.

So the take-home is that if you are calling sort() or using any of the methods that take one or more indexes on your ArrayList, or return one, you are taking advantage of its RandomAccess nature.  I have done that a lot at both work and on HackerRank/interview type questions.

[salvin francis]

Monica Shiralkar wrote:...I am yet to write any code where I used arraylist for its primary purpose, i,e ordered and random access...

Have you ever used the "get()" method from ArrayList in your code ? If yes, please explain what you think it does.

[Carey Brown]

This has been an interesting discussion and has led me to write a little class to scan my entire archive of .java files to see how many of the various Collections I've used. These projects span the age of Java itself, from small to middling in size. You can see the age of some of them by the use of the Vector class, which I haven't used in ages.

Projects... 429
Files...... 6,101
Lines...... 1,074,274
ArrayBlockingQueue          4
ArrayDequeue                0
ArrayList                1958
BitSet                    180
ConcurrentLinkedDequeue     0
ConcurrentLinkedQueue       5
DelayQueue                  0
HashMap                   649
HashSet                   184
Hashtable                  12
LinkedBlockingDequeue       0
LinkedBlockingQueue        11
LinkedHashMap              18
LinkedHashSet              16
LinkedList                 69
LinkedTransferQueue         1
PriorityBlockingQueue      10
PriorityQueue               2
Stack                      15
SynchronousQueue            1
TreeMap                    66
TreeSet                    52
Vector                    207

Edit: Note that "BitSet" is NOT a Collection.

[Monica Shiralkar]

Nice. Are all from line 4 onwards a collection? If so , I never knew there are so many. Never heard a Bit Set.

[Monica Shiralkar]

salvin francis wrote:

Monica Shiralkar wrote:...I am yet to write any code where I used arraylist for its primary purpose, i,e ordered and random access...

Have you ever used the "get()" method from ArrayList in your code ? If yes, please explain what you think it does.

I know that get is used for random access i.e. to access element at a particular index. But I have never come across a usecase where it required me to use get.

[Jesse Silverman]

Have you never written a sort?
I personally feel that is asked too often on interviews, but is the sort (ha ha!) of thing that while possible without any indexed access is rather painful.
There are some sorts that aren't too hard to do without any indexed gets or sets, but for most it would feel like you were trying to make dinner with your hands handcuffed behind your back.

I feel like I am reading your replies to say that an extremely, extremely high percentage of your code using ArrayLists, either does, or easily could make use of purely sequential access.
i.e. if all of the code you have accessing your ArrayLists were replaced with a forward-only Iterator, limiting you to sequential access, it would barely change it at all except that you would need to call .hasNext() and .next() ??