HashSet vs TreeSet vs ArrayList

It turns out that there are times when a (HashSet|TreeSet)+ArrayList approach is more efficient than a HashSet-only approach, and times when it is not. This is interesting because the former maintain order while the latter does not.

Here is some code that runs tests on most of the cases discussed above. It compares HashSet to TreeSet as well as both combined with ArrayList (to ensure list order).

code:

---

import java.util.*;
import java.math.*;
public class NoDupsTest
{
  /* ---- HashSet approach (list order not maintained) ---- */
  public static void test_HashSet(ArrayList a_master)
  {
    ArrayList a = new ArrayList(a_master);
    long cur = System.currentTimeMillis();
    HashSet h = new HashSet(a);
    a.clear();
    a.addAll(h);
    long diff = System.currentTimeMillis()-cur;
    System.out.println("HashSet approach (no order) = "+diff);
  }

  /* ---- TreeSet approach (list order not maintained, but sorted) ---- */
  public static void test_TreeSet(ArrayList a_master)
  {
    ArrayList a = new ArrayList(a_master);
    long cur = System.currentTimeMillis();
    TreeSet t = new TreeSet(a);
    a.clear();
    Iterator iter = t.iterator();
    while (iter.hasNext())
      a.add(iter.next());
    long diff = System.currentTimeMillis()-cur;
    System.out.println(
      "TreeSet approach (sorted order) = "+diff+" ms");
  }

  /* ---- ArrayList and HashSet approach (order maintained) ---- */
  public static void test_HashSet_listOrder(ArrayList a_master)
  {
    ArrayList a = new ArrayList(a_master);
    long cur = System.currentTimeMillis();
    Set set = new HashSet();
    List newList = new ArrayList();
    for (Iterator iter = a.iterator(); iter.hasNext(); ) {
      Object element = iter.next();
      if (set.add(element))
        newList.add(element);
    }
    a.clear();
    a.addAll(newList);
    long diff = System.currentTimeMillis()-cur;
    System.out.println(
      "ArrayList/HashSet approach (list order) = "+diff+" ms");
  }

  /* ---- ArrayList and TreeSet approach ---- */
  public static void test_TreeSet_listOrder(ArrayList a_master)
  {
    ArrayList a = new ArrayList(a_master);
    long cur = System.currentTimeMillis();
    Set set = new TreeSet();
    List newList = new ArrayList();
    for (Iterator iter = a.iterator(); iter.hasNext(); ) {
      Object element = iter.next();
      if (set.add(element))
        newList.add(element);
    }
    a.clear();
    a.addAll(newList);
    long diff = System.currentTimeMillis()-cur;
    System.out.println(
      "ArrayList/TreeSet approach (list order) = "+diff+" ms");
  }

  public static void main(String[] args)
  {
    int num = Integer.parseInt(args[0]);
    int numUnique = Integer.parseInt(args[1]);
    /* Create master list */
    Random rnd = new Random();
    ArrayList masterList = new ArrayList();
    for (int i=0; i<num; i++) {
      masterList.add(new Integer((Math.abs(rnd.nextInt())%numUnique)));
    }
    /* Run tests */
    test_HashSet(masterList);
    test_TreeSet(masterList);
    test_HashSet_listOrder(masterList);
    test_TreeSet_listOrder(masterList);
  }
}

---

The (crude) code test above takes, as arguments, the number of objects in the list and the number of unique objects (they are distributed randomly).

My sample runs looked like this:

(first arg is number of objects, second arg is number of unique objects -- distributed randomly)

% java NoDupsTest 500000 500000
% java NoDupsTest 500000 250000
etc.

and resulted in

code:

---

List size = 500,000 Integer objects (Integer implements Comparable)
Unique objects are distributed randomly throughout list.
All times in milliseconds.
AL=ArrayList
ORD=Ordered
              --Unordered--        --Ordered--
Num unique  HashSet  TreeSet  HashSet+AL TreeSet+AL   Best       Best(ORD)
----------  -------  -------  ----------- ----------  --------   ---------
500,000     1372     3284     2283        4216        HashSet    HashSet+AL
250,000     1212     2754     1522        2754        HashSet    HashSet+AL
100,000     1031     2754     721         2123        HashSet+AL HashSet+AL
50,000      951      1973     541         1833        HashSet+AL HashSet+AL
25,000      921      1622     471         1452        HashSet+AL HashSet+AL
10,000      861      1182     521         1181        HashSet+AL HashSet+AL
5,000       801      932      330         871         HashSet+AL HashSet+AL
1,000       731      661      331         631         HashSet+AL HashSet+AL
100         721      470      250         460         HashSet+AL HashSet+AL

---

In summary, to efficiently remove duplicate objects from an ArrayList, HashSet+ArrayList is a good general strategy and maintains list order. The main disadvantage is, however, more memory. Most interestingly (although it makes sense when you think about it some), both (HashSet|TreeSet)+AL can be superior to HashSet alone.