What is the best way to merge similar objects in a java List?

Question

Here is my problem (simplified):

Suppose we have a class:

public class MyClass{
String name;
Double amount;
String otherAttribute;
}

And a List<MyClass> myList

Suppose we have 2 elements from myList. Let's say object1 and object2

What I would like to do is:

if (object1.name.equals(object2.name){
//add amount of object2 to object1
//remove object 2 from the list
}

Considering I have a large list (maybe 100 elements) and I would like to find the best and less consuming way to do what I want.

What would you suggest ?

---

EDIT:

• Yes 100 items is not large, but I would call this method (of merging similar objects) many times for many different sized lists. So that's way I would like to find the best practice for this.

• I can't override equals or hashCode methods of MyClass, unfortunately (client requirement)

Answer 1

I'd add the objects to a HashMap where the name is the key and MyClass is the value being stored. Loop through each object in your list to add them to the map. If the name isn't in the map, just add the name, object pair. If it is already in the map, add the amount to the object already stored. When the loop completes, extract the objects from the map.

Answer 2

100 elements is a tiny size for a list, considering you're not going to repeat the operation some hundreds of thousands times. If it's the case, I'd consider creating a data structure indexing the list items by the search property (Map for instance), or ordering it if suitable and using an efficient search algorithm.

One approach (as suggested by Bill) would be to traverse the List adding every element to a Map, with the name property as key. You can take advantage of put's return to know if a name has been previously put into the map, and add the previosuly accumulated amounts in the current element. Finally, you could use values() to get the List without duplicates.

For instance:

List<MyClass> l;
Map<String, Myclass> m = new HashMap<MyClass>();
for (MyClass elem : l) { 
    MyClass oldElem = m.put(elem.getName(), elem);
    if (oldElem != null) { 
        elem.setAmount(elem.getAmount() + oldElem.getAmount());
    }
} 
l = new ArrayList<MyClass>(m.values());

If you need to preserve order in the list, consider using a LinkedHashMap.

Answer 3

This is an O(n^2) problem unfortunately. You need to compare n elements to n-1 other elements. There is no way to do this but to brute force it.

If you used a HashMap however, you could check the map for an element before adding it to the Map which is an O(1) operation. It would look something like this:

HashMap<String, MyClass> map = new HashMap<String, MyClass>();

when you add an element:

if (map.get(obj1.name) != null) {
    var obj2 = map.get(obj1.name);
    obj2.amount = obj2.amount + obj1.amount;
    map.put(obj1.name, obj2);
}

Answer 4

'Large' is relative, 100 items is definitely not large, imagine if you had to process a stream of 1.000.000 items/second. Then you would redefine large :D

In your example, what I think would be good to avoid would be to create a Set of your items' names. Searching a java HashSet takes O(1), so if an objects' name exists in the hash set, then update it on the list. An even better solution would be to create a HashMap, on which you could say e.g.

if(mymap.contains(thename)){
    mymap.put(thename, newSum);
}

this being an example of how you could use it. Here's a link to get you started: http://java67.blogspot.gr/2013/02/10-examples-of-hashmap-in-java-programming-tutorial.html

Answer 5

I suggest to optimize (if possible) by not even doing the .add() to the list if an element with the same name exists. Using one of the hash based collections in combination with a proper equals() & hashCode() implementation based on MyClass.name should also give you somewhat good performance.

Answer 6

First, since you cannot override equals or hashCode, then you need to have the function that will do this functionality in the same package as your MyClass class, since no accessor methods are defined in MyClass

Second, try to have your items in a LinkedList, so that you can remove repeating elements from that list really quick without having to move around the other items.

Use a map to keep track of the amount that corresponds to a given name, while iterating the list, and removing repeating elements at the same time. In this way you don't have to create a new list.

List<MyClass> myClass_l;

Map<String, MyClass> nameMyClass_m = new HashMap<String, MyClass>();

for (Iterator<MyClass> iterator = myClass_l.iterator(); iterator.hasNext(){
    MyClass m = iterator.next();
    if (nameAmount_m.contains(m.name)){
        MyClass firstClass = m.get(m.name);
        firstClass.amount += m.amount;
        iterator.remove();
    }
    else{
        nameMyClass_m.put(m.name, m);
    }
}

By the time you have finished the loop, you will have the items you want in your original list.