Collezioni
84. Parlaci degli iteratori e di come vengono utilizzati
Le raccolte sono l'argomento preferito in qualsiasi intervista agli sviluppatori Java. Quando rispondono alle domande sulla gerarchia della raccolta, i candidati spesso dicono che tutto inizia con l' interfaccia della raccolta . Ma non è così. C'è un'altra interfaccia un livello sopra: Iterable . Questa interfaccia è costituita dal metodo iterator() , che consente di accedere all'oggetto Iterator per la raccolta corrente. E cos'è esattamente questo oggetto Iterator ? L' oggetto Iterator offre la possibilità di spostarsi all'interno di una raccolta ed eseguire l'iterazione sui suoi elementi e non è necessario che l'utente conosca i dettagli di implementazione specifici della raccolta. In altre parole, è una sorta di puntatore agli elementi della collezione, come se si sbirciasse all'interno di uno di essi. L'iteratore ha metodi come:-
hasNext() — restituisce true se l'iterazione ha un altro elemento (questo metodo ti consente di sapere quando hai raggiunto la fine della raccolta);
-
next() — restituisce l'elemento successivo nell'iterazione. Se non ce n'è uno, viene lanciata una NoSuchElementException . Ciò significa che prima di utilizzare questo metodo, è meglio utilizzare il metodo hasNext() per assicurarsi che esista un elemento successivo;
-
rimuovi() — rimuove dalla raccolta l'ultimo elemento ricevuto utilizzando il metodo next() . Se next() non è mai stato chiamato, la chiamata a delete() causerà la generazione di un'eccezione IllegalStateException ;
-
forEachRemaining(<Consumer>) — esegue l'azione passata su ciascun elemento della raccolta (questo metodo è apparso in Java 8).
List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
iterator.next();
iterator.remove();
}
System.out.println(list.size());
La console visualizzerà quanto segue:
iterator.forEachRemaining(x -> System.out.print(x));
Ma una volta fatto questo, l'iteratore diventa inadatto per un ulteriore utilizzo: ha attraversato l'intero elenco e un iteratore ordinario non ha metodi per eseguire l'iterazione all'indietro. E questo costituisce un bel passaggio alla discussione su LinkedList , in particolare sul suo metodo listIterator() , che restituisce un tipo avanzato di iteratore: ListIterator . Oltre ai metodi di un iteratore regolare (standard), questo tipo ha quanto segue:
-
add(<Element>) — aggiunge un nuovo elemento alla lista;
-
hasPrevious() — restituisce true se c'è un elemento situato prima dell'elemento successivo (se c'è un elemento precedente);
-
nextIndex() — restituisce l'indice dell'elemento successivo;
-
previous() — restituisce l'elemento precedente (quello prima dell'elemento successivo);
-
previousIndex restituisce l'indice dell'elemento precedente.
-
set(<Element>) — sostituisce l'ultimo elemento restituito da next() o previous() .
85. Quale gerarchia di raccolte esiste nel Java Collection Framework?
Esistono due gerarchie di raccolte in Java. La prima gerarchia è la gerarchia della Collezione, che ha la seguente struttura: È divisa nelle seguenti sottoraccolte:-
Set è un'interfaccia che descrive un set, una struttura dati che contiene elementi univoci (non ripetitivi) non ordinati. Questa interfaccia ha alcune implementazioni standard: TreeSet , HashSet e LinkedHashSet .
-
List è un'interfaccia che descrive una struttura dati che memorizza una sequenza ordinata di oggetti. Gli oggetti in un elenco possono essere inseriti e rimossi tramite il loro indice nell'elenco (come un array, ma con ridimensionamento dinamico). Questa interfaccia ha anche alcune implementazioni standard: ArrayList , Vector ( deprecato e non attualmente utilizzato ) e LinkedList .
-
La coda è un'interfaccia che descrive una struttura dati che memorizza gli elementi in una coda FIFO (First In First Out) . Questa interfaccia ha le seguenti implementazioni standard: LinkedList (esatto, implementa anche Queue ) e PriotityQueue .
86. Qual è la struttura interna di un ArrayList?
Un ArrayList è come un array, ma può espandersi dinamicamente. Che cosa significa? Dietro le quinte, ArrayList utilizza un array ordinario, ovvero memorizza i suoi elementi in un array interno la cui dimensione predefinita è 10 celle. Una volta che l'array interno è pieno, viene creato un nuovo array. La dimensione del nuovo array è determinata da questa formula:
<size of the current array> * 3 / 2 + 1
Quindi, se la dimensione del nostro array è 10, la dimensione di quello nuovo sarà: 10 * 3 / 2 + 1 = 16. Quindi tutti i valori dell'array originale (vecchio) verranno copiati al suo interno utilizzando il metodo integrato System.arraycopy() e l'array originale viene eliminato. In poche parole, è così che ArrayList implementa il ridimensionamento dinamico. Consideriamo i metodi ArrayList più popolari : 1. add(<Element>) — aggiunge un elemento alla fine dell'array (nell'ultima cella vuota), dopo aver prima controllato se c'è una cella disponibile nell'array. In caso contrario, viene creato un nuovo array e gli elementi vengono copiati al suo interno. La complessità temporale di questa operazione è O(1). Esiste un metodo add(<Index>, <Elelement>) simile . Aggiunge un elemento non alla fine dell'elenco (array), ma alla cella specifica indicata dall'indice inserito come argomento. In questo caso, la complessità temporale varierà a seconda di dove aggiungi:
- se l'aggiunta è vicina all'inizio della lista, allora la complessità temporale sarà prossima a O(N), perché tutti gli elementi situati a destra di quello nuovo dovranno essere spostati di una cella a destra;
- se l'elemento è inserito al centro, allora sarà O(N/2), poiché dobbiamo solo spostare metà degli elementi dell'elenco di una cella a destra.
87. Qual è la struttura interna di una LinkedList?
Un ArrayList contiene elementi nell'array interno, ma un LinkedList li memorizza in un elenco doppiamente collegato. Ciò significa che ogni elemento contiene un collegamento all'elemento precedente e all'elemento successivo . Il primo elemento non si collega a un elemento precedente (dopotutto è il primo). È anche considerato l'inizio della lista e l' oggetto LinkedList ha un riferimento diretto ad esso. Allo stesso modo, l'ultimo elemento non ha l'elemento successivo, poiché è la coda della lista. Anche l' oggetto LinkedList fa riferimento direttamente ad esso. Ciò significa che la complessità temporale dell'accesso alla testa o alla coda di una lista è O(1). In ArrayList , se l'elenco cresce, cresce anche l'array interno. Qui tutto è più semplice: aggiungere un riferimento è semplice come cambiare un paio di link. Diamo un'occhiata ad alcuni dei metodi LinkedList più utilizzati : 1. add(<Element>) — aggiunge un elemento alla fine della lista, ovvero dopo l'ultimo elemento (5), verrà aggiunto un collegamento al nuovo elemento come successivo . Il riferimento precedente nel nuovo elemento punterà all'elemento (5) che ora lo precede nell'elenco. La complessità temporale di questa operazione è O(1), poiché abbiamo bisogno solo del collegamento all'ultimo elemento e, come ricorderai, l'oggetto LinkedList ha un riferimento diretto alla coda e l'accesso ad esso ha una complessità temporale costante minima. 2. add(<Index>, <Element>) — aggiunge un elemento per indice. Quando si aggiunge un elemento, diciamo, al centro di un elenco, questo metodo prima esegue l'iterazione sugli elementi dalla testa e dalla coda (in entrambe le direzioni) finché non viene trovata la posizione desiderata. Se aggiungiamo un elemento tra il terzo e il quarto elemento (nell'immagine sopra), il collegamento successivo del terzo elemento punterà al nuovo elemento. E il precedente dell'elemento appena aggiunto punterà al terzo. A sua volta, il collegamento precedente del vecchio quarto elemento ora punterà al nuovo elemento, e il collegamento successivo del nuovo elemento punterà al nuovo quarto elemento: La complessità temporale di questo metodo dipende dall'indice del nuovo elemento:- se è vicino alla testa o alla coda, l'operazione si avvicinerà a O(1), poiché in realtà non sarà necessario iterare sugli elementi;
- se è vicino al centro, allora avremo O(N/2), poiché il metodo cercherà contemporaneamente dalla testa e dalla coda finché non verrà trovato l'elemento desiderato.
88. Qual è la struttura interna di una HashMap?
Questa potrebbe essere una delle domande più popolari da porre ai candidati sviluppatori Java durante il colloquio. Una HashMap funziona con coppie chiave-valore . Come vengono archiviati all'interno della HashMap stessa? Una HashMap ha un array interno di nodi:
Node<K,V>[] table
Per impostazione predefinita, la dimensione dell'array è 16 e raddoppia ogni volta che viene riempita di elementi (ovvero, quando viene raggiunto LOAD_FACTOR ; specifica la soglia per quanto può essere pieno l'array - per impostazione predefinita, è 0.75 ) . Ciascuno dei nodi memorizza un hash della chiave, la chiave, un valore e un riferimento all'elemento successivo: in questo caso, il "riferimento all'elemento successivo" significa che abbiamo a che fare con una lista concatenata singolarmente, dove ogni elemento contiene un collegamento al successivo. In altre parole, una HashMap memorizza i suoi dati in una serie di elenchi collegati singolarmente. Ma lasciatemi dire subito che quando una cella dell'array della tabella ha un elenco concatenato composto da più di un elemento, ciò non va bene. Questo fenomeno è chiamato collisione . Ma prima le cose principali. Vediamo come viene salvata una nuova coppia utilizzando il metodo put . Innanzitutto, il metodo ottiene l' hashCode() della chiave . Ciò implica che affinché una HashMap funzioni correttamente, le chiavi utilizzate devono essere classi che sovrascrivono questo metodo. Questo codice hash viene quindi utilizzato nel metodo hash() interno per determinare un indice di alcune celle all'interno dell'array della tabella. L'indice risultante ci consente di accedere a una cella specifica dell'array della tabella. Qui abbiamo due casi:
- La cella è vuota: in questo caso, al suo interno viene memorizzato il nuovo valore del nodo .
- La cella non è vuota: in questo caso vengono confrontati i valori delle chiavi. Se sono uguali, il nuovo valore Nodo sovrascrive quello vecchio; se non è uguale, si accede al successivo e la sua chiave viene confrontata... E così via, finché il nuovo valore non sovrascrive qualche vecchio valore o si raggiunge la fine dell'elenco collegato singolarmente e quindi si memorizza lì il nuovo valore come ultimo elemento.
GO TO FULL VERSION