Analisi di domande e risposte da interviste per sviluppatori Java. Parte 9

Fuochi d'artificio! Essere un programmatore non è facile. Devi imparare costantemente, imparare sempre qualcosa di nuovo. Ma, come in ogni altra attività, la cosa più difficile è iniziare, fare il primo passo verso il proprio obiettivo. E poiché sei seduto su questo sito e stai leggendo questo articolo, hai completato il primo passaggio. Ciò significa che ora devi muoverti intenzionalmente verso il tuo obiettivo, senza rallentare o spegnerti lungo il percorso. Se ho capito bene, il tuo obiettivo è diventare uno sviluppatore Java o migliorare le tue conoscenze se lo sei. Se è così, allora sei nel posto giusto, perché continueremo ad analizzare un ampio elenco di oltre 250 domande per interviste agli sviluppatori Java. Continuiamo!

Collezioni

84. Parlaci degli iteratori e del loro utilizzo

Le raccolte sono uno degli argomenti preferiti in qualsiasi colloquio con uno sviluppatore Java e, quando parlano della gerarchia delle raccolte, i candidati spesso affermano che inizia con l' interfaccia Raccolta . Ma questo non è vero, perché sopra questa interfaccia ce n'è un'altra: Iterable . Questa interfaccia rappresenta il metodo iterator() , che consente di chiamare un oggetto Iterator per la raccolta corrente. E cos'è esattamente questo oggetto Iterator ? Un Iterator è un oggetto che offre la possibilità di spostarsi attraverso una raccolta ed eseguire l'iterazione sugli elementi senza che l'utente debba conoscere l'implementazione di una particolare raccolta. Cioè, questo è una sorta di puntatore agli elementi della collezione, che, per così dire, guarda a un certo posto al suo interno. L'iteratore ha i seguenti metodi:

• hasNext() - restituisce true se c'è un elemento situato dopo il puntatore (questo metodo permette di scoprire se è stata raggiunta la fine della raccolta);
• next() - restituisce l'elemento successivo dopo il puntatore. Se non ce n'è, viene lanciata NoSuchElementException . Cioè, prima di utilizzare questo metodo, è meglio assicurarsi che l'elemento esista - utilizzando hasNext() ;
• rimuovi() - rimuove l'ultimo elemento ricevuto dalla raccolta utilizzando il metodo next() . Se next() non è mai stato chiamato prima di rimuovere() , verrà lanciata un'eccezione - IllegalStateException ;
• forEachRemaining(<Consumer>) - esegue l'azione passata con ciascun elemento della raccolta (il metodo è apparso in Java 8).

Ecco un piccolo esempio di iterazione di un elenco e rimozione di tutti i suoi elementi utilizzando i metodi iteratori discussi:

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à: Ciò significa che la rimozione degli elementi ha avuto successo. Una volta ottenuto un iteratore, potremmo utilizzare un metodo per stampare tutti gli elementi sullo schermo:

iterator.forEachRemaining(x -> System.out.print(x));

Ma dopo questo, l'iteratore diventerebbe inadatto per un ulteriore utilizzo, poiché attraverserebbe l'intero elenco e un iteratore regolare non dispone di metodi per il backtracking. Qui ci avviciniamo gradualmente a LinkedList , vale a dire al suo metodo listIterator() , che restituisce un tipo modernizzato di iteratore - ListIterator . Oltre ai metodi iteratori regolari (standard), questo ne ha altri aggiuntivi:

• add(<Element>) - inserisce un nuovo elemento nella lista;
• hasPrevious() - restituisce true se c'è un elemento situato prima del puntatore (se c'è un elemento precedente);
• nextIndex() - restituisce l'indice nell'elenco dell'elemento successivo dopo il puntatore;
• previous() - restituisce l'elemento precedente (fino al puntatore);
• previousIndex() - restituisce l'indice dell'elemento precedente;
• set(<Element>) - Sostituisce l'ultimo elemento restituito dai metodi next() o previous() .

