Cosa potrebbero chiedere durante un colloquio: Strutture dati in Java. Parte 2

PARTE 1 Ora parliamo delle basi che ogni sviluppatore Java dovrebbe conoscere. Di quel sapere classico da cui tutto ha inizio. Oggi vorrei toccare uno degli argomenti fondamentali di qualsiasi struttura di dati intervista in Java . Quindi, invece di girare intorno al cespuglio, cominciamo. Prendi la continuazione dell'elenco delle domande che ti potrebbero essere poste su questo argomento durante un colloquio.

6. Parlaci di List

List è un'interfaccia che rappresenta una struttura ordinata di oggetti, chiamata lista. Il “trucco” di questa struttura è che gli elementi contenuti nella Lista possono essere inseriti, modificati o cancellati tramite indice, cioè l'identificatore interno della Lista . In altre parole, indice significa: “quanti elementi provengono dall’inizio della lista”. Il primo elemento della Lista ha indice 0, il secondo ha indice 1 e così via. Quindi il quinto elemento è a quattro elementi dall'inizio dell'elenco. Come accennato in precedenza, l'ordine in cui gli elementi vengono aggiunti a un elenco è importante. Ecco perché la struttura dei dati è chiamata lista . Elenchiamo metodi unici per questa struttura che mirano a lavorare con gli elementi per indice:

• get - restituisce l'elemento nella posizione specificata (per valore di indice),
• rimuovi : rimuove l'elemento nella posizione specificata,
• set - sostituisce l'elemento nella posizione specificata con l'elemento specificato nel metodo.

Le principali implementazioni sono ArrayList e LinkedList . Ne parleremo più approfonditamente un po' più tardi. Vector è un elenco thread-safe, quindi ogni metodo in questa classe è sincronizzato. Ma tieni presente che se vuoi proteggere alcune azioni dell'elenco, sincronizzerai un'intera sequenza di operazioni. E la sincronizzazione delle singole operazioni è meno sicura e molto più lenta. Naturalmente, Vector dispone anche del blocco in alto, anche se non è necessario il blocco. Pertanto, questa classe è ora considerata obsoleta e non viene utilizzata. A proposito: ArrayList è simile a Vector , ma non utilizza il blocco, quindi viene utilizzato ovunque. Stack è una sottoclasse della classe Vector con un costruttore predefinito e tutti i metodi della classe Vector , più alcuni propri (ne parleremo più avanti). Ad esempio, puoi immaginare il processo come una pila di cartelle con documenti. Metti una cartella in cima alla pila e puoi prendere queste cartelle solo in ordine inverso, iniziando dall'alto. In realtà si tratta di un meccanismo di tipo LIFO , cioè Last In First Out , l'ultimo che arriva è il primo ad uscire. Lo stack implementa i propri metodi:

• push - aggiunge l'elemento passato in cima allo stack;
• peek - restituisce l'elemento che si trova in cima allo stack;
• pop - restituisce anche l'elemento che si trova in cima allo stack, ma lo rimuove;
• vuoto - controlla se lo stack è vuoto - vero o non - falso ;
• search : cerca nello stack un dato elemento. Se viene trovato un elemento, viene restituito il suo numero di sequenza relativo alla parte superiore dello stack. Se l'elemento non viene trovato, viene restituito il valore -1.

Al momento, la sottoclasse Stack non viene effettivamente utilizzata a causa della sua semplicità e inflessibilità, ma è tuttavia possibile incontrarla. Ad esempio, quando ricevi un errore e nella console vedi una serie di messaggi a riguardo. Puoi leggere ulteriori informazioni sullo stack e sulla coda in questo articolo .

7. Raccontaci della Mappa

Come affermato in precedenza, una mappa è una raccolta che ha una struttura separata di interfacce e relative implementazioni. È separato perché qui i valori non vengono memorizzati uno alla volta, ma in una coppia “chiave-valore”. Metodi di base della mappa :

