DisjointSet with O(1) find and O(1) amortised union
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.