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

Ciao! Quante ore ci vogliono per diventare un maestro in qualcosa? Spesso ho sentito qualcosa del tipo: “Per diventare un maestro in qualsiasi cosa, devi dedicarci 10.000 ore”. Un numero spaventoso, non è vero? Tuttavia mi chiedo: questo è vero? E cerco costantemente di capire quante ore ho già investito nel padroneggiare l'arte della programmazione. E quando supererò quelle amate 10.000 ore e diventerò un maestro, sentirò questa differenza? Oppure li ho già scavalcati da tempo senza rendermene conto? In un modo o nell'altro, per diventare un programmatore, non è necessario investire una quantità di tempo così grande. La cosa principale è usarlo saggiamente. Il tuo obiettivo principale è superare il colloquio. E ai colloqui per i nuovi arrivati, la prima cosa che chiedono è la teoria, quindi devi essere forte in essa. In realtà, quando ti prepari per il colloquio, il tuo compito è scoprire tutte le tue lacune nella teoria di base di uno sviluppatore Java e colmarle con la conoscenza. E oggi ti aiuterò in questa faccenda, perché sono qui per continuare ad analizzare le domande più gettonate. Quindi continuiamo!

89. In che modo ArrayList è diverso da LinkedList?

Questa è una delle domande più popolari insieme alla domanda sulla struttura interna di HashMap . Nessuna intervista è completa senza di essa, e quindi la risposta dovrebbe "rimbalzare sui denti". Oltre all'ovvio - nomi diversi - differiscono nella struttura interna. In precedenza abbiamo esaminato la struttura interna sia di ArrayList che di LinkedList , quindi non entrerò nei dettagli della loro implementazione. Permettetemi solo di ricordarvi che ArrayList è implementato sulla base di un array interno, che viene aumentato secondo necessità secondo la formula:

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

Allo stesso tempo, LinkedList è implementato sulla base di una lista interna doppiamente collegata, cioè ogni elemento ha un collegamento con il precedente e il successivo, esclusi i valori che sono l'inizio/fine della lista. Alla gente piace porre questa domanda nel formato: "Qual è il migliore: ArrayList o LinkedList ?", sperando di catturarti. Dopotutto, se ne indichi una come risposta, sarà la risposta sbagliata. Dovresti invece chiarire di quale situazione specifica stai parlando: accesso all'indice o inserimento nel mezzo di un elenco. A seconda della risposta potrai motivare la tua scelta. In precedenza ho descritto come funzionano ArrayList e LinkedList in una situazione o nell'altra. Riassumiamolo mettendoli sulla stessa pagina per il confronto: Aggiunta di un elemento (aggiungi)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

In conclusione: in LinkedList, la complessità algoritmica varierà da O(1) a O(n/2) . Cioè, quanto più l'inserimento è vicino alla fine o all'inizio dell'elenco, tanto più veloce sarà. Allo stesso tempo, per ArrayList va da O(1) a O(n) : più l'inserimento è vicino alla fine della lista, più è veloce. Impostazione di un elemento (set) Questa operazione scrive un elemento nella posizione specificata nella lista, sovrascrivendo quello precedente, se presente. In LinkedList, questa operazione sarà simile all'aggiunta, perché La difficoltà più grande qui è trovare l'elemento. La riscrittura di un elemento avverrà riscrivendo una coppia di link, quindi anche qui la complessità algoritmica varierà da O(1) a O(n/2) a seconda della distanza della posizione dalla fine o dall'inizio della lista. A quel punto, la cella richiesta verrà trovata nell'ArrayList per questa operazione sull'indice e su di essa verrà scritto un nuovo elemento. La ricerca dell'indice, come questa operazione, ha una complessità algoritmica di O(1) . Prendi un elemento per indice (get) In LinkedList, la presa di un elemento avverrà secondo lo stesso principio della ricerca di altre operazioni, a seconda della distanza dalla fine o dall'inizio, ad es. da O(1) a O(n/2) . In ArrayList , come ho detto prima, trovare un elemento in un array per indice ha complessità O(1) . Rimuovi un elemento per indice (rimuovi) Per LinkedList, il suo principio di funzionamento funziona anche qui: prima viene trovato l'elemento, quindi i collegamenti vengono sovrascritti: i vicini dell'elemento iniziano a riferirsi tra loro, perdendo i riferimenti a questo elemento, che verrà successivamente eliminato dal Garbage Collector. Cioè, la complessità algoritmica è sempre la stessa: da O(1) a O(n/2) . Per ArrayList , questa operazione è più simile all'operazione di aggiunta di un nuovo elemento (add). Innanzitutto, viene trovato l'elemento richiesto - O(1) , quindi viene rimosso e tutti gli elementi che erano alla sua destra vengono spostati di un'unità a sinistra per colmare il divario risultante. L'operazione di eliminazione avrà la stessa complessità algoritmica dell'operazione di aggiunta: da O(1) a O(n) . Più l'eliminazione è vicina alla fine dell'elenco, minore è la complessità algoritmica. In realtà, queste erano tutte le operazioni principali. Lascia che te lo ricordi: quando confronti questi due elenchi, devi chiarire di quale situazione specifica stiamo parlando, e quindi puoi rispondere in modo inequivocabile alla domanda posta.