• put(chiave K, valore V) - aggiunge un elemento alla mappa;
• get(Chiave oggetto) - cerca un valore per chiave;
• contieneKey(chiave oggetto) — controlla la mappa per la presenza di questa chiave;
• contieneValue(valore oggetto) - controlla la mappa per la presenza di questo valore;
• rimuovi(Chiave oggetto) - rimuove un valore tramite la sua chiave.

Come puoi vedere, la maggior parte delle operazioni funziona utilizzando una chiave. Di norma, come chiavi vengono scelti oggetti immutabili . Un tipico esempio di questo oggetto è String . Implementazioni della mappa di base :

1. HashMap — предназначена для хранения значений в произвольном порядке, но позволяет быстро искать элементы карты. Позволяет задавать ключ ключевым словом null, но не более одного раза, т.к. пары с одинаковыми ключами записываются поверх друг друга. Главным conditionм является уникальность ключей: значения же могут повторяться (может быть несколько null значений).
2. LinkedHashMap — аналог HashMap, который хранит значения в порядке добавления. Соответственно, How и LinkedList, у него есть header — голова двусвязного списка. При инициализации указывает сам на себя.

   Также у LinkedHashMap есть accessOrder, который указывает, Howим образом будет осуществляться доступ к elementм во время использования итератора. При accessOrder false доступ будет осуществляться в порядке вставки элементов. При значении true элементы будут в порядке последнего доступа (элемент, к которому было последнее обращение будет помещен в конец).

3. TreeMap — это Map, сортирующая элементы по значениям ключа. Аналог TreeSet, но для пар с ориентировкой на значения ключей. Для задания правил сортировки TreeMap ключи должны реализовывать Comparable интерфейс. В ином случае должен быть Comparator, ориентированный на ключи (тот, который задается в конструктор TreeMap), TreeSet — реализован с an objectом TreeMap внутри, в котором, собственно, и происходит вся магия.

   Подробнее про сортировку в TreeMap с помощью красно-черных деревьев можно почитать в статье об особенностях TreeMap.

4. Hashtable — аналогичен HashMap, но но не позволяет хранить null ни в качестве ключей, ни в качестве значений. Он тщательно синхронизирован с точки зрения многопоточности, что в свою очередь означает, что он безопасен с точки зрения многопоточности. Но данная реализация устаревшая и медленная, поэтому сейчас вы и не встретите Hashtable в более-менее новых проектах.

8. ArrayList vs LinkedList. Какой предпочтительней использовать?

Questa domanda è forse la più popolare sulle strutture dati e porta con sé alcune insidie. Prima di rispondere, impariamo di più su queste strutture dati. ArrayList implementa l' interfaccia List e opera su un array interno che viene espanso secondo necessità. Quando l'array interno è completamente riempito ed è necessario inserire un nuovo elemento, viene creato un nuovo array con una dimensione di (oldSize * 1.5) +1. Successivamente, tutti i dati del vecchio array vengono copiati nel nuovo + nuovo elemento e quello vecchio verrà eliminato dal Garbage Collector . Il metodo add aggiunge un elemento all'ultima cella vuota dell'array. Cioè, se abbiamo già 3 elementi lì, aggiungerà quello successivo alla quarta cella. Esaminiamo l'esecuzione dei metodi di base:

• get(int indice) - prendere un elemento in un array per indice è il più veloce in O(1) ;
• add(Object obj) - se c'è abbastanza spazio nell'array interno per un nuovo elemento, con un normale inserimento verrà speso O(1) tempo , poiché l'aggiunta è mirata all'ultima cella.

  Se dobbiamo creare un nuovo array e copiarne il contenuto, il nostro tempo sarà direttamente proporzionale al numero di elementi nell'array O(n) ;

• rimuovi(int indice) - quando rimuoviamo un elemento, ad esempio, dal centro, otterremo un tempo O(n/2), poiché dovremo spostare gli elementi a destra di una cella indietro. Di conseguenza, se si cancella dall'inizio dell'elenco, allora O(n), dalla fine - O(1);
• add(int index, Object obj) - una situazione simile all'eliminazione: quando aggiungiamo al centro, dovremo spostare gli elementi a destra di una cella in avanti, quindi il tempo è O(n/2). Naturalmente, dall'inizio - O(n), dalla fine - O(1);
• set(int indice, Oggetto obj) - qui la situazione è diversa, poiché devi solo trovare l'elemento desiderato e scriverci sopra senza spostare il resto, quindi O(1).