Come puoi vedere, la funzionalità di questo iteratore è molto più interessante: ti consente di muoverti in entrambe le direzioni e libera le mani quando lavori con gli elementi. Inoltre, quando le persone parlano di iteratori, a volte intendono il modello stesso. Per evitare di finire nei guai e parlarne in modo convincente, leggi questo articolo sul pattern Iterator .

85. Qual è la gerarchia delle raccolte in Java Collection Framework?

Esistono due gerarchie di raccolte in Java. La prima gerarchia è la gerarchia della Collezione stessa con la seguente struttura: Essa, a sua volta, è suddivisa nelle seguenti sottoraccolte:

• Set è un'interfaccia che descrive una struttura di dati come un insieme contenente elementi unici (non ripetitivi) non ordinati. L'interfaccia ha implementazioni standard: TreeSet , HashSet e LinkedHashSet .
• List è un'interfaccia che descrive una struttura dati che memorizza una sequenza ordinata di oggetti. Le istanze contenute in un Elenco possono essere inserite ed eliminate tramite il loro indice in questa raccolta (analogamente a un array, ma con ridimensionamento dinamico). L'interfaccia ha implementazioni standard: ArrayList , Vector ( considerato obsoleto e attualmente non utilizzato ) e LinkedList .
• Queue è un'interfaccia che descrive una struttura dati che memorizza gli elementi sotto forma di una coda che segue la regola FIFO: First In First Out . L'interfaccia ha le seguenti implementazioni standard: LinkedList (sì, implementa anche Queue ) e PriotityQueue .

La seconda gerarchia di raccolte è Map , che ha la seguente struttura: In questa raccolta non ci sono divisioni in sottoraccolte (poiché la gerarchia Map stessa è qualcosa come una sottoraccolta, ma situata separatamente). Le implementazioni della mappa standard sono Hashtable (considerata deprecata), LinkedHashMap e TreeMap . In realtà, quando viene chiesto di Collection , di solito si intendono entrambe le gerarchie.

86. Qual è la struttura interna di un ArrayList?

ArrayList è simile a un array, ma con la capacità di espandersi dinamicamente. Cosa significa? Il fatto è che ArrayList funziona sulla base di un array regolare, ovvero memorizza gli elementi in un array interno (la sua dimensione predefinita è 10 celle). Quando l'array interno è pieno, viene creato un nuovo array, la cui dimensione è determinata dalla formula:

<размерТекущегоМассива> * 3 / 2  + 1

Cioè, se la dimensione del nostro array è 10, la dimensione di quello nuovo sarà: 10 * 3 / 2 + 1 = 16. Successivamente, tutti i valori del primo (vecchio) array vengono copiati al suo interno utilizzando il comando metodo nativo System.arraycopy () e il primo array viene eliminato. In realtà, questo è il modo in cui viene implementata l'estensibilità dinamica di ArrayList . Diamo un'occhiata ai metodi ArrayList più utilizzati : 1. add(<Elelement>) - aggiunge un elemento alla fine dell'array (all'ultima cella vuota) e prima controlla se c'è spazio in questo array. Se non è presente, viene creato un nuovo array in cui vengono copiati gli elementi. La complessità logaritmica di questa operazione è O(1). Esiste un metodo simile: add(<Index>,<Elelement>) . Aggiunge un elemento non alla fine dell'elenco (array), ma a una cella specifica con l'indice fornito come argomento. In questo caso, la complessità logaritmica varierà a seconda di dove viene aggiunta:

• se questo fosse all'incirca l'inizio della lista, la complessità logaritmica 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 - O(N/2) perché dobbiamo spostare solo la metà degli elementi dell'elenco di una cella a destra.

