Left Join of Two Different Java Objects

Question

I have a list of Object1 ( List<Object1> ) and a list of Object2 ( List<Object2> )

• Object 1 has several properties, including id
• Object 2 has several properties, including object1id

I have some SQL background and I'm trying to do a left join on

object1.id = object2.object1id

This will result in a List<Object3> representing the left join. I could hard code the algorithm in Java (for ... for ...), but I'm sure it would be inefficient, at least because of the complexity of n * m.

Do you have a better solution? (with code, if possible, thanks!)

Answer 1

You are trying to do what Java is not really intended for.

If you are able to do this, you would be better off adding the Object1 attribute , which would be a list of Object2 containing the objects associated with this .

If you cannot, we have the opportunity to do it naively, otherwise you can try something like this:

 HashSet<Integer> hs = new HashSet<Integer>(list2.size()); for(Object2 o : list2) { hs.add(o.object1id); } //hs contains all the ids of list2 List<Object1> result = new ArrayList<Object1>(); //Or another class implementing List for(Object1 o : list1) { if(hs.contains(o.id)) result.add(o); } 

Not really, since you should store all identifiers as a HashSet, but since adding and accessing elements in a HashSet are O (1) (theoretically), the O (N + M) algorithm

If the Object3 class is built with Object1 and Object2 , use HasMap instead of HashSet , where the keys are identifiers and the values ​​are Object2. The last for loop in the code will look like this:

 Object2 o2 = hs.get(o.id); if(o2 != null) result.add(new Object3(o, o2); 

---

In addition to Oscar Lopez's comment:

If your objectid1 is not unique, you need to adapt the code as follows:

 HashMap<Integer, List<Object2>> hm = new HashMap<Integer, List<Object2>>(); for(Object2 o : list2) { List<Object2> l = hm.get(o.objectid1); if(l != null) { l.add(o); } else { List<Object2> l = new ArrayList<Object2>(); l.add(o); hm.put(o.objectid1, l); } //hm is map, where each entry contains the list of Object2 associated with objectid1 List<Object1> result = new ArrayList<Object1>(); for(Object1 o : list1) { List<Object2> l = hm.get(o.id); //l contains all Object2 with object1id = o.id for(Object2 o2 : l) result.add(new Object3(o, o2)); } 

Still in O (n + m), but with big constants ...

Answer 2

Create an index in the list. Scan the list and fill in the index:

 HashMap<Integer, Object2> index=HashMap<Integer, Object2>(); for (Object2 obj2: list2) { index.put(obj2.object1id, obj2); } 

Then scan the list and make the connection:

 for (Object1 obj1: list1) { Object2 obj2=index.get(obj1.id); // may be null Object3 obj3=new Object3(obj1, obj2); } 

Answer 3

If you are using Java 8, you can use streams . It might look something like this (assuming id is the identifier of Object1 to search for):

 List<Object3> newList = obj2List.stream().filter(x -> x.object1id == id).map(x -> obj2To3(x)).collect(Collectors.toList()); 

The case provided is rather vague, so it is difficult to give a more detailed answer.

Answer 4

I believe that the O(n*m) solution is inevitable if a more complex data structure infrastructure is not created - efficient joins in the database are implemented using indexes, hashes, etc. Also keep in mind that the correct implementation should take into account the case when more than one object in list2 has the same object1id - my code works in this case, but all solutions that just add obj2.object1id to Set or like keys in Map will not done.

But is it worth the complexity of the implementation? if the input lists are small, the O(n*m) solution will work fine. Here is my suggestion using the good old nested loops:

 List<Object3> list3 = new ArrayList<>(); for (Object1 obj1 : list1) { boolean found = false; for (Object2 obj2 : list2) { if (obj1.id.equals(obj2.object1id)) { list3.add(new Object3(obj1, obj2)); found = true; } } if (!found) list3.add(new Object3(obj1, null)); } 

To work above, I use an output object that looks like this:

 public class Object3 { private Object1 obj1; private Object2 obj2; public Object3(Object1 obj1, Object2 obj2) { this.obj1 = obj1; this.obj2 = obj2; } } 

Answer 5

A good solution would be to convert List of Object2 to Map. Then go to the Object1 list and get Object2 from the Map, eventually create the result of combining and adding to the Object3 List.

Answer 6

Provided that they implement some common interface (this will facilitate the task, especially when casting), then this is relatively simple.

It is still O (nm), since you need to go through both lengths of the list to find the items to add.

 public interface JoinInterface { int getId(); int getObject1Id(); // likely baggage here } public static List<? extends JoinableEntity> leftJoin(List<? extends JoinableEntity> left, List<? extends JoinableEntity> right) { List<JoinableEntity> result = new ArrayList<>(); result.addAll(left); for(JoinableEntity aLeft : left) { for(JoinableEntity aRight : right) { if(aLeft.getId() == aRight.getObject1Id()) { result.add(aRight); break; } } } return result; }