两个不同Java对象的“左连接”

我有一个Object1（ List ）列表和一个Object2 List （ List ）

• 对象1具有多个属性，包括id
• 对象2有多个object1id ，包括object1id

我有一些SQL背景，我想要做的是执行“左连接”

object1.id = object2.object1id

这将导致List表示左连接。 我可以用Java硬编码算法（for … for …），但我确信这至少在n * m的复杂度下效率不高。

你有更好的解决方案吗？ （如果可能，请使用代码，谢谢！）

Answer 1

您正在尝试做一些Java并不是真正意义上的事情。

如果能够这样做，最好向Object1添加一个属性 ，它将是包含与this相关的对象的Object2列表。

如果你不能，我们仍然可以选择天真地做，否则你可以尝试这样的事情：

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

因为你必须将所有id存储在HashSet中，所以并不漂亮，但由于在HashSet中添加和访问元素是O（1）（理论上），算法是O（n + m）

如果您的Object3类是使用Object1和Object2构造的，请使用HasMap而不是HashSet ，其中键是id，值是object2。 代码中的最后一个for循环将变为：

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

---

继ÓscarLópez发表评论：

如果您的objectid1不是唯一的，您必须按如下方式调整代码：

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

仍然在O（n + m），但具有更大的常数……

Answer 2

在List上创建索引。 扫描列表并填写索引：

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

然后，扫描列表并进行连接：

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

Answer 3

如果您使用的是Java 8，则可以利用流 。 它可能看起来像这样（假设id是要查找的Object1的id）：

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

提供的案例非常模糊，因此很难给出更详细的答案。

Answer 4

一个好的解决方案可能是将Object2的List转换为Map。 然后遍历Object1 List并从Map获取Object2，最终创建Join并在Object3 List中添加结果。

Answer 5

我认为O(n*m)解决方案是不可避免的， 除非创建更复杂的数据结构基础结构 – 使用索引，哈希等实现数据库中的高效连接。还要记住正确的实现应该考虑这样的情况： list2中的多个对象具有相同的object1id – 我的代码在这种情况下工作，但是只是将obj2.object1id添加到Set或作为Map键的所有解决方案都将失败。

但是实现的复杂性值得吗？ 如果输入列表很小， O(n*m)解决方案就可以正常工作。 这是我的建议，使用好的旧嵌套循环：

 List 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)); } 

为了使上述工作，我使用的输出对象如下所示：

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

Answer 6

如果它们实现了一些通用接口（这会使事情变得更容易，尤其是使用转换），那么这是相对简单的。

它仍然是O（nm），因为您必须遍历列表的两个长度才能找到要添加的元素。

 public interface JoinInterface { int getId(); int getObject1Id(); // likely baggage here } public static List leftJoin(List left, List right) { List 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; }