Cioè, la complessità logaritmica di questo metodo varia da O(N) a O(1) a seconda di dove è inserito l'elemento. 2. set(<Index>,<Elelement>) - scrive un elemento nella posizione specificata nell'elenco. Se c'è già un elemento in quella posizione, lo sovrascrive. La complessità logaritmica di questa operazione è O(1), perché non ci sono spostamenti: solo ricerca per indice nell'array, che, come ricordiamo, ha complessità O(1), e scrittura dell'elemento. 3. rimuovi(<indice>) - rimuove un elemento tramite il suo indice nell'array interno. Quando elimini un elemento che non si trova alla fine dell'elenco, devi spostare tutti gli elementi alla sua destra di una cella a sinistra per colmare lo spazio rimasto dopo l'eliminazione dell'elemento. Pertanto, la complessità logaritmica sarà la stessa di add(<Index>,<Elelement>) se l'elemento era al centro - O(N/2) - perché è necessario spostare metà degli elementi a sinistra. Di conseguenza, se fosse all'inizio - O(N). Bene, se alla fine è O(1), non è necessario spostare nulla. Per chi volesse approfondire questo argomento, lascio questo link ad un articolo con analisi della classe ArrayList .

87. Qual è la struttura interna di LinkedList?

Se ArrayList contiene elementi in un array interno, LinkedList è sotto forma di un elenco doppiamente collegato. Ciò significa che ogni elemento contiene un collegamento all'elemento precedente ( previous ) e a quello successivo ( next ). Il primo elemento non ha un collegamento con il precedente (è il primo), ma è considerato l'inizio della lista, e la LinkedList ha un collegamento direttamente con esso. L'ultimo elemento, infatti, non ha un elemento successivo, è la coda della lista, e quindi c'è un collegamento diretto ad esso nella LinkedList stessa . Pertanto, la complessità logaritmica dell'accesso alla testa o alla coda di una lista è O(1). In ArrayList, quando l'elenco è cresciuto, l'array interno è aumentato, ma qui tutto avviene in modo più semplice: quando si aggiunge un elemento, un paio di collegamenti cambiano semplicemente. Diamo un'occhiata ad alcuni dei metodi LinkedlList più utilizzati : 1. add(<Elelement>) - aggiunta alla fine dell'elenco, ad es. dopo l'ultimo elemento (5) verrà aggiunto un collegamento al nuovo elemento come successivo . Il nuovo elemento avrà un collegamento all'ultimo (5) come elemento precedente . La complessità logaritmica di tale operazione sarà O(1), poiché è necessario solo un collegamento all'ultimo elemento e, come ricorderete, la coda ha un collegamento diretto da LinkedList e la complessità logaritmica per accedervi è minima. 2. add(<Index>,<Elelement>) - aggiunge un elemento per indice. Quando si aggiunge un elemento, ad esempio, al centro di un elenco, gli elementi dalla testa e dalla coda (su entrambi i lati) vengono prima ripetuti finché non viene trovata la posizione desiderata. Se vogliamo inserire un elemento tra il terzo e il quarto (nella figura sopra), allora durante la ricerca del posto giusto, il collegamento successivo del terzo elemento punterà già a quello nuovo. Per quello nuovo, il collegamento precedente punterà al terzo. Di conseguenza, il collegamento del quarto elemento - precedente - punterà già al nuovo elemento, e il collegamento successivo del nuovo elemento punterà al quarto elemento: La complessità logaritmica di questo metodo dipenderà dall'indice dato al nuovo elemento:

• se è vicino alla testa o alla coda, si avvicinerà a O(1), poiché in realtà non sarà necessario iterare sugli elementi;
• se è vicino al centro, allora O(N/2) - gli elementi della testa e della coda verranno ordinati simultaneamente finché non viene trovato l'elemento richiesto.

3. set(<Index>,<Elelement>) - scrive un elemento nella posizione specificata nell'elenco. La complessità logaritmica di questa operazione varierà da O(1) a O(N/2), sempre a seconda di quanto l'elemento è vicino alla testa, alla coda o al centro. 4. Remove(<index>) - rimuove un elemento dall'elenco, essenzialmente facendo in modo che l'elemento che precede quello da rimuovere ( previous ) faccia riferimento all'elemento che viene dopo quello da rimuovere ( next ). E viceversa: in modo che l'elemento che viene dopo quello da eliminare si riferisca a quello che precede quello da eliminare: Il risultato è un processo inverso all'aggiunta per indice ( add(<Index>,<Elelement>) ). Per chi volesse approfondire la struttura interna di LinkedList , consiglio la lettura di questo articolo .

