HashSet vs ArrayList contains() performance for several small String collections

Question

This question is essentially an addendum to this one which already asks about Java's contains() performance, but my use case targets collections with a small number of String elements.

To make the problem more precise, there will be:

• Only java.lang.String elements in the collection (thus using String.equals(...) in the contains(...) calls).
• String have average length of 16.
• The average number of elements in a single collection is 7.
• The collection will face frequent contains(...) checks, occasional additions, and no removals.
• Ordering of Strings is not important at all.
• This code would run on a web server, and there would be a large number of such collection objects (~1000 per user request).

Which collection would be a better fit for this use-case, both memory-wise and time-wise?

Answer 1

Which collection would be a better fit for this use-case, both memory-wise?

A String[]. Cannot be more compact than that.

Of course, that's not really a Collection, but I took that in the loosest meaning possible.

For best lookup (contains) performance, make it sorted and use binary search.

... and time-wise?

Probably a HashSet, but you need to test performance of such small collections, because the O(log n) performance of e.g. binary search may actually be faster than the O(1) performance of a hash table lookup, when n is only 7.

For that small a value of n, the performance difference may be negligible, and memory footprint may be more important.

Deciding between memory footprint and runtime performance, only you can decide which is "a better fit". We can't decide that for you.