CODEWITHSUNDEEP
javaarraysstringsearchhashset
7oso
7oso

Reputation: 283

Searching a HashSet for any element in a string array

I have a HashSet of strings and an array of strings. I want to find out if any of the elements in the array exists in the HashSet. I have the following code that work, but I feel that it could be done faster. 

public static boolean check(HashSet<String> group, String elements[]){
    for(int i = 0; i < elements.length; i++){
        if(group.contains(elements[i]))
            return true;
    }
    return false;
}

Thanks.

Upvotes: 2

Views: 6458

Answers (5)

Mike Samuel
Mike Samuel

Reputation: 120526

If you know that the set is a sorted set, and that the array is sorted, you can get the interval set from the start to the end to possibly do better than O(|array| * access-time(set)), and which especially allows for some better than O(|array|) negative results, but if you're hashing you can't.

Upvotes: 0

Stewart Murrie
Stewart Murrie

Reputation: 1319

As others have said, the slowest part of the algorithm is iterating over every element of the array. The only way you could make it faster would be if you knew some information about the contents of the array beforehand which allowed you to skip over certain elements, like if the array was sorted and had duplicates in known positions or something. If the input is essentially random, then there's not a lot you can do.

Upvotes: 0

卢声远 Shengyuan Lu
卢声远 Shengyuan Lu

Reputation: 32014

It's O(n) in this case (array is used), it cannot be faster.

If you just want to make the code cleaner:

 return !Collections.disjoint(group, Arrays.asList(elements));

Upvotes: 3

Stephen C
Stephen C

Reputation: 719229

... but I feel that it could be done faster.

I don't think there is a faster way. Your code is O(N) on average, where N is the number of strings in the array. I don't think that you can improve on that.

Upvotes: 1

Chad La Guardia
Chad La Guardia

Reputation: 5164

That seems somewhat reasonable. HashSet has an O(1) (usually) contains() since it simply has to hash the string you give it to find an index, and there is either something there or there isn't.

If you need to check each element in your array, there simply isn't any faster way to do it (sequentially, of course).

Upvotes: 2

Related Questions