Manejo de listas de cadenas grandes en java

Question

Tengo una tarea, donde tengo que pasar por varios miles de líneas de cadenas y verificar si cada una de ellas es única. Todas las líneas en sí no pueden ser acomodadas dentro de la memoria RAM de la PC. Además, es probable que la cantidad de líneas sea mayor que Integer.MAX_VALUE.

Supongo que la mejor manera de manejar esta cantidad de datos es poner los códigos hash de cada una de las cadenas en algún tipo de HashTable.

lo tanto, aquí están mis preguntas:

1. ¿Qué debo usar en lugar de String.hashCode()? (el valor de retorno es int, pero probablemente necesite mucho tiempo)
2. ¿Cuál es la forma/marco más rápido para trabajar con listas de este tamaño? Lo que más necesito es la capacidad de verificar rápidamente si la lista contiene un elemento o no

Answer 1

Está pensando demasiado sobre el problema, esto se puede hacer de manera muy simple con una tabla MySQL que guarda datos en el disco en lugar de almacenar todo en la memoria. Esa gran cantidad de datos nunca fue pensada para ser manejada eficientemente por una aplicación independiente.

CREATE TABLE TONS_OF_STRINGS 
(
    unique_string varchar(255) NOT NULL, 
    UNIQUE (unique_string) 
) 

Sólo bucle a través de los valores (suponiendo una lista separada por comas aquí) y tratar de insertar cada token. Cada token fallido es un duplicado.

public static void main(args) { 
    Connection con = DriverManager.getConnection("jdbc:mysql://localhost/database","username","password"); 
    FileReader file = new FileReader("SomeGiantFile.csv"); 
    Scanner scan = new Scanner(file); 
    scan.useDelimiter(","); 
    String token; 
    while (scan.hasNext()) { 
    token = scan.next(); 
    try { 
     PreparedStatement ps = con.prepareStatement("Insert into TONS_OF_STRING (UNIQUE_STRING) values (?)"); 
     ps.setString(1, token); 
     ps.executeUpdate(); 
    } catch (SQLException e) { 
     System.out.println("Found duplicate: " + token); 
    } 
    } 
    con.close(); 
    System.out.println("Well that was easy, I'm all done!"); 
    return 0; 
} 

No se olvide de borrar la tabla cuando haya terminado, eso es una gran cantidad de datos.

Answer 2

No es suficiente almacenar simplemente hashcodes de 32 o 64 bits porque dos cadenas distintas (de unos pocos miles de millones) pueden tener fácilmente el mismo código hash Una vez que tiene dos cadenas con el mismo código hash, necesita comparar las cadenas reales para ver si son realmente iguales.

Aquí es la forma en que me resuelvo este problema:

1. leer el archivo/corriente de cuerdas:

   1. Lea cada línea

   2. Calcular el código hash para el línea

   3. Escriba el código hash y la cadena a un tempora ry archivo con un separador de campo adecuado en el medio

2. Utilice un programa de tipo externo decente para ordenar el archivo temporal utilizando el campo de código hash como la clave de ordenación principal y el campo de cadena como la clave de ordenación secundaria.

3. Lea el archivo temporal una línea a la vez. Si dos líneas sucesivas tienen el mismo campo de código hash y diferentes campos de cadena, entonces ha encontrado una cadena duplicada.

Nota: Este enfoque funcionará igual de bien con hashcodes de 32 o 64 bits.