Maggiori informazioni su ArrayList in questo articolo . LinkedList implementa due interfacce contemporaneamente: List e Queue e pertanto dispone di proprietà e metodi inerenti a entrambe le strutture dati. Dalla Lista ha avuto accesso all'elemento tramite indice, dalla Coda - dalla presenza di una “testa” e di una “coda”. Internamente, è implementato come una struttura dati che rappresenta un elenco doppiamente collegato. Cioè ogni elemento ha un collegamento con quello successivo e precedente, ad eccezione della “coda” e della “testa”.

• get(int indice) - quando si cerca un elemento che si trova al centro dell'elenco, inizia a cercare tutti gli elementi in ordine finché non viene trovato quello desiderato. Logicamente, la ricerca dovrebbe richiedere O(n/2) , ma LinkedList ha anche una coda, quindi la ricerca viene eseguita simultaneamente da entrambi i lati. Di conseguenza, il tempo si riduce a O(n/4) .

  Se l'elemento è vicino all'inizio dell'elenco o alla fine, il tempo sarà O(1) ;

• add(Object obj) - quando si aggiunge un nuovo elemento, l'elemento "coda" avrà un collegamento all'elemento successivo aggiunto e quello nuovo riceverà un collegamento a questo elemento precedente e diventerà la nuova "coda". Di conseguenza, il tempo sarà O(1) ;
• rimuovi(int indice) - logica simile al metodo get(int indice) . Per rimuovere un elemento dal centro dell'elenco, devi prima trovarlo. Anche questo è O(n/4) , mentre la cancellazione stessa in realtà non richiede nulla, poiché cambia solo il puntatore degli oggetti vicini (iniziano a riferirsi l'uno all'altro). Se l'elemento è all'inizio o alla fine, allora di nuovo - O(1) ;
• add(int indice, Object obj) e set(int indice, Object obj) - i metodi avranno una complessità temporale identica a get(int indice) , poiché la maggior parte del tempo viene spesa nella ricerca dell'elemento. Pertanto, per la metà dell'elenco - O(n/4) , per l'inizio - O(1).

Ulteriori informazioni sull'utilizzo di LinkedList sono descritte in questo articolo . Vediamo tutto questo in una tabella: Come probabilmente hai già capito, è impossibile rispondere a questa domanda in modo inequivocabile. Dopotutto, in diverse situazioni lavorano a velocità diverse. Pertanto, quando ti viene posta una domanda come questa, dovresti immediatamente chiedere su cosa si concentrerà questo elenco e quali operazioni verranno eseguite più spesso. Partendo da questo, date una risposta, ma spiegando perché è così. Riassumiamo il nostro confronto: ArrayList:

• la scelta migliore se l'operazione più frequente è la ricerca di un elemento, sovrascrivendo un elemento;
• la scelta peggiore se l'operazione è di inserimento e cancellazione all'inizio-centro, perché avverranno le operazioni di spostamento degli elementi a destra.

Lista collegata:

• la scelta migliore se la nostra operazione frequente è l'inserimento e la cancellazione all'inizio-metà;
• la scelta peggiore se l'operazione più comune è la ricerca.

9. Come vengono archiviati gli elementi in una HashMap?

La raccolta HashMap contiene una tabella Node[] di array interno , le cui celle sono anche chiamate bucket . Il nodo contiene:

• chiave : collegamento alla chiave,
• valore : riferimento al valore,
• hash - valore hash,
• next - collegamento al nodo successivo .

Una cella dell'array table[] può contenere un riferimento a un oggetto Node con un collegamento al successivo elemento Node , e può avere un collegamento a un altro, e così via... Di conseguenza, questi elementi Node possono formare un lista collegata singolarmente , con elementi con un collegamento al successivo. In questo caso, il valore hash degli elementi di una catena è lo stesso. Dopo una breve digressione, diamo un'occhiata a come gli elementi vengono archiviati in una HashMap :

