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

Question

Hi,

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).

Answer 1

Without benchmarking, contains should be faster or the same in all cases.

For 1 and 2, it doesn't need to call the iterator methods. It can loop internally. Both ArrayList and LinkedList implement contains in terms of indexOf

1. ArrayList - indexOf is a C-style for loop on the backing array.
2. LinkedList - indexOf walks the linked list in a C-style for loop.

For 3 and 4, you have to distinguish between containsKey and containsValue.

3. HashMap, containsKey is O(1). It works by hashing the key, getting the associated bucket, then walking the linked list. containsValue is O(n) and works by simply checking every value in every bucket in a nested for loop.

4. TreeMap, containsKey is O(log n). It checks whether it's in range, then searches the red-black tree. containsValue, which is O(n), uses an in-order walk of the tree.

Answer 2

EDITED:

With the new form of the question no longer including HashMap and TreeMap, my answer is entirely different. I now say no.

I'm sure that other people have answered this, but in both LinkedList and ArrayList, contains() just calls indexOf(), which iterates over the collection.

It's possible that there are tiny performance differences, both between LinkedList and ArrayList, and between contains and foreach, there aren't any big differences.

Answer 3

Hi, I think using contains is better because generally the library implementation is more efficient than manual implementation of the same. Check out if you can during object construction or afterwards pass a comparator method that you have written which takes care of your custom equals and hashcode implementation.

Thanks, Krishna

Answer 4

Traversing the container with foreach/iterator is always O(n) time. ArrayList/LinkedList search is O(n) as well.

HashMap.containsKey() is O(1) amortized time.

TreeMap.containsKey() is O(log n) time.

For both HashMap and TreeMap containsValue() is O(n), but there may be implementations optimized for containsValue() be as fast as containsKey().

Answer 5

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 :).

Answer 6

This makes no differency since contains(o) calls indexOf(o) which simply loops like this:

for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
       return i;

(Checked in ArrayList)