Ho un elenco di stringa univoca . Non voglio distruggere questa stringa ne ho bisogno. Devo solo scoprire che una determinata stringa S esiste in questo elenco univoco. Quale sarebbe la migliore struttura dati per questo scopo.
Potresti utilizzare un Set .
Un Set è una struttura di dati che non può contenere oggetti duplicati, quindi puoi semplicemente riversare tutte le tue stringhe e automaticamente filtra i duplicati.
Per verificare esplicitamente se una determinata stringa è già presente nel set, puoi chiamare un metodo contains() .
Un HashSet di stringhe ti offre buone prestazioni di ricerca, ma è adatto solo se le stringhe sono garantite come uniche.
Dipende da quante stringhe uniche hai. Ci sono almeno tre modi per memorizzare le tue stringhe.
Elenco (vettore / array): mantiene un elenco di stringhe ordinato o non ordinato. È quindi possibile eseguire la scansione dell'elenco per scoprire se la stringa esiste già. L'aggiunta di una nuova stringa è un'appendice o un inserto (a seconda se si mantiene l'elenco ordinato).
Hash (Map / Associative Array) - Memorizza le stringhe come chiavi in un hash / mappa, e puoi contare le occorrenze di ogni stringa come i valori contenuti nel hash heys.
Trie - Una struttura ad albero N-ary in cui ogni nodo dell'albero ha una lista / matrice di bambini, in cui ogni bambino è indicizzato da una sottostringa di caratteri diversa da tutti gli altri bambini. Le foglie rappresentano le parole terminali (stringhe univoche). L'albero ha una profondità al massimo uguale alla lunghezza della corda più lunga.
Inoltre, un semplice ibrido di hash e liste usate nelle tabelle dei simboli (molto tempo fa), avrebbe hash (primo carattere, ultimo carattere) in elenchi più piccoli di stringhe. Fornisce un accesso ragionevolmente rapido, un numero limitato di confronti nella lista e abbastanza facile da implementare (una tecnica utilizzata nelle tabelle dei simboli molto tempo fa).
Un'altra possibilità: se hai un minor numero di stringhe da codificare, una piccola possibilità di falsi positivi non è una preoccupazione, e non ti interessa tenere la corda in giro, leggi i filtri di fioritura.
Leggi altre domande sui tag data-structures