90. In che modo ArrayList è diverso da HashSet?

Se ArrayList e LinkedList potessero essere confrontati in termini di operazioni - il che è meglio - allora non sarebbe così facile confrontare ArrayList con HashSet , perché si tratta di raccolte completamente diverse. Puoi confrontare un piatto dolce con un altro, ma funzionerà con un piatto di carne: sono troppo diversi. Tuttavia, proverò a fornire alcune differenze tra loro:

• ArrayList implementa l' interfaccia List , mentre HashSet implementa l' interfaccia Set ;

• In ArrayList l'accesso è possibile tramite l'indice dell'elemento: l' operazione get ha una complessità algoritmica di O(1) , e in HashSet l'elemento richiesto può essere ottenuto solo con la forza bruta, e questo va da O(1) a O(n) ;

• ArrayList consente elementi duplicati. In un HashSet tutti gli elementi sono unici: aggiungere a un HashSet un elemento il cui analogo è già presente nella collezione non funzionerà (i duplicati vengono controllati utilizzando hashcode, da cui il nome di questa collezione);

• ArrayList viene implementato utilizzando un array interno e HashSet viene implementato utilizzando un HashMap interno ;

• Un ArrayList mantiene l'ordine di inserimento degli elementi, mentre un HashSet è un insieme non ordinato e non mantiene l'ordine degli elementi;

