L'inizio del cammino
Oggi vorrei parlare di un argomento così interessante come il “
Java Collections Framework ” o, in termini semplici, delle collezioni. La maggior parte del lavoro del codice consiste nell'elaborare i dati in una forma o nell'altra. Ottieni un elenco di utenti, ottieni un elenco di indirizzi, ecc. In qualche modo ordinali, esegui una ricerca, confrontali. Ecco perché la conoscenza delle collezioni è considerata una competenza fondamentale. Ecco perché voglio parlarne. Inoltre, una delle domande più comuni nelle interviste agli sviluppatori Java riguarda le raccolte. Ad esempio, "disegna una gerarchia di raccolte". Il compilatore online ci aiuterà nel nostro cammino. Ad esempio, puoi utilizzare " Tutorialspoint
Online Java Compiler " o
Repl.it. Il percorso per conoscere qualsiasi struttura dati inizia con le variabili ordinarie (Variabili). Sul sito Web Oracle, vari argomenti sono rappresentati come "percorsi" o Trails. Quindi, il percorso per conoscere Java si chiama “
Trail: Learning the Java Language: Table of Contents ”. E le basi del linguaggio (cioè le basi del linguaggio) iniziano con le variabili. Scriviamo quindi un semplice codice:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Va bene in tutto, tranne che capiamo che questo codice è buono e bello solo per una variabile. Cosa fare se ce ne sono diversi? Gli array sono stati inventati per memorizzare dati di un tipo. Nello stesso Trail di Oracle c'è una sezione separata dedicata agli array. Questa sezione si chiama: "
Array ". Anche lavorare con gli array è abbastanza semplice:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Gli array risolvono il problema della memorizzazione di più valori in un unico posto. Ma impone una limitazione: la dimensione dell'array è costante. Se, come nell'esempio, abbiamo detto che dimensione = 2, allora è uguale a due. È tutto. Se vogliamo un array più grande, dobbiamo creare una nuova istanza. Inoltre, anche trovare un elemento è una cosa complicata per un array. Esiste un metodo
Arrays.binarySearch, ma questa ricerca funziona solo su un array ordinato (per un array non ordinato, il risultato è indefinito o semplicemente imprevedibile). Cioè, la ricerca ci obbligherà a ordinare ogni volta. L'eliminazione cancella anche semplicemente il valore. Pertanto, non sappiamo ancora quanti dati ci sono effettivamente nell'array, sappiamo solo quante celle ci sono nell'array. Per rinfrescare le tue conoscenze sugli array:
E come conseguenza dello sviluppo del linguaggio Java, in JDK 1.2 è apparso il Java Collections Framework, di cui parleremo oggi.
Collezione
Inizia a costare fin dall'inizio. Perché le collezioni? Il termine stesso deriva da cose come "Teoria dei tipi" e "Tipi di dati astratti". Ma se non consideriamo le questioni importanti, allora quando abbiamo diverse cose, possiamo chiamarle una “raccolta di cose”. Coloro che raccolgono oggetti. In generale la parola stessa raccogliere deriva dal lat. collectionio "raccogliere, collezionare". Cioè, una raccolta è una raccolta di qualcosa, un contenitore per alcuni elementi. Quindi abbiamo una raccolta di elementi. Cosa potremmo voler fare con esso:
Come puoi vedere, potremmo volere cose abbastanza logiche. Comprendiamo anche che potremmo voler fare qualcosa con più raccolte:
Di conseguenza, gli sviluppatori Java hanno scritto l'interfaccia java.util.Collection per descrivere questo comportamento generale per tutte le raccolte . L'interfaccia Raccolta è il punto in cui hanno origine tutte le raccolte. La collezione è un’idea, è un’idea di come dovrebbero comportarsi tutte le collezioni. Pertanto, il termine "Collezione" è espresso come interfaccia. Naturalmente, un'interfaccia necessita di implementazioni. L'interfaccia
java.util.Collectionha una classe astratta
AbstractCollection, cioè una sorta di "raccolta astratta", che rappresenta lo scheletro per altre implementazioni (come scritto nel JavaDoc sopra la classe
java.util.AbstractCollection). Parlando di raccolte, torniamo indietro e ricordiamo che vogliamo iterare su di esse. Ciò significa che vogliamo scorrere gli elementi uno per uno. Questo è un concetto molto importante. Pertanto, l'interfaccia
Collectionviene ereditata da
Iterable. Questo è molto importante perché... in primo luogo, tutto ciò che è Iterable deve essere in grado di restituire un Iterator in base al suo contenuto. E in secondo luogo, tutto ciò che Iterable può essere utilizzato in loop
for-each-loop. Ed è con l'aiuto di un iteratore che vengono implementati
AbstractCollectionmetodi come . E il percorso per comprendere le raccolte inizia con una delle strutture dati più comuni: un elenco, ad es. .
containstoArrayremoveList
Elenchi
Quindi, gli elenchi occupano un posto importante nella gerarchia delle raccolte:
Come possiamo vedere, le liste implementano l' interfaccia
java.util.List . Gli elenchi esprimono che abbiamo una raccolta di elementi disposti in sequenza uno dopo l'altro. Ogni elemento ha un indice (come in un array). In genere, una lista consente di avere elementi con lo stesso valore. Come abbiamo detto sopra,
Listconosce l'indice dell'elemento. Ciò consente di ottenere (
get) un elemento per indice o impostare un valore per un indice specifico (
set). I metodi di raccolta
add, consentono di specificare l'indice da cui eseguirli. Inoltre, y ha la propria versione di un iteratore chiamato . Questo iteratore conosce l'indice dell'elemento, quindi può eseguire l'iterazione non solo in avanti, ma anche all'indietro. Può anche essere creato da un punto specifico della collezione. Tra tutte le implementazioni, ce ne sono due più comunemente utilizzate: e . Innanzitutto è una lista ( ) basata su un array ( ). Ciò consente di ottenere un "accesso casuale"
agli elementi. L'accesso casuale è la capacità di recuperare immediatamente un elemento per indice, anziché scorrere tutti gli elementi fino a trovare l'elemento con l'indice desiderato. È l'array come base che permette di raggiungere questo obiettivo. Al contrario, è una lista collegata. Ogni voce in un elenco collegato è rappresentata nel modulo , che memorizza i dati stessi, nonché un collegamento al successivo (next) e al precedente (previous) . Implementa così "Accesso sequenziale
" . È chiaro che per trovare il 5° elemento dovremo passare dal primo all'ultimo elemento, perché non abbiamo accesso diretto al quinto elemento. Possiamo accedervi solo dal 4° elemento. La differenza nel loro concetto è riportata di seguito:
addAllremoveListListIteratorArrayListLinkedListArrayListListArrayLinkedListEntryEntryLinkedList
Nel lavoro, come capisci, c'è anche una differenza. Ad esempio, aggiungendo elementi. Gli
LinkedListelementi sono semplicemente collegati come gli anelli di una catena. Ma
ArrayListmemorizza gli elementi in un array. E un array, come sappiamo, non può cambiare la sua dimensione. Come funziona allora
ArrayList? E funziona in modo molto semplice. Quando lo spazio nell'array si esaurisce, aumenta di 1,5 volte. Ecco il codice zoom:
int newCapacity = oldCapacity + (oldCapacity >> 1); Un'altra differenza nel funzionamento è l'eventuale spostamento degli elementi. Ad esempio, quando si aggiungono o rimuovono elementi al centro. Per rimuovere da
LinkedListun elemento, rimuovi semplicemente i riferimenti a questo elemento. Nel caso di ,
ArrayListsiamo costretti a spostare gli elementi ogni volta utilizzando
System.arraycopy. Pertanto, più elementi ci sono, più azioni dovranno essere eseguite. Una descrizione più dettagliata può essere trovata in questi articoli:
Dopo aver esaminato ArrayList non si può fare a meno di ricordare il suo “predecessore”, la classe
java.util.Vector . La differenza
Vectorè
ArrayListche i metodi per lavorare con la raccolta (aggiunta, eliminazione, ecc.) sono sincronizzati. Cioè, se un thread (
Thread) aggiunge elementi, gli altri thread aspetteranno finché il primo thread non termina il suo lavoro. Poiché la thread safety spesso non è richiesta, in questi casi si consiglia di utilizzare la classe
ArrayList, come esplicitamente dichiarato nel JavaDoc per la classe
Vector. Inoltre,
Vectoraumenta le sue dimensioni non di 1,5 volte,
ArrayListma di 2 volte. Altrimenti, il comportamento è lo stesso:
Vectorla memorizzazione degli elementi sotto forma di array è nascosta e l'aggiunta/rimozione di elementi ha le stesse conseguenze di
ArrayList. In effetti,
Vectorce lo siamo ricordato per un motivo. Se guardiamo nel Javadoc, vedremo in "Direct Known Subclasses" una struttura come
java.util.Stack . Lo stack è una struttura interessante che è una
last-in-first-outstruttura LIFO (last in, first out). Pila tradotta dall'inglese è una pila (come una pila di libri, per esempio). Lo stack implementa metodi aggiuntivi:
peek(look, look),
pop(push),
push(push). Il metodo
peekè tradotto come guardare (ad esempio,
sbirciare dentro la borsa è tradotto come “
guardare dentro la borsa ”, e
sbirciare attraverso il buco della serratura è tradotto come “
sbirciare attraverso il buco della serratura ”). Questo metodo ti consente di guardare la "cima" dello stack, cioè ottieni l'ultimo elemento senza rimuoverlo (cioè senza rimuoverlo) dallo stack. Il metodo
pushspinge (aggiunge) un nuovo elemento nello stack e lo restituisce, mentre il metodo element
popspinge (rimuove) e restituisce quello rimosso. In tutti e tre i casi (ovvero peek, pop e push), lavoriamo solo con l'ultimo elemento (ovvero la "cima dello stack"). Questa è la caratteristica principale della struttura dello stack. A proposito, c'è un compito interessante per comprendere gli stack, descritto nel libro "A Programmer's Career" (Cracking Coding Interview). C'è un compito interessante in cui utilizzando la struttura "stack" (LIFO) è necessario implementare la "coda "struttura (FIFO). Dovrebbe sembrare come questo:
L'analisi di questa attività può essere trovata qui: "
Implementa una coda utilizzando gli stack - The Queue ADT ("Implement Queue Using Stacks" su LeetCode) ". Quindi passiamo senza problemi a una nuova struttura dati: una coda.
Coda
Una coda è una struttura a noi familiare dalla vita. Code ai negozi, ai medici. Chi è arrivato primo (First In) sarà il primo a uscire dalla coda (First Out). In Java, una coda è rappresentata dall'interfaccia
java.util.Queue . Secondo Javadoc della coda, la coda aggiunge i seguenti metodi:
Come puoi vedere, esistono metodi di ordine (la mancata esecuzione è irta di eccezioni) e metodi di richiesta (l'impossibilità di eseguirli non porta a errori). È anche possibile ottenere l'elemento senza rimuoverlo (peek o elemento). L'interfaccia della coda ha anche un utile successore:
Deque . Questa è la cosiddetta "coda a doppio senso". Cioè, una tale coda ti consente di utilizzare questa struttura sia dall'inizio che dalla fine. La documentazione afferma che "Deques può anche essere utilizzato come stack LIFO (Last-In-First-Out). Questa interfaccia dovrebbe essere utilizzata preferibilmente rispetto alla classe Stack legacy.", ovvero si consiglia di utilizzare le implementazioni Deque invece di Pila. Il Javadoc mostra quali metodi descrive l'interfaccia Deque:
Vediamo quali implementazioni ci sono. E vedremo un fatto interessante: LinkedList è entrato nel campo delle code) Cioè, LinkedList implementa sia
List, che
Deque. Ma ci sono anche le “solo code”, ad esempio
PriorityQueue. Non viene ricordata spesso, ma invano. Innanzitutto non è possibile utilizzare "oggetti non comparabili" in questa coda, ad es. è necessario specificare il Comparatore oppure tutti gli oggetti devono essere confrontabili. In secondo luogo, "questa implementazione fornisce tempo O(log(n)) per i metodi di accodamento e rimozione dalla coda". La complessità logaritmica esiste per una ragione. Implementata PriorityQueue in base all'heap. Il Javadoc dice: "Coda prioritaria rappresentata come un heap binario bilanciato". Lo spazio di archiviazione stesso per questo è un array regolare. Che cresce quando necessario. Quando l'heap è piccolo, aumenta 2 volte. E poi del 50%. Commento dal codice: "Taglia doppia se piccola; altrimenti aumenta del 50%". La coda prioritaria e l'heap binario sono un argomento separato. Quindi per maggiori informazioni:
Come implementazione,
java.util.Dequepuoi utilizzare la classe
java.util.ArrayDeque . Cioè, gli elenchi possono essere implementati utilizzando un elenco collegato e un array e le code possono anche essere implementate utilizzando un array o un elenco collegato. Le interfacce
Queuee
Dequehanno discendenti che rappresentano la "coda di blocco":
BlockingQueuee
BlockingDeque. Ecco la modifica dell'interfaccia rispetto alle code normali:
Diamo un'occhiata ad alcuni esempi di blocco delle code. Ma sono interessanti. Ad esempio, BlockingQueue è implementato da:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Ma
BlockingDequeimplementano tutto, dai Collection Frameworks standard
LinkedBlockingDeque. Ogni coda è oggetto di una revisione separata. E nell'ambito di questa recensione, descriveremo la gerarchia delle classi non solo con
List, ma anche con
Queue:
Come possiamo vedere dal diagramma, le interfacce e le classi del Java Collections Framework sono fortemente intrecciate. Aggiungiamo un altro ramo della gerarchia:
Set.
Impostato
Set– tradotto come “set”. Si differenzia da una coda e da una lista
Setper la sua maggiore astrazione rispetto alla memorizzazione degli elementi.
Set- come un sacco di oggetti, dove non si sa come si trovano gli oggetti e in quale ordine si trovano. In Java, tale insieme è rappresentato dall'interfaccia
java.util.Set . Come dice la documentazione,
Setquesta è una "raccolta che non contiene elementi duplicati". È interessante notare che l'interfaccia stessa
Setnon aggiunge nuovi metodi all'interfaccia
Collection, ma chiarisce solo i requisiti (su cosa non dovrebbe contenere duplicati). Inoltre, dalla descrizione precedente ne consegue che non è possibile
Setottenere semplicemente un elemento da esso. Iterator viene utilizzato per ottenere elementi.
Setha molte altre interfacce ad esso associate. Il primo è
SortedSet. Come suggerisce il nome,
SortedSetindica che tale insieme è ordinato, e quindi gli elementi implementano l'interfaccia
Comparableo sono specificati
Comparator. Inoltre,
SortedSetoffre diversi metodi interessanti:
Inoltre, esistono metodi
first(elemento più piccolo per valore) e
last(elemento più grande per valore). C'è
SortedSetun erede -
NavigableSet. Lo scopo di questa interfaccia è descrivere i metodi di navigazione necessari per identificare con maggiore precisione gli elementi appropriati. Una cosa interessante è
NavigableSetche aggiunge al solito iteratore (che va dal più piccolo al più grande) un iteratore per l'ordine inverso -
descendingIterator. Inoltre,
NavigableSetti permette di utilizzare il metodo
descendingSetper ottenere una visione di te stesso (View), in cui gli elementi sono in ordine inverso. Si chiama così
Viewperché attraverso l'elemento risultante è possibile modificare gli elementi di quello originale
Set. Cioè, in sostanza, si tratta di una rappresentazione dei dati originali in modo diverso e non di una copia degli stessi. È interessante notare che
NavigableSet, come
Queue, può gestire elementi
pollFirst(minimi) e
pollLast(massimi). Cioè, ottiene questo elemento e lo rimuove dal set. Che tipo di implementazioni ci sono? Innanzitutto, l'implementazione più famosa si basa su un codice hash:
HashSet . Un'altra implementazione altrettanto nota si basa su un albero rosso-nero:
TreeSet . Completiamo il nostro diagramma:
All'interno delle collezioni resta da sistemare la gerarchia: gli eremiti. Che a prima vista sta da parte -
java.util.Map.
Mappe
Le mappe sono una struttura dati in cui i dati vengono archiviati tramite chiave. Ad esempio, la chiave potrebbe essere un ID o un codice di città. Ed è attraverso questa chiave che i dati verranno ricercati. È interessante che le carte vengano visualizzate separatamente. Secondo gli sviluppatori (vedere "
Domande frequenti sulla progettazione delle API delle raccolte Java "), la mappatura dei valori-chiave non è una raccolta. E le mappe possono essere pensate più rapidamente come una raccolta di chiavi, una raccolta di valori, una raccolta di coppie chiave-valore. Questo è un animale così interessante. Quali metodi forniscono le carte? Diamo un'occhiata all'interfaccia API Java
java.util.Map . Perché Poiché le mappe non sono raccolte (non ereditano dalle raccolte), non contengono un file
contains. E questo è logico. Una mappa è composta da chiavi e valori. Quale di questi dovrebbe controllare il metodo
containse come non confondersi? Pertanto, l'interfaccia
Mapha due diverse versioni:
containsKey(contiene una chiave) e
containsValue(contiene un valore). Usandolo
keySetti permette di ottenere un mazzo di chiavi (lo stesso
Set). E utilizzando il metodo
valuespossiamo ottenere una raccolta di valori nella mappa. Le chiavi nella mappa sono uniche, come evidenziato dalla struttura dei dati
Set. I valori possono essere ripetuti, il che è enfatizzato dalla struttura dei dati della raccolta. Inoltre, utilizzando il metodo
entrySetpossiamo ottenere un insieme di coppie chiave-valore. Puoi leggere di più su quali implementazioni di carte ci sono nelle analisi più dettagliate:
Vorrei anche vedere cosa è
HashMapmolto simile a
HashSet, e
TreeMapa
TreeSet. Hanno anche interfacce simili:
NavigableSete
NavigableMap,
SortedSete
SortedMap. Quindi la nostra mappa finale sarà simile a questa:
Possiamo concludere con il fatto interessante che la raccolta
Setutilizza internamente
Map, dove i valori aggiunti sono le chiavi e il valore è lo stesso ovunque. Questo è interessante perché
Mapnon è una raccolta e restituisce
Set, che è una raccolta ma di fatto è implementato come
Map. Un po’ surreale, ma è andata così)
Conclusione
La buona notizia è che questa recensione finisce qui. La cattiva notizia è che questo è un articolo molto di revisione. Ogni implementazione di ciascuna raccolta merita un articolo a parte, così come ogni algoritmo nascosto ai nostri occhi. Ma lo scopo di questa recensione è ricordare cosa sono e quali sono le connessioni tra le interfacce. Spero che dopo una lettura attenta sarai in grado di tracciare un diagramma delle collezioni a memoria.
Bene, come al solito, alcuni link:
#Viacheslav
GO TO FULL VERSION