Fastest way to check if a List contains a

Question

Basically I have about 1,000,000 strings, for each request I have to check if a String belongs to the list or not.

I'm worried about the performance, so what's the best method? ArrayList? Hash?

Answer 1

Sometimes you want to check if an object is in the list/set and at the same time you want the list/set to be ordered. If you are looking to also retrieve objects easily without using an enumeration or iterator, you may consider using both an ArrayList<String> and HashMap<String, Integer>. The list is backed by the map.

Example from some work I recently did:

public class NodeKey<K> implements Serializable, Cloneable{
private static final long serialVersionUID = -634779076519943311L;

private NodeKey<K> parent;
private List<K> children = new ArrayList<K>();
private Map<K, Integer> childrenToListMap = new HashMap<K, Integer>();

public NodeKey() {}

public NodeKey(Collection<? extends K> c){
    List<K> childHierarchy = new ArrayList<K>(c);
    K childLevel0 = childHierarchy.remove(0);

    if(!childrenToListMap.containsKey(childLevel0)){
        children.add(childLevel0);
        childrenToListMap.put(childLevel0, children.size()-1);
    }

    ...

In this case, parameter K would be a String for you. The map (childrenToMapList) stores Strings inserted into the list (children) as the key, and the map values are the index position in the list.

The reason for the list and the map is so that you can retrieve indexed values of the list, without having to do an iteration over a HashSet<String>.

Answer 2

Your best bet is to use a HashSet and check if a string exists in the set via the contains() method. HashSets are built for fast access via the use of Object methods hashCode() and equals(). The Javadoc for HashSet states:

This class offers constant time performance for the basic operations (add, remove, contains and size),

HashSet stores objects in hash buckets which is to say that the value returned by the hashCode method will determine which bucket an object is stored in. This way, the amount of equality checks the HashSet has to perform via the equals() method is reduced to just the other Objects in the same hash bucket.

To use HashSets and HashMaps effectively, you must conform to the equals and hashCode contract outlined in the javadoc. In the case of java.lang.String these methods have already been implemented to do this.

Answer 3

If you are having such a large amount of strings, the best opportunity for you is to use a database. Look for MySQL.

Answer 4

With such a huge number of Strings, I immediately think of a Trie. It works better with a more limited set of characters (such as letters) and/or when the start of many string overlap.

Answer 5

Not only for String, you can use Set for any case you need unique items.

If the type of items is primitive or wrapper, you may not care. But if it is a class, you must override two methods:

1. hashCode()
2. equals()

Answer 6

I'd use a Set, in most cases HashSet is fine.