1. La chiave viene controllata per null . Se è null , la chiave verrà archiviata nella cella table[0] perché il codice hash per null è sempre 0.
2. Se la chiave non è null , viene chiamato il metodo hashcode() dell'oggetto chiave , che restituirà il relativo codice hash. Questo codice hash viene utilizzato per determinare la cella dell'array in cui verrà archiviato l'oggetto Node.
3. Successivamente, questo hashcode viene inserito nel metodo hash() interno , che calcola l'hashcode, ma entro la dimensione dell'array table[] .
4. Successivamente, a seconda del valore hash, Node viene inserito in una cella specifica nell'array table[] .
5. Se la cella table[] utilizzata per salvare l' elemento Node corrente non è vuota, ma contiene già qualche elemento, gli elementi Node vengono ripetuti sul valore successivo fino a raggiungere l'ultimo elemento. Cioè quello il cui campo successivo è null .

   Durante questa ricerca la chiave dell'oggetto Nodo protetto viene confrontata con le chiavi di quello cercato:

   • se viene trovata una corrispondenza, la ricerca terminerà e il nuovo Nodo sovrascriverà il Nodo in cui è stata trovata la corrispondenza (verrà sovrascritto solo il suo campo valore );
   • se non viene trovata alcuna corrispondenza chiave, il nuovo nodo diventerà l'ultimo in questo elenco e quello precedente avrà un collegamento successivo ad esso.

Durante le interviste spesso emerge la domanda: cos'è un conflitto ? La situazione in cui una cella dell'array table[] memorizza non un elemento, ma una catena di due o più, è chiamata collisione . Nei casi normali in cui un solo elemento è memorizzato in una singola cella table[] , l'accesso agli elementi di una HashMap ha una complessità temporale O(1) costante . Ma quando una cella con l'elemento desiderato contiene una catena di elementi ( collisione ), allora O(n) , poiché in questo caso il tempo è direttamente proporzionale al numero di elementi da ordinare.

10. Spiegare l'iteratore

Nel diagramma di mappatura della gerarchia della raccolta riportato sopra, l'interfaccia della raccolta era il punto in cui iniziava l'intera gerarchia, ma in pratica non è proprio così. La raccolta eredita da un'interfaccia con un metodo iterator() , che restituisce un oggetto che implementa l' interfaccia Iterator<E> . L'interfaccia di Iterator è simile alla seguente:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - chiamando questo metodo, puoi ottenere l'elemento successivo. hasNext() - ti permette di scoprire se c'è un elemento successivo e se è stata raggiunta la fine della raccolta. E quando ci sono ancora elementi, hasNext() restituirà true . In genere, hasNext() viene chiamato prima del metodo next() , poiché next() lancerà una NoSuchElementException quando raggiunge la fine della raccolta . rimuovi() - Rimuove l'elemento che è stato recuperato dall'ultima chiamata a next() . Lo scopo di Iterator è scorrere gli elementi. Per esempio:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

In realtà, il ciclo for-each viene implementato dietro le quinte utilizzando un iteratore. Puoi leggere di più a riguardo qui . List fornisce la propria versione di un iteratore, ma più interessante e sofisticato: ListIterator . Questa interfaccia estende Iterator e dispone di metodi aggiuntivi:

• hasPrevious restituirà true se è presente un elemento precedente nella raccolta, false altrimenti;
• precedente restituisce l'elemento corrente e passa a quello precedente; se non ce n'è, viene lanciata una NoSuchElementException;
• add inserirà l'oggetto passato prima dell'elemento che verrà restituito dalla successiva chiamata a next() ;
• set assegna all'elemento corrente un riferimento all'oggetto passato;
• nextIndex restituisce l'indice dell'elemento successivo. Se non esiste nulla di simile, viene restituita la dimensione dell'elenco;
• previousIndex restituisce l'indice dell'elemento precedente. Se non ce n'è, viene restituito il numero -1.

Bene, per me oggi è tutto. Spero che dopo aver letto questo articolo sarai ancora più vicino al tuo caro sogno: diventare uno sviluppatore.