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

Question

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

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

我有一些SQL的背景知识，我正在尝试对其执行“左连接”

object1.id = object2.object1id

这将导致一个表示左连接的List<Object3>。 我可以用Java硬编码一个算法，但我敢肯定，至少在n*m的复杂度下，这是不有效的

你有更好的解决办法吗？（如果可能，请提供代码，谢谢！）

Answer 1

如果他们实现了一些公共接口（这将使事情变得更容易，尤其是在铸造方面），那么这是相对简单的

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

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

Answer 2

一个好的解决方案可能是将Object2列表转换为映射。然后遍历Object1列表，从映射中获取Object2，最终创建连接并将结果添加到Object3列表中

Answer 3

您正在尝试做一些Java并不真正适合的事情

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

如果你做不到，我们仍然可以选择天真地去做，否则你可以尝试这样的方式：

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

不太好，因为必须将所有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);

---

关于Óscar López的评论：

如果你的目标不是唯一的，你必须按照以下方式调整代码：

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

仍然在O（n+m）中，但常数更大

Answer 4

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

HashMap<Integer, Object2> index=HashMap<Integer, Object2>();
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 5

如果您使用的是Java8，那么可以利用streams。它可能看起来像这样（假设id是要查找的Object1的id）：

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

提供的案例相当模糊，因此很难给出更详细的答案

Answer 6

我相信一个O(n*m)解决方案是不可避免的，除非创建一个更复杂的数据结构基础设施——数据库中的高效连接是implemented使用索引、哈希、，也请记住，正确的实现应该考虑^ {CD2}}中的不止一个对象具有相同的^ {{CD3}} -在这种情况下，我的代码工作，但是所有简单地将^ {CD4}}添加到^ {{CD5}}或作为^ {< CD6}}中的键的所有解决方案都将失败。p>

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

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

为了实现上述功能，我使用的输出对象如下所示：

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