Gestione di elenchi di stringhe di grandi dimensioni in java

Question

Ho un compito, in cui devo passare attraverso diversi miliardi di stringhe e controllare, se ognuno di questi è unico. Tutte le linee stesse non possono essere ospitate all'interno della memoria RAM del PC. Inoltre, è probabile che il numero di righe sia maggiore di Integer.MAX_VALUE.

Suppongo che il modo migliore per gestire questa quantità di dati sia di inserire codici hash di ciascuna stringa in una sorta di HashTable.

Così, qui sono le mie domande:

1. Cosa devo usare al posto di String.hashCode()? (il valore restituito è int, ma probabilmente ho bisogno di molto tempo)
2. Qual è il modo/framework più veloce per lavorare con elenchi di queste dimensioni? Quello di cui ho maggiormente bisogno è la possibilità di controllare rapidamente se l'elenco contiene un elemento oppure no

Answer 1

Stai pensando troppo al problema, tutto questo può essere fatto molto semplicemente con una tabella MySQL che salva i dati sul disco invece di tenere tutto in memoria. Non è stato mai pensato che molti dati fossero gestiti efficientemente da un'applicazione standalone.

Basta scorrere i valori (presupponendo un elenco separato da virgola qui) e provare a inserire ciascun token. Ogni token non riuscito è un duplicato.

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

Non dimenticare di cancellare la tabella quando hai finito però, questo è un sacco di dati.

Answer 2

Non è sufficiente archiviare semplicemente hash a 32 o 64 bit perché due stringhe distinte (su qualche miliardo) possono facilmente avere lo stesso codice hash. Una volta che hai due stringhe con lo stesso codice hash, devi confrontare le stringhe reali per vedere se sono effettivamente uguali.

Ecco il modo in cui mi piacerebbe risolvere questo problema:

1. leggere il file/flusso di stringhe:

   1. Leggere ogni riga

   2. calcolare il codice hash per la line

   3. Scrivi il codice hash e la stringa in un tempora lima ry con un separatore di campo adatto tra

2. Utilizzare un programma di ordinamento esterno discreto per ordinare il file temporaneo utilizzando il campo hashcode come criterio di ordinamento primaria e il campo stringa come chiave di ordinamento secondaria.

3. Leggere il file temporaneo una riga alla volta. Se due righe successive hanno lo stesso campo hashcode e campi stringa diversi, hai trovato una stringa duplicata.

Nota: questo approccio funziona egregiamente con codici hash a 32 o 64 bit.