88. Qual è la struttura interna di una HashMap?

Forse una delle domande più popolari quando si intervista uno sviluppatore Java. HashMap v funziona con coppie chiave-valore . Come vengono archiviati all'interno dello stesso HashMapv ? All'interno della HashMap c'è una serie di nodi:

Node<K,V>[] table

Per impostazione predefinita, la dimensione dell'array è 16 e raddoppia ogni volta che viene riempita di elementi (quando viene raggiunta LOAD_FACTOR - una certa percentuale di pienezza, per impostazione predefinita è 0.75 ). Ogni nodo memorizza un hash della chiave, una chiave, un valore e un collegamento all'elemento successivo: in realtà, "collegamento all'elemento successivo" significa che abbiamo a che fare con una lista collegata singolarmente, in cui ogni elemento contiene un collegamento a il prossimo. Cioè, HashMap memorizza i dati in una serie di elenchi collegati singolarmente. Ma lo noterò subito: quando una cella dell'array della tabella ha un collegamento a un elenco simile concatenato singolarmente composto da più di un elemento, questo non va bene. Questo fenomeno è chiamato collisione . Ma prima le cose principali. Vediamo come viene salvata una nuova coppia utilizzando il metodo put . Per prima cosa viene preso l'hachCode() della chiave. Pertanto, affinché hashmap funzioni correttamente , è necessario prendere classi in cui questo metodo viene sovrascritto come chiavi. Questo codice hash viene quindi utilizzato nel metodo interno - hash() - per determinare il numero all'interno della dimensione dell'array della tabella . Successivamente, utilizzando il numero ricevuto, si accede a una cella specifica dell'array della tabella . Qui abbiamo due casi:

1. La cella è vuota: al suo interno è memorizzato il nuovo valore del nodo .
2. La cella non è vuota: viene confrontato il valore delle chiavi. Se sono uguali, il nuovo valore Nodo sovrascrive quello vecchio, se non sono uguali, si accede all'elemento successivo e lo si confronta con la sua chiave... E così via fino a quando il nuovo valore sovrascrive quello vecchio o raggiunge la fine del elenco collegato singolarmente e verrà memorizzato lì come ultimo elemento.

Quando si cerca un elemento tramite chiave ( metodo get(<key>) ), viene calcolato l'hashCode della chiave, quindi il suo valore all'interno dell'array utilizzando hash() e utilizzando il numero risultante, viene trovata la cella dell'array della tabella , in cui la ricerca è già effettuata enumerando i nodi e confrontando la chiave del nodo desiderato con la chiave di quello corrente. Le operazioni in Map, in una situazione ideale, hanno una complessità algoritmica di O(1), perché accedono a un array e, come ricorderete, indipendentemente dal numero di elementi, le operazioni su un array hanno una complessità di O(1) . Ma questo è l'ideale. Quando la cella dell'array utilizzata non è vuota (2) e sono già presenti alcuni nodi, la complessità algoritmica si trasforma in lineare O(N), perché ora è necessario iterare sugli elementi prima di trovare il posto giusto. Non posso fare a meno di menzionarlo: a partire da Java 8, se un nodo di una lista collegata singolarmente ha più di 8 elementi (collisioni), si trasforma in un albero binario. In questo caso la complessità algoritmica non sarà più O(N), ma O(log(N)): questo è un altro discorso, no? HashMap è un argomento importante e alla gente piace porre domande al riguardo nelle interviste. Pertanto, ti consiglio di capirlo in dettaglio (in modo che rimbalzi sui tuoi denti). Personalmente, non ho avuto un'intervista senza domande su HashMap . Puoi trovare un approfondimento su HashMap in questo articolo . Per oggi è tutto, continua...