How can I find whether a collection does or does not contain Java?

Question

It seems to be a very common thing to have to tell whether some list or set contains at least one object matching a given condition, yet my prior searching and reading have never found a satisfactory best practice or design pattern to speak of. In the situations I am thinking of, merely using "contains" is not sufficient, as the test we want to perform is not strictly based on the equals method of the class in question.

Some things I have seen:


// for-each with break
private boolean doFoosHaveGoodQuality(List candidates) {
    boolean foundIt = false;
    for (Foo item: candidates) {
        if (<< item>>) {
            fountIt = true;
            break;
        }
    }
    return foundIt;
}   
// while-do with index counter
private boolean doFoosHaveGoodQuality(List candidates) {
    boolean foundIt = false;
    int index = 0;
    while(!fountIt && index < candidates>        Foo item = candidates.get(index++);
        if (<< item>>) {
            fountIt = true;
        }
    }
    return foundIt;
}

Both of these get the job done and quit as soon as a success is found, possibly saving some time if we are lucky enough to have the desired item early in the list. However, both require looping the entire list in order to get a false result

Another technique I've seen in some circumstances is that at the same time the original List is generated (i.e. retrieved from a database) to then simultaneously generate a Map. In this technique, FooKey is an additional (often inner) class holding only those attributes of a Foo that form the "desired quality" and overrides equals and hashcode methods based on that. When you need to determine if there exists a desired Foo, you make a new FooKey() instance with exactly that you want, then call hasKey() on the map. Extra effort up front, but quick and easy at the moment you need it.

I can't put a finger on it. Each idea works, yet each feels just a little hacky and inefficient.

Melvin Forbis · Accepted Answer

Algorithmically, the for-each and the while-with-indexing version implement linear search. This is okay for small collections or when you only do such a check very occasionally, but if it's an important building block of your program, you'd want a dedicated mapping structure which speeds up these queries by doing something fundamentally different from linear search to know if a collection does not contain java. Examples include binary search trees (where you need to define a consistent ordering) and hash tables (where you need to define a consistent hash function). For most predicates this is trivial, for others it would be some extra code (defining FooKey), and for others it is hard or completely impractical. This is a judgement call depending on the criteria by which you search.

When you've decided on linear search, there are several options to implement it (provided there isn't already a good implementation — if so, prefer that!). The for-each variant is quite general and IMHO elegant: It works with any iterable, it doesn't even have to be backed by a concrete collection (cf. streams in Java 8). The while loop with indexing, on the other hand, is very restricted: It's offensively slow for containers that can't do random access (e.g. linked lists), and it doesn't work at all for things that can't be indexed. I would never recommend this one. There are probably other variations, but they are even more specialised. If you implement linear search, implement it for iterables.

Another issue is how you supply the predicate. You could write essentially the same loop again and again with only the condition different. But this is error prone, verbose, and inefficient. There should be only one copy of this loop, with the condition being passed as parameter. If your language (version) can do this, use a first-class function/lambda. Otherwise, you could emulate it with an interface and anonymous classes. Once you do this, Maps lose some of their appeal: It's no longer a long loop versus map.get(whatIWant), it's list.find(whatIWant). Of course they still have a performance benefit for large collections.

Side note: The loops can be slightly simpler, for example I'd write the for-each loop as:

private boolean doFoosHaveGoodQuality(List candidates) {
    for (Foo item: candidates) {
        if (<< item>>) {
            return true;
        }
    }
    return false;
}

How can I find whether a collection does or does not contain Java?

About this question

Your answer

1 Answer

More Java discussions

Learn & Explore

Popular Tutorials

Java Interview Q&A

Latest Java Blogs

Want answers to more Java questions?

Stay in the loop — it’s free

You’re on the list!