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

Question

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<>();
            t.add(a);
            t.add(b);
        } 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;
            t.add(a);
            t.add(b);
        }

        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);
        refs.add(ref);
    }

    /**
     * @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() {

        }
    }
}

Answer 1

Union is \$O(\log n)\$, not \$O(1)\$

Consider a case where 1024 elements are initially added to their own set. Then do 512 unions of pairwise neighbors to make 512 sets of 2 elements each. This requires 512 copies in the "addAll" step, because half the elements are moved to a new set. Then do 256 unions of pairwise neighboring sets to make 256 sets of 4 elements each. This also requires 512 copies, because again half of all elements are moved to a new set. Continue to do unions in passes, where each pass you end up with 2x the number of sets as before. In the end, you will need 10 passes, and each pass will require 512 elements to be moved.

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.