在 Java 中查看 ArrayList 是否包含对象的最有效方法

optimization algorithm java search arraylist

2022-08-31 13:48:10

我在Java中有一个对象的ArrayList。这些对象有四个字段，其中两个字段用于将对象视为等于另一个字段。鉴于这两个字段，我正在寻找最有效的方法来查看数组是否包含该对象。

问题是这些类是基于 XSD 对象生成的，因此我无法修改类本身以覆盖 ..equals

有没有比循环并手动比较每个对象的两个字段，然后在找到时中断更好的方法吗？这似乎太乱了，寻找更好的方法。

编辑：ArrayList 来自未编组到对象中的 SOAP 响应。

答案 1

这取决于你需要多高效率。只需循环访问列表以查找满足特定条件的元素是 O（n），但如果可以实现 Equals 方法，ArrayList.Contains 也是如此。如果你不是在循环或内部循环中执行此操作，这种方法可能很好。

如果您真的需要不惜一切代价实现非常高效的查找速度，则需要执行两项操作：

解决生成类的事实：编写一个适配器类，它可以包装生成的类，并根据这两个字段实现 equals（）（假设它们是公共的）。不要忘记还要实现hashCode（） (*)
使用该适配器包装每个对象，并将其放入哈希集中。HashSet.contains（）具有恒定的访问时间，即 O（1）而不是 O（n）。

当然，构建此哈希集仍然需要 O（n）成本。只有当构建 HashSet 的成本与您需要执行的所有包含（）检查的总成本相比可以忽略不计时，您才会获得任何收益。尝试构建没有重复的列表就是这样一种情况。

* (）实现hashCode（）最好通过XOR'ing（^运算符）完成，该哈希码与您用于相等实现的相同字段的哈希码（但乘以31以减少XOR产生0的机会）

答案 2

您可以将比较器与Java的内置方法一起使用，以进行排序和二进制搜索。假设您有一个这样的类，其中 a 和 b 是要用于排序的字段：

class Thing { String a, b, c, d; }

您可以定义比较器：

Comparator<Thing> comparator = new Comparator<Thing>() {
  public int compare(Thing o1, Thing o2) {
    if (o1.a.equals(o2.a)) {
      return o1.b.compareTo(o2.b);
    }
    return o1.a.compareTo(o2.a);
  }
};

然后对列表进行排序：

Collections.sort(list, comparator);

最后进行二进制搜索：

int i = Collections.binarySearch(list, thingToFind, comparator);