Comparing the Performance of Sets and Lists

Sets are more efficient than lists for storing nonduplicate elements. Lists are useful for accessing elements through the index. The elements in a list can be accessed through the index. However, sets do not support indexing, because the elements in a set are unordered. To traverse all elements in a set, use a foreach loop. We now conduct an interesting experiment to test the performance of sets and lists.

The code below gives a program that shows the execution time of (1) testing whether an element is in a hash set, linked hash set, tree set, array list, and linked list, and (2) removing elements from a hash set, linked hash set, tree set, array list, and linked list.

package demo;
import java.util.*;

public class SetListPerformanceTest {
    static final int N = 50000;

    public static void main(String[] args) {
        // Add numbers 0, 1, 2, ..., N - 1 to the array list
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < N; i++)
            list.add(i);
        Collections.shuffle(list); // Shuffle the array list

        // Create a hash set, and test its performance
        Collection<Integer> set1 = new HashSet<>(list);
        System.out.println("Member test time for hash set is " + getTestTime(set1) + " milliseceonds");
        System.out.println("Remove element time for hash set is " + getRemoveTime(set1) + " milliseceonds");

        // Create a linked hash set, and test its performance
        Collection<Integer> set2 = new LinkedHashSet<>(list);
        System.out.println("Member test time for linked hash set is " + getTestTime(set2) + " milliseceonds");
        System.out.println("Remove element time for linked hash set is " + getRemoveTime(set2) + " milliseceonds");

        // Create a tree set, and test its performance
        Collection<Integer> set3 = new TreeSet<>(list);
        System.out.println("Member test time for tree set is " + getTestTime(set3) + " milliseceonds");
        System.out.println("Remove element time for tree set is " + getRemoveTime(set3) + " milliseceonds");

        // Create an array list, and test its performance
        Collection<Integer> list1 = new ArrayList<>(list);
        System.out.println("Member test time for array list is " + getTestTime(list1) + " milliseceonds");
        System.out.println("Remove element time for array list is " + getRemoveTime(list1) + " milliseceonds");

        // Create an linked list, and test its performance
        Collection<Integer> list2 = new LinkedList<>(list);
        System.out.println("Member test time for linked list is " + getTestTime(list2) + " milliseceonds");
        System.out.println("Remove element time for linked list is " + getRemoveTime(list2) + " milliseceonds");
    }

    public static long getTestTime(Collection<Integer> c) {
        long startTime = System.currentTimeMillis();

        // Test if a number is in the collection
        for(int i = 0; i < N; i++)
            c.contains((int)(Math.random() * 2 * N));

        return System.currentTimeMillis() - startTime;
    }

    public static long getRemoveTime(Collection<Integer> c) {
        long startTime = System.currentTimeMillis();

        for(int i = 0; i < N; i++)
            c.remove(i);

        return System.currentTimeMillis() - startTime;
    }

}

Member test time for hash set is 31 milliseceonds
Remove element time for hash set is 25 milliseceonds
Member test time for linked hash set is 21 milliseceonds
Remove element time for linked hash set is 47 milliseceonds
Member test time for tree set is 33 milliseceonds
Remove element time for tree set is 52 milliseceonds
Member test time for array list is 3509 milliseceonds
Remove element time for array list is 1796 milliseceonds
Member test time for linked list is 7833 milliseceonds
Remove element time for linked list is 3867 milliseceonds

The program creates a list for numbers from 0 to N-1 (for N = 50000) (lines 9–11) and shuffles the list (line 12). From this list, the program creates a hash set (line 15), a linked hash set (line 20), a tree set (line 25), an array list (line 30), and a linked list (line 35). The program obtains the execution time for testing whether a number is in the hash set (line 16), linked hash set (line 21), tree set (line 26), array list (line 31), and linked list (line 36), and obtains the execution time for removing the elements from the hash set (line 17), linked hash set (line 22), tree set (line 27), array list (line 32), and linked list (line 37).

The getTestTime method invokes the contains method to test whether a number is in the container (line 45) and the getRemoveTime method invokes the remove method to remove an element from the container (line 54).

As these runtimes illustrate, sets are much more efficient than lists for testing whether an element is in a set or a list. Therefore, the No-Fly list should be implemented using a set instead of a list, because it is much faster to test whether an element is in a set than in a list.