La forma más rápida de comprobar si una Lista contiene una cadena única

En general, un HashSet le dará un mejor rendimiento, ya que no tiene que mirar a través de cada elemento y comparar, como lo hace un ArrayList, pero normalmente compara a lo sumo unos pocos elementos, donde los hashcodes son iguales.

Sin embargo, para cadenas 1M, el rendimiento del HashSet puede no ser óptimo. Muchos errores de caché ralentizarán la búsqueda en el conjunto. Si todas las cadenas son igualmente probables, entonces esto es inevitable. Sin embargo, si algunas cadenas se solicitan con más frecuencia que otras, a continuación, puede colocar las cadenas comunes en un pequeño HashSet, y comprobar que primero, antes de comprobar el conjunto más grande. El pequeño hashset debe ser dimensionado para caber en caché (por ejemplo, unos pocos cientos de K como máximo). Las visitas al hashset pequeño serán muy rápidas, mientras que las visitas al hashset más grande procederán a una velocidad limitada por el ancho de banda de la memoria.

Antes de ir más lejos, por favor considere esto: ¿Por qué está preocupado por el rendimiento? ¿Con qué frecuencia se llama este cheque?

En cuanto a las posibles soluciones:

• Si la lista ya está ordenada, entonces puede usar java.util.Collections.binarySearch que ofrece las mismas características de rendimiento que un java.util.TreeSet.

• De lo contrario, puede usar un java.util.HashSet que como una característica de rendimiento de O(1). Tenga en cuenta que calcular el código hash para una cadena que aún no tiene uno calculado es un O (m) operación con m = string.length(). También tenga en cuenta que los hashtables solo funcionan bien hasta que alcanzan un factor de carga dado, es decir, los hashtables usarán más memoria que las listas simples. El factor de carga predeterminado utilizado por el HashSet es .75, lo que significa que internamente un HashSet para objetos 1e6 usará una matriz con entradas 1.3e6.

• Si el HashSet no funciona para usted (por ejemplo, porque hay muchas colisiones de hash, porque la memoria está apretada o porque hay muchas inserciones), considere usar un Trie . La búsqueda en un Trie tiene una complejidad en el peor de los casos de O(m) donde m=string.length(). Un Trie también tiene algunos beneficios adicionales que podrían ser útiles para usted: por ejemplo, puede darle el ajuste más cercano para una cadena de búsqueda. Pero tenga en cuenta que el mejor código es no código, así que solo ruede su propia implementación de Trie si los beneficios superan los costos.

• Considere usar una base de datos si desea consultas más complejas, por ejemplo, coincidencia para una subcadena o un expresion.

Usaría un Set, en la mayoría de los casos HashSet está bien.

Con un número tan grande de Cadenas, inmediatamente pienso en un Trie. Funciona mejor con un conjunto más limitado de caracteres (como letras) y/o cuando el inicio de muchas cadenas se superponen.

Después de ejecutar el ejercicio aquí están mis resultados.

private static final int TEST_CYCLES = 4000;
private static final long RAND_ELEMENT_COUNT = 1000000l;
private static final int RAND_STR_LEN = 20;
//Mean time
/*
Array list:18.55425
Array list not contains:17.113
Hash set:5.0E-4
Hash set not contains:7.5E-4
*/

Creo que los números hablan por sí mismos. El tiempo de búsqueda del conjunto de hash es way, wayyyy más rápido.

Si tiene una cantidad tan grande de cadenas, la mejor oportunidad para usted es usar una base de datos. Busca MySQL.

Tal vez esto no es necesario para su caso, pero creo que es útil saber que hay algunos algoritmos probabilísticos espacio-eficientes. Por ejemplo Bloom filter.

No solo para String, puede usar Set para cualquier caso que necesite elementos únicos.

Si el tipo de elementos es primitivo o wrapper, puede que no le importe. Pero si es una clase, debe anular dos métodos:

1. hashCode ()
2. es igual a ()

A veces desea verificar si un objeto está en la lista/conjunto y al mismo tiempo desea que la lista/conjunto esté ordenada. Si también está buscando recuperar objetos fácilmente sin usar una enumeración o un iterador, puede considerar usar ArrayList<String> y HashMap<String, Integer>. La lista está respaldada por el mapa.

Ejemplo de un trabajo que hice recientemente:

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);
    }

    ...

En este caso, el parámetro K sería un String para usted. El mapa (childrenToMapList) almacena Strings insertado en la lista (children) como la clave, y los valores del mapa son la posición del índice en la lista.

La razón de la lista y el mapa es para que pueda recuperar los valores indexados de la lista, sin tener que hacer una iteración sobre un HashSet<String>.