Which instance method is called when super type method calls method present in both super type and subtype

Question

Pardon me if I'm missing some core Java here.

I was searching through HashSet's javadocs for the specification of it's implementation of Collection.containsAll() and it apparently inherits the implementation by AbstractCollection which according to the JDK 8 source code documentation goes like this:

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

My question stems from the fact that while HashSet does not override containsAll() it does however override contains():

public boolean contains(Object o) {
    return map.containsKey(o);
}

AbstractCollection likewise:

public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

My understanding has been that when an instance member call is not explicitly specified within the instance, the JVM implicitly replaces it with this.instanceMemberCall() which in this case would translate to AbstractCollection's contains() being called. But then again I read here that the time complexity for HashMap/HashSet's containsAll() would be O(n) suggesting that HashSet's contains() (O(1)) is called. Would appreciate some clarity as to what the actual semantics behind this are.

Answer 1

No, this is simply polymorphism. Whenever a method is invoked on an object, the true type of that object matters, nothing else.

Meaning: it doesn't matter that foo() is implemented in Base. When foo()calls bar() with bar() being overridden in Child. When you have a Child object, then it will always be the Child bar() version that gets called.

In your example, this isn't AbstractSet, it is HashSet!

Or again in other words: it doesn't matter "where" a method is invoked. What matters is the type of object it is invoked on. And as said, your object is of type HashSet!

Answer 2

This is an interesting question. HashSet in Java is backed by HashMap. The containsAll() method is just looping over contains() in this case HashSet's contains method. That's because HashSet overrides the contains and delegates.

Because HashSet is backed by the HashMap actual invocation is containsKey(Object key).

The HashMap's containsKey(Object key) is mostly gives you O(1) complexity. However, the containsAll() does loop over n elements. Your worse case complexity become O(n).

The reason I said it's mostly, because performance of a HashMap relies on hashing.