Efficient way to implement a String Array "is in" method using Java

Question

I have a requirement to present highly structured information picked from a highly un-structured web service. In order to display the info correctly, I have to do a lot of String matches and duplicate removals to ensure I'm picking the right combination of elements.

One of my challenges involves determining if a String is in an Array of Strings.

My dream is to do "searchString.isIn(stringArray);" but I realize the String class doesn't provide for that.

Is there a more efficient way of doing this beyond this stub?:

private boolean isIn(String searchString, String[] searchArray)
{
  for(String singleString : searchArray)
  {
    if (singleString.equals(searchString)
      return true;
  }

  return false;
}

Thanks!

http://stackoverflow.com/questions/1128723/in-java-how-can-i-test-if-an-array-contains-a-certain-value — Paolo Falabella, Feb 24 '11 at 16:40
unless you change the data structure (i.e. use a HashSet or similar), what you've written is pretty optimal. However on some JVMs you might get a very very slight speed advantage with searchString.equals(singleString)... this can (in theory) enable the compiler to eliminate a null check. — mikera, Feb 24 '11 at 16:50
Thanks. My team and I have been actively lobbying for a more structured version of the web service. When that happens, all of this String searching excitement will be wiped away. — IVR Avenger, Feb 24 '11 at 17:04

Zach L · Accepted Answer · 2011-02-24T16:43:23.070

You may want to look into HashMap or HashSet, both of which give constant time retrieval, and it's as easy as going:

hashSet.contains(searchString)

Additionally, HashSet (and HashMap for its keys) prevents duplicate elements.

If you need to keep them in order of insertion, you can look into their Linked counterparts, and if you need to keep them sorted, TreeSet and TreeMap can help (note, however, that the TreeSet and TreeMap do not provide constant time retrieval).

score 3 · Answer 2 · answered Feb 24 '11 at 16:40

3

Everybody else seems to be viewing this question in a broader scope (which is certainly valid). I am only answering this bit:

One of my challenges involves determining if a String is in an Array of Strings.

That's simple:

return Arrays.asList(arr).contains(str)

Reference:

Arrays.asList(array)

answered Feb 24 '11 at 16:40

Sean Patrick Floyd

292,901
67
465
588

I actually used this solution, as the lists in question won't ever be larger than five items. However, I marked Zach's answer as "correct", as it hit my efficiency question. +1, though! – IVR Avenger Feb 28 '11 at 15:11

score 0 · Answer 3 · answered Feb 24 '11 at 16:40

0

If you are doing this a lot, you can initially sort the array and do a binary search for your strings.

answered Feb 24 '11 at 16:40

Jeremy

22,188
4
68
81

reef · Answer 4 · 2011-02-24T16:47:48.547

As explained before you can use a Set (see http://download.oracle.com/javase/1.5.0/docs/api/java/util/Set.html and specially the boolean contains(Object o) method) for that purpose. Here is a quick 'n dirty example that demonstrates this:

String[] a = {"a", "2"};
Set<String> hashSet = new HashSet<String>();
Collections.addAll(hashSet, a);
System.out.println(hashSet.contains("a"));  // Returns true
System.out.println(hashSet.contains("2"));  // Returns true
System.out.println(hashSet.contains("e"));  // Returns false

Hope this helps ;)

score 0 · Answer 5 · answered Feb 24 '11 at 16:47

As mentioned a HashMap or HashSet can provide reasonable performance above what you've mentioned. It depends greatly on how well distributed your hash algorithm is and how many buckets are in the Map.

You could also keep a sorted list and perform a binary search on that list which could perform slightly better, though you pay the cost of sorting. If it's a one time sort, then that's not a big deal. If the list is constantly changing, you may pay a larger cost.

Lastly, you could consider a Trie structure. I think this would be the fastest way to search, but that's a gut reaction. I don't have the numbers to support that.

score 0 · Answer 6 · answered Feb 24 '11 at 16:56

As Zach has pointed out , you can use hashset to prevent duplicate, and use contains method to search for a string , which returns true when a match is found.You also need to override equals in ur class.

public boolean equals(Object other) { return other != null && other instanceof L && this.l == ((L)other).l;

score 0 · Answer 7 · answered Feb 24 '11 at 17:39

If the search space (your collection of strings) is limited than I agree with the answers already posted. If, however, you have a large collection of strings and need to perform a sufficient number of searches on it (to outweigh the setup overhead), you might also consider encoding the search strings in a trie data structure. Again this would only be advantageous if there are enough strings and you search enough times to justify the setup overhead.

Efficient way to implement a String Array "is in" method using Java

7 Answers7