Performance benefits of using a List vs Map in Java

Question

I have been wondering what is the actual benefit of using Lists. Please note that my question is not "when to use what" but rather Is there any impact on performance if i insist on having maps as my primary objects

obviously if my aim is to just work on values

UPDATE after not being clear with my intent at first glance: I meant if i just want to filter a list of [8000] people whose age is > 30 , i would use a list... But can i use a map instead and have it be used instead - My Question is - will there be any performance hindrance ?

I would also use List. But do we get any performance boost - if yes - How can I see it myself.

for example if i take

List <Integer> listOfInt = new ArrayList<>(map.values());

It would make sense to use Map as my global object and serve lists based on it.

I know the key/value O(1) runtime for insert or remove in Maps but then why Lists are preferred most places i have seen.

You question doesn't make any sense because it largely depends on the use case. If you don't describe what "to just work with values" means nobody can tell. — fhossfel, Oct 04 '17 at 10:04
I meant if i just want to filter a list of people whose age is > 30 , i would use a list... But can i use a map instead and have it be used instead - My Question is - will there be any performance hindrance ? — RangerReturn, Oct 04 '17 at 10:05
How can i also be as sure as you ... is there a way i can see the difference myself — RangerReturn, Oct 04 '17 at 10:09
I don't think so. Looping over 8000 elements will be so fast that you won't see much of a difference. Just write a benchmark an try with 800.000 entries. — fhossfel, Oct 04 '17 at 10:10
@Saurabh Make stress tests with map and list and measure the time. (for example `long startTime = System.nanoTime();` create a loop with 10.000.000 entries and then measure time again. — Bevor, Oct 04 '17 at 10:11
it depends,if you want key value pair you will use map,if you want list of elements you use list and if you want unique items you use set.now you can compare performance of these within their category like you can check which one will prove useful list for you between Arraylist,LinkedList,etc. — NikhilP, Oct 04 '17 at 12:11

score 8 · Accepted Answer · answered Oct 04 '17 at 10:15

my question is not "when to use what"

but it should. List and Map are having different use. A List is - well - a list of values without any explicit key. Item in a list is designated by its position.

obviously if my aim is to just work on values I would also use List.

yes, that's correct

But do we get any performance boost

Please note,. the Map is not a simple structure. For each item in a map, an "Entry" object is created with references to the key and the value object, an hash array is created, etc.. so using map you definitely use more memory and code. For simpler cases the performance difference is negligible

score 1 · Answer 2 · answered Oct 04 '17 at 10:11

1

It depends on the use case. With your example it could make a difference in the usage for example if you want access a specific object. The access time with a List would be O(n) while in a Map it is O(1).

If you don't care about specific retrieval of objects you can use a List.

answered Oct 04 '17 at 10:11

Murat Karagöz

35,401
16
78
107

Thanks, my aim is to provide filtering capabilities (updated the question with it). – RangerReturn Oct 04 '17 at 10:13
I don't agree. An item inside a list can be accessed in O(1) if you know the position. Access in MAp is O(log(n)) or similar, because the key needs to be looked-up. – gusto2 Oct 04 '17 at 10:14
Access in a map is O(logN) ? how ? – Sujal Mandal Oct 04 '17 at 10:17
@gusto2 you are wrong. It should be O(1), but for HashMaps it could happen to be O(n) worst case check https://stackoverflow.com/questions/4553624/hashmap-get-put-complexity – Oct 04 '17 at 10:28
@MehdiB. well - O(1) you can expect on small (1 level) maps, however if there are ~ 10^3 or 10^4 records with uniform distribution you will get O(log(n)) as claims the answer in your link. Regardless that, if Map is used instead of List, it just creates additional structures and relations. – gusto2 Oct 04 '17 at 10:39
@SujalMandal O(logN) comes with how the map works. It create an array of values as "buckets". Each bucket contains items with certain hashCode. As MehdiB linked an answer, the best approach is creating a sorted tree, the the access time is O(log N) (that's all hidden behind the 'Map' interface) – gusto2 Oct 04 '17 at 10:44
I still don't understand how you can say that the access time is O(logN) because atleast in HashMap(java) the bucket tables just point to a LinkedList of Entry, & whenever we involve linkedlist it's always O(n) can you explain your point ? @gusto2 – Sujal Mandal Oct 04 '17 at 12:24
@SujalMandal I have to be more specific. O( log n) is valid for the [TreeMap](https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html). For the default HashMap the access time can vary from O(1) to O(n) (from best to worse case) depends on the hash collision. How you can have O(1)?? It would work, it you'd have an array covering all possible hash values (which is int) – gusto2 Oct 04 '17 at 12:45
@SujalMandal and apparently I am wrong.. now I see the HashMap table is based on the capacity and loadFactory but effectively it tries to match the size of the map. Then the access time is O(1) with high probability with the uniform hash code distribution. In theory it still matches (O log n), just the table resizing increasis the log base :P Thank you for inspiration, now I am wiser – gusto2 Oct 04 '17 at 13:09
@gusto2 yeah capcity & load factor are the thing when it comes to maps.. :) the trees & lists are in the game when things get bad :D – Sujal Mandal Oct 04 '17 at 16:04

Performance benefits of using a List vs Map in Java

2 Answers2