比较 java 中的两个大列表

Question

我必须对每个列表中包含 1000 个对象的列表进行排列。我需要删除数组列表 1 中存在于数组列表 2 中的所有元素。目前我是运行 2 个循环，在最坏的情况下会导致 1000 x 1000 次操作。


List<DataClass> dbRows = object1.get("dbData");
List<DataClass> modifiedData = object1.get("dbData");
List<DataClass> dbRowsForLog = object2.get("dbData");
for (DataClass newDbRows : dbRows) {
            boolean found=false;
            for (DataClass oldDbRows : dbRowsForLog) {
                if (newDbRows.equals(oldDbRows)) {
                    found=true;
                    modifiedData.remove(oldDbRows);
                    break;
                }
            }
        }

public class DataClass{
    private int categoryPosition;
    private int subCategoryPosition;
    private Timestamp lastUpdateTime;
    private String lastModifiedUser;
    // + so many other variables 
    
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        DataClass dataClassRow = (DataClass) o;
        return  categoryPosition == dataClassRow.categoryPosition
                && subCategoryPosition == dataClassRow.subCategoryPosition && (lastUpdateTime.compareTo(dataClassRow.lastUpdateTime)==0?true:false)
                && stringComparator(lastModifiedUser,dataClassRow.lastModifiedUser);
    }

    public String toString(){
        return "DataClass[categoryPosition="+categoryPosition+",subCategoryPosition="+subCategoryPosition
                +",lastUpdateTime="+lastUpdateTime+",lastModifiedUser="+lastModifiedUser+"]";
    }
    
    public static boolean stringComparator(String str1, String str2){
         return (str1 == null ? str2 == null : str1.equals(str2));
    }

    public int hashCode() {
    int hash = 7;
    hash = 31 * hash + (int) categoryPosition;
    hash = 31 * hash + (int) subCategoryPosition
    hash = 31 * hash + (lastModifiedUser == null ? 0 : lastModifiedUser.hashCode());
    return hash;
    }
}

我能想到的最佳解决方法是通过调用 DataClass 的 tostring() 方法创建 2 组字符串并比较字符串。它将导致 1000（用于制作 set1）+ 1000（用于制作 set 2）+ 1000（在 set 中搜索）= 3000 次操作。我卡在了 Java 7. 有没有更好的方法来做到这一点？谢谢

Answer 1

利用 Java 的内置集合类处理 ~~大部分~~ 优化，利用 HashSet。它的contains方法的复杂度是O(1)。我强烈建议查看它是如何实现这一点的，因为它非常有趣。

List<DataClass> a = object1.get("dbData");
HashSet<DataClass> b = new HashSet<>(object2.get("dbData"));
a.removeAll(b);
return a;

这一切都为你完成了。

编辑：警告

为了使其工作，DataClass 需要实施 Object::hashCode。否则，您不能使用任何基于散列的收集算法。

编辑 2：实施 hashCode

对象的散列码不需要在每次实例变量改变时都改变。哈希码只需要反映判断相等性的实例变量.

例如，假设每个对象都有一个唯一字段 private final UUID id。在这种情况下，您可以通过简单地测试 id 值来确定两个对象是否相同。 lastUpdateTime 和 lastModifiedUser 等字段将提供有关对象 的信息 ，但具有相同 id 的两个实例将引用同一对象，即使lastUpdateTime和lastModifiedUser各不相同.

关键是，如果您真的想优化它，请在哈希计算中包含尽可能少的字段。从你的例子来看，似乎 categoryPosition 和 subCategoryPosition 可能就足够了。

无论您选择包括什么字段，从中计算哈希码的最简单方法是使用 Objects::hash 而不是运行自己的数字。

Answer 2

是Set A-B操作（只保留Set A中不在Set B = A-B中的元素）

如果使用 Set 没问题，那么我们可以像下面那样做。我们也可以使用 ArrayList 来代替 Set，但在 AL 的情况下，每个要 remove/retain 的元素都需要经过整个其他列表扫描。

Set<DataClass> a = new HashSet<>(object1.get("dbData"));
Set<DataClass> b = new HashSet<>(object2.get("dbData"));
a.removeAll(b);

如果需要排序，请使用 TreeSet。

尝试 return 来自 object1.get("dbData") 和 object2.get("dbData") 的一组，跳过一个中间集合创建。

比较 java 中的两个大列表

Comparing two large lists in java

java

java-7