0

This is probably a simple question for you JAVA experts, but I'm relatively new, so I thought I'd ask. I need to test if string X exists in a set. I don't need any associated values or indices, and I don't need any order. I just need to know if it exists. I know that this could be implemented using a HashMap or ArrayList, but those seem overkill. What to do? Just a List? Or is there something even more basic that would serve the same purpose. What is the fastest way to test if some string X exists in a given set?

meesterguyperson
  • 1,726
  • 1
  • 20
  • 31
  • How big is the set? You can't be sure of the fastest solution without benchmarking it with realistic data. – DNA Feb 17 '12 at 22:14

6 Answers6

8

Sounds like you want a HashSet<String>:

Set<String> set = new HashSet<String>();
set.add("foo");
set.add("bar");

boolean no = set.contains("baz");
boolean yes = set.contains("foo");

There are other Set implementations available, of course, but HashSet is probably the most appropriate here.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
1

You don't have just ArrayList and HashMap, JDK comes with a good variety of classes, in which you can find also what you are looking for: sets.

One of them for example is HashSet, which has the functionality you are looking about..

Set<String> set = new HashSet<String>();

set.add("foo");
set.add("bar");

boolean b = set.contains("foo");
Jack
  • 131,802
  • 30
  • 241
  • 343
0
import java.util.Arrays;

...

if (Arrays.asList("foo", "bar", "baz").contains(myString)) {
    ...
}
gpeche
  • 21,974
  • 5
  • 38
  • 51
  • 1
    This won't be efficient, since it will be O(N) compared with an `HashSet` (constant O(1) ) or a `TreeSet` (I guess O(logn) if I remember correctly) – Jack Feb 17 '12 at 21:55
  • @Jack for very small sets (say, <5) it will be as efficient, and easier to write. Of course it is not a general solution, but the questioner thinks the general solution is "overkill" anyway. – gpeche Feb 17 '12 at 22:02
  • You are both right - but the OP needs to benchmark with an appropriate size of set! – DNA Feb 17 '12 at 22:16
0

I know that this could be implemented using a HashMap or ArrayList, but those seem overkill.

What exactly is "overkill" about using a builtin class that is designed to do exactly what you want, and do it very fast? Because that's what HashMap is. HashSet would be a bit more basic in its interface (not mapped values), but it's actually implements by having a HashMap with null values.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • Well, `HashMap` is designed to map keys to values, which is *more* than the OP wants (as he only needs "presence"). `HashSet`, on the other hand... – Jon Skeet Feb 17 '12 at 21:59
0

Several answers have suggested HashSet, and others have pointed out that simpler collections might be faster for small sets - you haven't said what size of set.

The size of the Strings is also relevant, because HashSet etc will use the hashcode of the String, which is computed from the entire contents of the String (and then cached). This might take a little time - but on the other hand it may have already been computed, depending on your code, so wouldn't incur an extra cost.

In some cases you may be able to rule out Strings from the set by their size, or by checking the first few characters - it depends on your data and your set of Strings. A data structure such as a Trie could be useful here - (but you wanted a simple solution).

If performance is critical, then you need to benchmark all the suggested solutions carefully under realistic conditions. See How do I write a correct micro-benchmark in Java?

If you really need a fast solution (is this actually critical for your application?) then you may need to tolerate 'overkill' !

Community
  • 1
  • 1
DNA
  • 42,007
  • 12
  • 107
  • 146
0

Don't use contains use Collections.binarySearch(List, Object)

Don't forget to sort before you use this method Collections.sort(List)

Ramu
  • 199
  • 2
  • 11