两个不同Java对象的"左连接"

Question

我有一个Object1(List<Object1>)列表和一个Object2(List<Object2>)列表

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

我有一些SQL背景,我正在尝试做的是执行"左连接"

object1.id = object2.object1id

这将导致List<Object3>表示左连接.我可以用Java硬编码算法(for ... for ...),但我确信这至少在n*m的复杂度下效率不高.

你有更好的解决方案吗？(如果可能,请使用代码,谢谢!)

Answer 1

你正在尝试做一些Java并不是真正意义上的东西.

如果你能够做到这一点,你最好添加一个属性Object1,这将是一个Object2包含与之相关的对象的列表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);
}

因为必须将所有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<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),但具有更大的常数......