• ArrayList consente un numero qualsiasi di valori vuoti (null), solo un valore null può essere inserito in un HashSet (dopo tutto, l'unicità degli elementi).

91. Perché esiste una tale varietà di implementazioni di array dinamici in Java?

Bene, questa è più una questione filosofica. Ebbene, perché inventano così tante nuove tecnologie diverse? Per comodità. In realtà, è lo stesso con un gran numero di implementazioni di array dinamici. Nessuno di loro può essere definito il migliore o l'ideale. Ognuno ha un vantaggio in alcune situazioni specifiche. E il nostro compito è conoscerne le differenze, i punti di forza/debolezza: per poter utilizzare quello più adatto nella giusta situazione.

92. Perché esiste una tale varietà di implementazioni di archiviazione di valori-chiave in Java?

Qui la situazione è la stessa delle implementazioni di array dinamici. Non esiste il migliore: ognuno ha pregi e difetti. E noi, ovviamente, dobbiamo sfruttare al massimo le nostre forze. Esempio: il pacchetto concurrent, che contiene molte tecnologie multi-thread, ha le proprie raccolte Concurrent . La stessa ConcurrentHashMap ha un vantaggio nella sicurezza del lavoro multithread con i dati rispetto a una HashMap normale , ma in un ambiente non multithread perde velocità. Bene, le implementazioni, che non sono le più forti in nessuna situazione, vengono gradualmente interrotte. Esempio: Hashtable , che originariamente doveva essere un HashMap thread-safe , ma ConcurrentHashMap lo ha sovraperformato in un ambiente multi-thread e alla fine Hashtable è stato dimenticato e non più utilizzato.

93. Come ordinare una raccolta di elementi?

La prima cosa da dire è che la classe dell'elemento collection deve implementare l' interfaccia Comparable e il suo metodo compareTo . Oppure hai bisogno di una classe che implementi Comaprator con il suo metodo comparatore . Puoi leggere di più su di loro in questo post . Entrambi i metodi specificano come devono essere confrontati gli oggetti di un determinato tipo. Durante l'ordinamento, questo è di fondamentale importanza, perché è necessario comprendere il principio in base al quale gli elementi possono essere confrontati. Il modo principale per farlo è implementare Comparable , implementato direttamente nella classe che si desidera ordinare. Allo stesso tempo, l'uso del comparatore è meno comune. Diciamo che stai utilizzando una classe da una libreria che non ha un'implementazione Comparable , ma dovrai ordinarla in qualche modo. Senza poter modificare il codice di questa classe (se non estendendolo), puoi scrivere un'implementazione di Comparator , in cui indichi in base a quale principio desideri confrontare gli oggetti di questa classe. E un altro esempio. Supponiamo che tu abbia bisogno di principi diversi per ordinare oggetti dello stesso tipo, quindi scrivi diversi comparatori da utilizzare in situazioni diverse. Di norma, molte classi implementano già l' interfaccia Comparable , la stessa String . In realtà, quando li usi, non devi preoccuparti di come confrontarli. Basta prenderli e usarli. Il primo e più ovvio modo è utilizzare una raccolta di tipo TreeSet o TreeMap , che memorizza gli elementi già ordinati in base al comparatore di classi di elementi. Ricorda che TreeMap ordina le chiavi, ma non i valori. Se utilizzi l' implementazione Comparator invece di Comparable , dovrai passare il suo oggetto al costruttore della raccolta al momento della creazione:

TreeSet treeSet = new TreeSet(customComparator);

Ma cosa succede se hai un diverso tipo di collezione? Come ordinarlo? In questo caso, è adatto il secondo metodo della classe di utilità Collections : il metodo sort() . È statico, quindi tutto ciò che serve è il nome della classe e un metodo a cui viene passato l'elenco richiesto. Per esempio:

Collections.sort(someList);

Se non stai utilizzando Comparable , ma piuttosto un'implementazione di Comparator , devi passarlo come secondo parametro:

Collections.sort(someList, customComparator);

Di conseguenza, l'ordine interno degli elementi della lista passata cambierà: sarà ordinato in base al comparatore di elementi. Prendo atto che l'elenco degli elementi trasferiti deve essere mutabile, ovvero mutabile, altrimenti il ​​metodo non funzionerà e verrà lanciata un'eccezione UnsupportedOperationException . Come terzo modo è possibile utilizzare l' operazione Stream sort , che ordina gli elementi della collection se viene utilizzata l' implementazione Comparable :

someList = someList.stream().sorted().collect(Collectors.toList());

se comparatore :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Puoi leggere ulteriori informazioni su Stream in questo articolo . Il quarto metodo consiste nell'implementare manualmente l'ordinamento, come il bubble sort o il merge sort .

ClasseOggetto. Uguale e HashCode

94. Fornire una breve descrizione dell'oggetto classe in Java

Nella seconda parte dell'analisi abbiamo già parlato dei metodi della classe Object , e ti ricordo che la classe Object è la capostipite di tutte le classi Java. Ha 11 metodi che, di conseguenza, vengono ereditati da tutte le classi. Le informazioni su tutti gli 11 metodi possono essere trovate nella seconda parte della discussione.

95. A cosa servono Equals e HashCode in Java?

hashCode() è un metodo della classe Object ereditato da tutte le classi. Il suo compito è generare un numero che rappresenti un oggetto specifico. Un esempio di utilizzo di questo metodo è il suo utilizzo in una HashMap su un oggetto chiave per determinare ulteriormente l'hashcode locale, che determinerà la cella dell'array interno (bucket) in cui verrà archiviata la coppia. Abbiamo parlato in dettaglio del lavoro di HashMap nella parte 9 dell’analisi , quindi non ci soffermeremo troppo su questo. Inoltre, di norma, questo metodo viene utilizzato nel metodo equals() come uno dei suoi strumenti principali per determinare l'identità degli oggetti. equals() è un metodo della classe Object il cui compito è confrontare gli oggetti e determinare se sono uguali o meno. Questo metodo viene utilizzato ovunque sia necessario confrontare oggetti, perché il solito confronto tramite == non è adatto per gli oggetti, perché confronta solo i collegamenti ad essi.

96. Ci parli del contratto tra Equals e HashCode in Java?

La prima cosa che dirò è che affinché i metodi equals() e hashCode() funzionino correttamente , devono essere sovrascritti correttamente. Successivamente devono seguire le regole:

• oggetti identici per i quali il confronto tramite uguale restituisce true devono avere gli stessi codici hash ;
• gli oggetti con gli stessi codici hash potrebbero non essere sempre uguali.

A questo punto ci fermeremo alla parte successiva dell'analisi!