CODEWITHSUNDEEP
javaperformancedictionary
sg1
sg1

Reputation: 41

Map versus List

Input : Let's say I have an object as Person. It has 2 properties namely

In one hand I have a List of Person objects (with unique ssnNo) and in the other hand I have a Map containing Person's ssnNo as the key and Person's name as the value.

Output : I need Person names using its ssnNo.

Questions :

  1. Which approach to follow out of the 2 I have mentioned above i.e. using list or map? (I think the obvious answer would be the map).

  2. If it is the map, is it always recommended to use map whether the data-set is large or small? I mean are there any performance issues that come with the map.

Upvotes: 4

Views: 130

Answers (6)

Rob
Rob

Reputation: 6497

Map is the way to go. Maps perform very well, and their advantages over lists for lookups get bigger the bigger your data set gets.

Of course, there are some important performance considerations:

  1. Make sure you have a good hashcode (and corresponding equals) implementation, so that you data will be evenly spread across the buckets of the Map.

  2. Make sure you pre-size your Map when you allocate it (if at all possible). The map will automatically resize, but the resize operation essentially requires re-inserting each prior element into the new, bigger Map.

Upvotes: 3

Nuntipat Narkthong
Nuntipat Narkthong

Reputation: 1397

Using map especially one that implement using a hash table will be faster than the list since this will allow you to get the name in constant time O(1). However using the list you need to do a linear search or may be a binary search which is slower.

Upvotes: 0

dmon
dmon

Reputation: 30168

It's all pointers. It actually makes no sense to have a Map<ssn,PersonName> instead of a Map<ssn,Person>. The latter is the best choice most of the time.

Upvotes: 0

Steve P.
Steve P.

Reputation: 14699

I think it makes sense to have a Person object, but it also makes sense to use a Map over a List, since the look up time will be faster. I would probably use a Map with SSNs as keys and Person objects as values:

  Map<SSN,Person> ssnToPersonMap;

Upvotes: 0

arshajii
arshajii

Reputation: 129507

This looks like a situation appropriate for a Map<Long, Person> that maps a social security number to the relevant Person. You might want to consider removing the ssnNo field from Person so as to avoid any redundancies (since you would be storing those values as keys in your map).

In general, Maps and Lists are very different structures, each suited for different circumstances. You would use the former whenever you want to maintain a set of key-value pairs that allows you to easily and quickly (i.e. in constant time) look up values based on the keys (this is what you want to do). You would use the latter when you simply want to store an ordered, linear collection of elements.

Upvotes: 0

luke657
luke657

Reputation: 835

You're right, you should use a map in this case. There are no performance issues using map compared to lists, the performance is significantly better than that of a list when data is large. Map uses key's hashcodes to retrieve entries, in similar way as arrays use indexes to retrieve values, which gives good performance

Upvotes: 0

Related Questions