CODEWITHSUNDEEP
javacollectionslookup
user1411135
user1411135

Reputation: 31

Looking up if a value is present in a collection (small collection, several checks per second)

I need to implement a very efficient method of checking if a certain key (long value) is present in a small collection of items (less than 100, usually around 10) in java.

This check must be as efficient as possible, as it is going to be made several times per second (more than 1000, I'm treating an Multicast feed and i want to discard messages that i don't need to treat).

The items that need to be checked is going to vary almost nothing during the application life cycle, and it can be expensive in terms of performance.

Thanks

Thanks for all the prompt replies. My concern is that my long keys might be very concentrated in a small range of the long, and I'm worried about it. If you guys think that it wont be an issue, I'll give it a try.

Upvotes: 1

Views: 86

Answers (2)

Paul Bellora
Paul Bellora

Reputation: 55223

If efficiency takes precedence over versatility, you might consider using Trove's TLongHashSet:

An open addressed set implementation for long primitives.

This would give you O(1) and avoid autoboxing entirely. But this might be an extreme choice for such a small collection.

Upvotes: 0

Bohemian
Bohemian

Reputation: 425188

Use a HashSet<Long> - it will take nanoseconds (literally) for contains() to return.

Code something like this:

private static Set<Long> keys = new HashSet<Long>();
// populate keys

if (keys.contains(requestKey)) { // this call is super fast!
    // ignore request
}

Edited:

Don't worry about your longs being "close" together. The hashCode() of Long is sufficiently "scattered" that for all practical purposes no pattern to it - that is, Longs that are "close" do not have hash codes that are "close".

Upvotes: 3

Related Questions