Get cumulative value from a List of Map

Question

I have a List of Map<String, Integer> . Each Map instance contain the productName as key, product price as value.

List<Map<String, Integer>> products = GET_ALL_PRODUCTS();

For example the List could contain Maps with the following data :

Map 1:

"prod1" : 10
"prod2" : 5
"prod3" : 2

Map 2:

"prod3" : 3
"prod4" : 6

Map 3:

"prod1" : 12
"prod4" : 8

I need to generate a new Map<String, Integer> which contains productName as key still, but with the cumulative amount of price for each product as value. That is:

new Map should contain:

"prod1" : 10+12
"prod2" : 5
"prod3" : 2+3
"prod4" : 6+8

I ended up with the following code, I am wondering what is the most efficient way to generate this new Map??

Map<String, Integer> cumulativeMap = new HashMap<String, Integer>();
for(int i=0; i< products.size(); i++){
    Map<String, Integer> product = products.get(i);
    ...
}

Masudul · Accepted Answer · 2013-11-18T12:15:44.067

5

Try,

List<Map<String, Integer>> products = new ArrayList<>();
//Add products Maps here 

Map<String, Integer> cumulativeMap = new HashMap<String, Integer>();
// Use enhaced for loop for efficiency.
for(Map<String, Integer> productMap: products){
  for(Map.Entry<String, Integer> p: productMap.entrySet()){

   if(cumulativeMap.containsKey(p.getKey())){
      cumulativeMap.put(p.getKey(), cumulativeMap.get(p.getKey())+ p.getValue());
   }
   else{
     cumulativeMap.put(p.getKey(),  p.getValue());
   }
  }
}

edited Nov 18 '13 at 12:15

answered Nov 18 '13 at 11:58

Masudul

21,823
5
43
58

is it more efficient than the index-based loop? – aga Nov 18 '13 at 12:12
You should avoid calling `get` inside a loop, @aga. Utilizing `Map.Entry` should be preferred. – predi Nov 18 '13 at 12:14
@predi so, the time complexity of `HashMap.get` method is `O(N)`, right? – aga Nov 18 '13 at 12:17
1

No, it's not more efficient than the index-based loop, unless the `List` is `LinkedList` or something like this. An `ArrayList` implements `RandomAccessList` and so the indexed access must be faster *per definition*. However, the difference is most probably negligible. and using the for-each loop is more readable. – maaartinus Nov 18 '13 at 12:17
1

@aga, [see this](http://stackoverflow.com/questions/4553624/hashmap-get-put-complexity). – predi Nov 18 '13 at 12:18
2

@aga: No, the time complexity of `HashMap.get` is `O(1)` assuming the `hashCode` works well. It can get as bad as `O(N)` in pathological cases only. However, by using the `entrySet` you save the access. – maaartinus Nov 18 '13 at 12:20
@predi, okay, it's `O(1)`, but it tends to be equal `O(N)` in some particular cases. now I understand. thanks for the explanation! – aga Nov 18 '13 at 12:21

Get cumulative value from a List of Map

1 Answers1