java - 用于对等价类的元素进行分组的数据结构

我必须实现一个对等价类的元素进行分组的数据结构。

API:

interface Grouper<T>{
  void same(T l, T r);
  Set<EquivalenceClass<T>> equivalenceClasses();
}

interface EquivalenceClass<T>{
    Set<T> members();
}

例如，分组的行为如下:

Grouper g;
g.same(a, b);
g.equivalenceClasses() -> [[a,b]]

g.same(b, a);
g.equivalenceClasses() -> [[a,b]]

g.same(b, c);
g.equivalenceClasses() -> [[a,b,c]]

g.same(d, e);
g.equivalenceClasses() -> [[a,b,c], [d,e]]

g.same(c, d);
g.equivalenceClasses() -> [[a,b,c,d]]

我正在寻找一个可容纳约1000万个条目的实现。应该对其进行优化以填充它并获得一次等效类。

最佳答案

看一看Union-Find。联合(“相同”)可以在O(log N)中轻松完成，并且可以通过一些优化在有效的O(1)中完成。 “equivalenceClasses”是O(N)，这是无论如何都要访问所有内容的成本。