# DisjointSet with O(1) find and O(1) amortised union

Does this code outperform the common implementation with path-compression and union-by-rank? I'm still okay with a review.

GitHub

import java.util.*;

public class DisjointSet<E> {
public static void main(String... args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();

DisjointSet<String> set = new DisjointSet<>();

for (int i = 0; i < n; i++) {
String a = s.next();
String b = s.next();
set.union(a, b);
}

System.out.println(set);
}

/**
* a map from each element to a reference to the set
* that contains them. The reference is used so that many
* map entries can be updated at once in O(1) without
* the cost of iterating through each entry.
* This occurs when performing the union. If we are merging
* a set A and a set B then we would otherwise be required
* to iterate through all of B's entries and point them to
* A and then call A.addAll(B). By having a mutable reference
* we skip the iteration and update all entries of B in O(1).
*/
private HashMap<E, Ref<Set<E>>> map = new HashMap<>();

/**
* a set of references to subsets.
* Just used for #toString().
*/
private Set<Ref<Set<E>>> refs = new HashSet<>();

/**
* @time worst case O(n), amortised O(1)
*/
public void union(E a, E b) {
Ref<Set<E>> ra = map.get(a);
Ref<Set<E>> rb = map.get(b);

Set<E> sa = ra != null ? ra.value : null;
Set<E> sb = rb != null ? rb.value : null;

Set<E> t;

if (sa == null && sb == null) {
t = new HashSet<>();
} else if (sa != null && sb != null) {
t = sa.size() > sb.size() ? sa : sb;

// addAll is worst-case O(n) but you have to add n items to be able to
// experience that worst case, and all intermediate adds will be O(1),
// so #union is amortised O(1)
t.addAll(sa.size() > sb.size() ? sb : sa);
} else {
t = sa != null ? sa : sb;
}

Ref<Set<E>> ref = ra != null ? ra : rb != null ? rb : new Ref<>();

ref.value = t;

map.put(a, ref);
map.put(b, ref);

refs.remove(ra);
refs.remove(rb);
}

/**
* @param e the element whose (sub)set you would like to find.
* @return the set that e belongs to or null if it is not present
* @time O(1)
*/
public Set<E> find(E e) {
Ref<Set<E>> ref = map.get(e);
return ref != null ? ref.value : null;
}

/**
* @time O(n)
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();

for (Ref<Set<E>> ref : refs) {
builder.append(ref.value);
builder.append('\n');
}

return builder.toString();
}

private class Ref<R> {
private R value;

Ref(R r) {
value = r;
}

public Ref() {

}
}
}


### Union is $O(\log n)$, not $O(1)$
As you can see from the above, with N=1024, you end up with N unions taking N * log N copies, or on average log N copies per union.