Set

Properties

• Collection of Objects, but it does not contain duplicate value (only one 'null' value you can insert)

• Unlike List, Set is not an Ordered collection, means objects inside set does not follow the insertion order.

• Unlike List, Set cannot be accessed via index.

Internal Implementation - Map

• Which Data structure is used in Stack internally (as it does not allow duplicate value)? (Map)

• As order is not gurantee, then what if we want to sort the Set Collection? (TreeSet)

Internally Set is implemented using map.

Methods

All methods declared in the Collections interface are generally only available in Set.

add(E element)

Returns true after inserting an element into the set only if the element is not already present. If the same value is already present, then it returns false.

addAll(Collection c)

performs UNION of 2 Set collection .

set1 = [12, 11, 33, 4]

set2 = [11, 9, 88, 10, 5, 12]

set1 + set2 = [12, 11, 33, 4, 9, 88, 10, 5]

remove(E element)

Remove element from the set.

removeAll(Collection c)

performs DIFFERENCE of 2 Set Collection. Delete the values from set which are present in another set.

set1 = [12, 11, 33, 4]

set2 = [11, 9, 88, 10, 5, 12]

set1 - set2 = [33, 4]

retainAll(Collection c)

performs Intersection of 2 Set collection. Returns element which are present in both

set1 = [12,11,33,4]

set2 = [11, 9, 88, 10, 5, 12]

set1 intersect set2 = [12, 11]

HashSet

• Data structure used: HashMap

  HashMap<E, Object> map = new HashMap<>();

• During Add method invocation, it stored the element in the key part and in value it stores the dummy object:

  map.put(element, new Object())

• What if 2 values get the same hash value? How it's handled? What is load factor? (Refere HashMap)

• No guarantee that the order will remain constant.

• HashSet is not threadSafe. newkeySet method present in ConcurrentHashMap class is used to create threadSafe Set.

public class Main {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>();
        set1.add(12);
        set1.add(11);
        set1.add(33);
        set1.add(4);

        Set<Integer> set2 = new HashSet<>();
        set2.add(11);
        set2.add(9);
        set2.add(88);
        set2.add(10);
        set2.add(5);
        set2.add(12);

        //UNION of 2 sets
        set1.addAll(set2);
        System.out.println("after union");
        set1.forEach(val -> System.out.println(val));

        //Intersection of 2 sets
        set1 = new HashSet<>();
        set1.add(12);
        set1.add(11);
        set1.add(33);
        set1.add(4);

        set2 = new HashSet<>();
        set2.add(11);
        set2.add(9);
        set2.add(88);
        set2.add(10);
        set2.add(5);
        set2.add(12);

        set1.retainAll(set2);
        System.out.println("after intersection:");
        set1.forEach(val -> System.out.println(val));

        //Difference of 2 sets
        set1 = new HashSet<>();
        set1.add(12);
        set1.add(11);
        set1.add(33);
        set1.add(4);

        set2 = new HashSet<>();
        set2.add(11);
        set2.add(9);
        set2.add(88);
        set2.add(10);
        set2.add(5);
        set2.add(12);

        set1.removeAll(set2);
        System.out.println("after Difference");
        set1.forEach(val-> System.out.println(val));

    }
}

after union
33
4
5
88
9
10
11
12
after intersection:
11
12
after Difference
33
4

Thread Safe Version

• Thread Safe - No

• Maintains Insertion Order - No

• Null Elements allowed - Yes (only one)

• Duplicate elements allowed - No

HashSet is not Thread Safe

public class Main {
    public static void main(String[] args) {

        Set<Integer> set1 = new HashSet<>();
        set1.add(1);
        set1.add(2);

        Iterator<Integer> iterator = set1.iterator();

        while (iterator.hasNext()){
            int val = iterator.next();
            if (val==1){
                //iterator.remove(); // we can remove
                set1.add(9); //we should be able to add in the set as its thread safe
            }
        }
        set1.forEach(val-> System.out.println(val));
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1597)
    at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1620)
    at learn.collection.Main.main(Main.java:19)

Example: Thread Safe

public class Main {
    public static void main(String[] args) {

        ConcurrentHashMap concurrentHashMap = new ConcurrentHashMap();
        Set<Integer> threadSafeSet = concurrentHashMap.newKeySet();
        threadSafeSet.add(1);
        threadSafeSet.add(2);

        Iterator<Integer> iterator = threadSafeSet.iterator();

        while (iterator.hasNext()){
            int val = iterator.next();
            if (val==1){
                //iterator.remove(); // we can remove
                threadSafeSet.add(9); //we should be able to add in the set as its thread safe
            }
        }
        threadSafeSet.forEach(val-> System.out.println(val));
    }
}
/*
1
2
9
*/

Time Complexity

add: O(1)

remove: Amortized O(1)

contains: Amortized O(1)

LinkedHashSet

• Internally it uses: LinkedHashMap

• Maintains the insertion Order of the element

• Its not thread safe

• Set<Integer> set = Collections.synchronizedMap(new LinkedHashSet<>());

public class Main {
    public static void main(String[] args) {

        Set<Integer> set1 = new LinkedHashSet<>();
        set1.add(1);
        set1.add(77);
        set1.add(82);
        set1.add(63);
        set1.add(5);

        Iterator<Integer> iterator = set1.iterator();

        while (iterator.hasNext()){
            int val = iterator.next();
            System.out.println(val);
        }

    }
}
/*
1
77
82
63
5
*/

TreeSet

• Internally it uses: TreeMap

• It cannot store null value

public class Main {
    public static void main(String[] args) {

        Set<Integer> set1 = new TreeSet<>();
        set1.add(1);
        set1.add(77);
        set1.add(82);
        set1.add(63);
        set1.add(5);

        Iterator<Integer> iterator = set1.iterator();

        while (iterator.hasNext()){
            int val = iterator.next();
            System.out.println(val);
        }

    }
}
/*
1
5
63
77
82
*/