java - 具有可定制 "equals"的类集合

Question

我有一个数据类:

public class MyData {
  final Integer alpha;
  final Double beta;
  final Integer foo;
  final Double bar;
}

我需要 .equals和 .hashCode具有涉及所有四个领域的常规定义。但我还有一个重要的要求:

给定大量MyData对象，我需要快速检查是否有新的 MyData对象与 .alpha 上的任何现有对象匹配和 .beta字段仅。

我不想采用的三种方法:

1. 复合对象:

public class MyData {
  final MyDataKey alphaAndBeta;
  final Integer foo;
  final Double bar;
}
public class MyDataKey {
  final Integer alpha;
  final Double beta;
}

然后我可以针对 HashSet<MyDataKey> 进行查找，这并不优雅，因为该对象的所有其他用途都需要引用 dataObj.alphaAndBeta.alpha而不是 dataObj.alpha .

1. 比较器:

public class OnlyAlphaAndBeta implements Comparator<MyData> {
  int compare(MyData a, MyData b) {...}
}

然后这会让 new TreeSet<MyData>(new OnlyAlphaAndBeta())做我想要的查找；但是用 O(log(N)) 而不是 O(1)。

1. 多级查找:

public class MyDataLookup {
  Map<Integer, Set<Double>> existingAlphaBeta;
  
  boolean contains(MyData query) {
    Set<Double> betas = this.existingAlphaBeta.get(query.alpha);
    if (betas == null) {
      return false;
    }
    return betas.contains(query.beta);
  }

  boolean add(MyData toInsert) {...};
}

这在 O(1) 中完成了工作，但如果键不仅仅是 2 个字段怎么办？我可以继续嵌套 Map<A, Map<B, Map<C, ...>>>对于键中的每个字段，但这似乎不正确。当然，我宁愿只计算一个散列并在一张表中查找它。

---

我想我要找的是类似 HashSet 的东西, 但它可以专门用于使用 其他 的东西而不是 .equals和 .hashCode方法，类似于如何 Comparator重新定义 SortedSet 的顺序.这样的集合不会满足 Set contract 不再存在，但它会是“set-like”。

在任何维护良好的大型 Java 实用程序库中是否存在类似的东西？或者，我是否忽略了一些明显的实现目标的方法？

Answer 1

使用 Map 是正确的方法，但您可以将其封装在 Set 实现中，该实现具有“a Set”的预期行为使用自定义 equals”。

public class CustomSet<E> extends AbstractSet<E> {
    private final Function<E, Object> theKeyFunction;
    private final HashMap<Object, E> backend = new HashMap<>();

    public CustomSet(Function<E,Object> keyFunction) {
        theKeyFunction = Objects.requireNonNull(keyFunction);
    }

    @Override
    public int size() {
        return backend.size();
    }

    @Override
    public boolean add(E e) {
        Objects.requireNonNull(e);
        return backend.putIfAbsent(theKeyFunction.apply(e), e) == null;
    }

    @Override
    public boolean contains(Object o) {
        if(o == null) return false;
        @SuppressWarnings("unchecked") E e = (E)o;
        Object key;
        try { key = theKeyFunction.apply(e); }
        catch(ClassCastException ex) { return false; }
        return backend.containsKey(key);
    }

    @Override
    public boolean remove(Object o) {
        if(o == null) return false;
        @SuppressWarnings("unchecked") E e = (E)o;
        Object key;
        try { key = theKeyFunction.apply(e); }
        catch(ClassCastException ex) { return false; }
        return backend.remove(key) != null;
    }

    @Override
    public void clear() {
        backend.clear();
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return backend.values().retainAll(c);
    }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        return backend.values().removeIf(filter);
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        backend.values().forEach(action);
    }

    @Override
    public Iterator<E> iterator() {
        return backend.values().iterator();
    }

    @Override
    public Spliterator<E> spliterator() {
        return backend.values().spliterator();
    }

    @Override
    public Object[] toArray() {
        return backend.values().toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return backend.values().toArray(a);
    }    
}

为简单起见，此Set 不支持null。

此类重写了一些它不必重写的方法，以便在对其进行迭代或流式处理时提供更好的性能。除此之外，它很简单。如果您认为“但是内部使用Map 的Set 效率很低”，请查看HashSet 或 的源代码树集...

这个集合的实现可以像这样测试

record Person(String name, int age) {}

Set<Person> nameSet = new CustomSet<>(Person::name);
Set<Person> ageSet = new CustomSet<>(Person::age);

for(String name: List.of("John", "Paul", "George", "Ringo")) {
    for(int age: new int[] { 20, 24, 27, 31 }) {
        Person p = new Person(name, age);
        if(nameSet.add(p)) System.out.println("added " + p + " to nameSet");
        if(ageSet.add(p)) System.out.println("added " + p + " to ageSet");
    }
}
System.out.println();
System.out.println("nameSet: " + nameSet);
System.out.println("ageSet:  " + ageSet);
System.out.println();
Person p = new Person("Paul", 100);
System.out.println("nameSet contains " + p + "? " + nameSet.contains(p));
System.out.println("ageSet  contains " + p + "? " + ageSet.contains(p));
p = new Person("Bob", 27);
System.out.println("nameSet contains " + p + "? " + nameSet.contains(p));
System.out.println("ageSet  contains " + p + "? " + ageSet.contains(p));

added Person[name=John, age=20] to nameSet
added Person[name=John, age=20] to ageSet
added Person[name=John, age=24] to ageSet
added Person[name=John, age=27] to ageSet
added Person[name=John, age=31] to ageSet
added Person[name=Paul, age=20] to nameSet
added Person[name=George, age=20] to nameSet
added Person[name=Ringo, age=20] to nameSet

nameSet: [Person[name=George, age=20], Person[name=John, age=20], Person[name=Ringo, age=20], Person[name=Paul, age=20]]
ageSet:  [Person[name=John, age=20], Person[name=John, age=24], Person[name=John, age=27], Person[name=John, age=31]]

nameSet contains Person[name=Paul, age=100]?true
ageSet  contains Person[name=Paul, age=100]?false
nameSet contains Person[name=Bob, age=27]?false
ageSet  contains Person[name=Bob, age=27]?true

展示了对两组相等性的不同理解，这导致了与适用于 TreeSet 的警告相同，比较器与 equals 不一致。混合具有不同键函数的集合可能会导致与将排序集合与不同比较器混合或将此类集合与普通哈希集混合一样的怪异行为。

如果键由多个属性组成，则可以使用专用键对象，但这并不意味着应用程序域对象必须是组合对象:

record MyData(int alpha, double beta, int foo, double bar) {}

Set<MyData> set = new CustomSet<>(d -> {
    record Key(int alpha, double beta) {}
    return new Key(d.alpha(), d.beta());
});

set.add(new MyData(1, 1.0, 100, 1.23));
System.out.println(set.contains(new MyData(1, 1.0, -1, Double.NaN))); // true

没有 record 的旧 Java 版本的解决方案有点冗长，但原理保持不变。如果您不需要最佳性能，您还可以使用 List 键，因为它们具有有效的 equals 和 hashCode 实现:

// Java 8 compatible
Set<MyData> set = new CustomSet<>(d -> Arrays.asList(d.alpha(), d.beta()));