HashSet vs ArrayList contains performance

The set will give much better performance (O(n) vs O(n^2) for the list), and that's normal because set membership (the contains operation) is the very purpose of a set.

Contains for a HashSet is O(1) compared to O(n) for a list, therefore you should never use a list if you often need to run contains.

The ArrayList uses an array for storing the data. The ArrayList.contains will be of O(n) complexity. So essentially searching in array again and again will have O(n^2) complexity.

While HashSet uses hashing mechanism for storing the elements into their respective buckets. The operation of HashSet will be faster for long list of values. It will reach the element in O(1).

I've made a test so please check the result:

For SAME STRING items in a HashSet, TreeSet, ArrayList and LinkedList, here are the results for

1. 50.000 UUIDs
   • SEARCHED ITEM : e608c7d5-c861-4603-9134-8c636a05a42b (index 25.000)
   • hashSet.contains(item) ? TRUE 0 ms
   • treeSet.contains(item) ? TRUE 0 ms
   • arrayList.contains(item) ? TRUE 2 ms
   • linkedList.contains(item) ? TRUE 3 ms
2. 5.000.000 UUIDs
   • SEARCHED ITEM : 61fb2592-3186-4256-a084-6c96f9322a86 (index 25.000)
   • hashSet.contains(item) ? TRUE 0 ms
   • treeSet.contains(item) ? TRUE 0 ms
   • arrayList.contains(item) ? TRUE 1 ms
   • linkedList.contains(item) ? TRUE 2 ms
3. 5.000.000 UUIDs
   • SEARCHED ITEM : db568900-c874-46ba-9b44-0e1916420120 (index 2.500.000)
   • hashSet.contains(item) ? TRUE 0 ms
   • treeSet.contains(item) ? TRUE 0 ms
   • arrayList.contains(item) ? TRUE 33 ms
   • linkedList.contains(item) ? TRUE 65 ms

Based on above results, there is NOT a BIG difference of using array list vs set. Perhaps you can try to modify this code and replace the String with your Object and see the differences then...

    public static void main(String[] args) {        Set<String> hashSet = new HashSet<>();        Set<String> treeSet = new TreeSet<>();        List<String> arrayList = new ArrayList<>();        List<String> linkedList = new LinkedList<>();        List<String> base = new ArrayList<>();        for(int i = 0; i<5000000; i++){            if(i%100000==0) System.out.print(".");            base.add(UUID.randomUUID().toString());        }        System.out.println("\nBase size : " + base.size());        String item = base.get(25000);        System.out.println("SEARCHED ITEM : " + item);        hashSet.addAll(base);        treeSet.addAll(base);        arrayList.addAll(base);        linkedList.addAll(base);        long ms = System.currentTimeMillis();        System.out.println("hashSet.contains(item) ? " + (hashSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");        System.out.println("treeSet.contains(item) ? " + (treeSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");        System.out.println("arrayList.contains(item) ? " + (arrayList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");        System.out.println("linkedList.contains(item) ? " + (linkedList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");    }