Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the time and space complexity of method retainAll when used on HashSets in Java?

For example in the code below:

public int commonTwo(String[] a, String[] b)
{
    Set common = new HashSet<String>(Arrays.asList(a));
    common.retainAll(new HashSet<String>(Arrays.asList(b)));
    return common.size();
} 
like image 914
Anirudh Avatar asked Jul 15 '14 09:07

Anirudh


People also ask

What is retainAll () in Java?

The retainAll() method of ArrayList is used to remove all the array list's elements that are not contained in the specified collection or retains all matching elements in the current ArrayList instance that match all elements from the Collection list passed as a parameter to the method.

What is the time complexity of HashSet in Java?

For HashSet, LinkedHashSet, and EnumSet, the add(), remove() and contains() operations cost constant O(1) time thanks to the internal HashMap implementation. Likewise, the TreeSet has O(log(n)) time complexity for the operations listed in the previous group.

What is the time complexity to get an item from a specific index in an ArrayList?

Note: Time Complexity: ArrayList is one of the List implementations built a top an array. Hence, get(index) is always a constant time O(1) operation. Example: Java.

What is time complexity of set in Java?

the elements in a set are sorted, but the add, remove, and contains methods has time complexity of o(log (n)).

How do I find the length of a HashSet?

util. HashSet. size() method is used to get the size of the HashSet or the number of elements present in the HashSet.

What does HashSet retain all do?

retainAll() method is present in the HashSet class inside the java. util package. It is used to retain all the elements in a HashSet that are specified in the input collection.


2 Answers

Lets take a peruse at the code. The method retainAll is inherited from AbstractCollection and (at least in OpenJDK) looks like this:

public boolean retainAll(Collection<?> c) {
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

There is one big this to note here, we loop over this.iterator() and call c.contains. So the time complexity is n calls to c.contains where n = this.size() and at most n calls to it.remove().

This important thing is that the contains method is called on the other Collection and so the complexity is dependant upon the complexity of the other Collection contains.

So, whilst:

Set<String> common = new HashSet<>(Arrays.asList(a));
common.retainAll(new HashSet<>(Arrays.asList(b)));

Would be O(a.length), as HashSet.contains and HashSet.remove are both O(1) (amortized).

If you were to call

common.retainAll(Arrays.asList(b));

Then due to the O(n) contains on Arrays.ArrayList this would become O(a.length * b.length) - i.e. by spending O(n) copying the array to a HashSet you actually make the call to retainAll much faster.

As far as space complexity goes, no additional space (beyond the Iterator) is required by retainAll, but your invocation is actually quite expensive space-wise as you allocate two new HashSet implementations which are actually fully fledged HashMap.

Two further things can be noted:

  1. There is no reason to allocate a HashSet from the elements in a - a cheaper collection that also has O(1) remove from the middle such as an LinkedList can be used. (cheaper in memory and also build time - a hash table is not built)
  2. Your modifications are being lost as you create new collection instances and only return b.size().
like image 132
Boris the Spider Avatar answered Sep 17 '22 23:09

Boris the Spider


The implementation can be found in the java.util.AbstractCollection class. The way it is implemented looks like this:

public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

So it will iterate everything in your common set and check if the collection that was passed as a parameter contains this element.

In your case both are HashSets, thus it will be O(n), as contains should be O(1) amortized and iterating over your common set is O(n).

One improvement you can make, is simply not copy a into a new HashSet, because it will be iterated anyway you can keep a list.

like image 34
Thomas Jungblut Avatar answered Sep 20 '22 23:09

Thomas Jungblut