Any big difference between using contains or loop through a list?

Performance wise, is there really a big difference between using:

ArrayList.contains(o) vs foreach|iterator
LinkedList.contains(o) vs foreach|iterator

Of course, for the foreach|iterator loops, I'll have to explicitly compare the methods and return true or false accordingly.

The object I'm comparing is an object where equals() and hashcode() are both properly overridden.

EDIT: Don't need to know about containsValue after all, sorry about that. And yes, I'm stupid... I realized how stupid my question was about containsKey vs foreach, nevermind about that, I don't know what I was thinking. I basically want to know about the ones above (edited out the others).

Edit Report

ArrayList.contains does

return indexOf(o) >= 0;

where

public int indexOf(Object o) {
if (o == null) {
    for (int i = 0; i < size; i++)
    if (elementData[i]==null)
        return i;
} else {
    for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
        return i;
}
return -1;
}

It's similar for LinkedList, only it uses .next() to iterate through the elements, so not much difference there.

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header.next; e != header; e = e.next) {
            if (e.element==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

HashMap.containKey uses the hash of the key to fetch all keys with that hash (which is fast) and then uses equals only on those keys, so there's an improvement there; but containsValue() goes through the values with a for.

TreeMap.containsKey seem to do an informed search using a comparator to find the Key faster, so still better; but containsValue still seems to go through the entire three until it finds a value.

Overall I think you should use the methods, since they're easier to write than doing a loop every time :).

answered 2010-05-21T22:10:26.910

Any big difference between using contains or loop through a list?

1 Answer

Your Answer