Pitanja za intervju za Java Collections

Ovaj je članak dio serije: • Pitanja za intervju za Java Collections (trenutni članak) • Pitanja za intervju za sustav Java Type

• Pitanja za intervju s Java-om (+ odgovori)

• Struktura Java razreda i pitanja za intervju za inicijalizaciju

• Java 8 pitanja za intervju (+ odgovori)

• Upravljanje memorijom u Java intervjuu Pitanja (+ odgovori)

• Pitanja o intervjuu za Java Generics (+ odgovori)

• Pitanja za intervju s Java Flow Control (+ odgovori)

• Pitanja o intervjuu za iznimke Java (+ odgovori)

• Pitanja za intervju s Java Annotations (+ odgovori)

• Najpopularnija pitanja za proljetni okvirni intervju

1. Uvod

Java Collections tema je koja se često pokreće u tehničkim intervjuima za programere Java. Ovaj članak daje pregled nekih važnih pitanja koja se najčešće postavljaju i koja mogu biti nezgodna za ispravljanje.

2. Pitanja

Q1. Opišite hijerarhiju tipa zbirki. Koja su glavna sučelja i koje su razlike između njih?

The Iterativ sučelje predstavlja bilo koju kolekciju koja se može ponoviti pomoću za svakoga petlja. The Kolekcija sučelje nasljeđuje od Iterativ i dodaje generičke metode za provjeru nalazi li se element u zbirci, dodavanje i uklanjanje elemenata iz zbirke, određivanje njegove veličine itd.

The Popis, Postavi, i Red sučelja nasljeđuju iz Kolekcija sučelje.

Popis je uređena zbirka, a njezinim elementima može se pristupiti njihovim indeksom na popisu.

Postavi je neuređena zbirka s različitim elementima, slična matematičkom pojmu skupa.

Red je zbirka s dodatnim metodama za dodavanje, uklanjanje i ispitivanje elemenata, korisnih za držanje elemenata prije obrade.

Karta sučelje je također dio okvira za prikupljanje, ali se ne proširuje Kolekcija. Ovo je dizajnirano kako bi se naglasila razlika između zbirki i mapiranja koja je teško sakupiti pod zajedničkom apstrakcijom. The Karta sučelje predstavlja strukturu podataka ključ / vrijednost s jedinstvenim ključevima i ne više od jedne vrijednosti za svaki ključ.

Q2. Opišite različite implementacije sučelja karte i njihove razlike u upotrebi.

Jedna od najčešće korištenih implementacija Karta sučelje je HashMap. To je tipična struktura podataka hash mape koja omogućuje pristup elementima u konstantnom vremenu, ili O (1), ali ne čuva red i nije zaštićen niti.

Da biste sačuvali redoslijed umetanja elemenata, možete koristiti LinkedHashMap klasa koja proširuje HashMap i dodatno povezuje elemente u povezani popis s predvidljivim općim troškovima.

The TreeMap class pohranjuje svoje elemente u crveno-crnu strukturu stabla, koja omogućava pristup elementima u logaritamskom vremenu ili O (log (n)). Sporiji je od HashMap u većini slučajeva, ali prema nekima omogućuje održavanje elemenata u redu Usporednik.

The ConcurrentHashMap je nit implementacija hash mape. Pruža potpunu istodobnost pretraživanja (kao dobiti operacija ne uključuje zaključavanje) i visoko očekivanu istodobnost ažuriranja.

The Hashtable class je na Javi od verzije 1.0. Nije zastario, ali uglavnom se smatra zastarjelim. To je hash karta zaštićena nitima, ali za razliku od nje ConcurrentHashMap, sve njegove metode su jednostavno sinkronizirano, što znači da sve radnje na ovoj karti blokiraju, čak i preuzimanje neovisnih vrijednosti.

Q3. Objasnite razliku između Linkedlista i Arraylista.

ArrayList je provedba Popis sučelje koje se temelji na nizu. ArrayList interno obrađuje promjenu veličine ovog polja kada se dodaju ili uklone elementi. Njegovim elementima možete pristupiti u stalnom vremenu prema njihovom indeksu u nizu. Međutim, umetanje ili uklanjanje elementa rezultira pomicanjem svih posljedičnih elemenata, što može biti sporo ako je niz ogroman, a umetnuti ili uklonjeni element blizu početka popisa.

LinkedList je dvostruko povezan popis: u njega se stavljaju pojedini elementi Čvor objekti koji imaju reference na prethodni i sljedeći Čvor. Ova implementacija može se činiti učinkovitijom od ArrayList ako imate puno umetanja ili brisanja u različitim dijelovima popisa, posebno ako je popis velik.

U većini slučajeva, međutim, ArrayList nadmašuje LinkedList. Čak se i elementi prebacuju ArrayList, iako je operacija O (n), provodi se vrlo brzo System.arraycopy () poziv. Može se čak pojaviti i brže od LinkedList'S O (1) umetanje koje zahtijeva instanciranje a Čvor objekt i ažuriranje više referenci ispod napa. LinkedList također može imati veliku režiju memorije zbog stvaranja više malih Čvor predmeta.

Q4. Koja je razlika između skupova podataka i skupova stabala?

Oba HashSet i TreeSet klase provode Postavi sučelje i predstavljaju skupove različitih elemenata. Dodatno, TreeSet provodi NavigableSet sučelje. Ovo sučelje definira metode koje iskorištavaju poredak elemenata.

HashSet interno se temelji na a HashMap, i TreeSet iza kojeg stoji a TreeMap instance koja definira njihova svojstva: HashSet ne drži elemente u bilo kojem određenom redoslijedu. Ponavljanje elemenata u a HashSet proizvodi ih promiješanim redoslijedom. TreeSet, s druge strane, proizvodi elemente redom prema nekim unaprijed definiranim Usporednik.

P5. Kako se Hashmap implementira u Javi? Kako se njegova implementacija koristi heškodom i jednakim metodama objekata? Kolika je vremenska složenost stavljanja i dobivanja elementa iz takve strukture?

The HashMap klasa predstavlja tipičnu strukturu podataka hash mape s određenim izborima dizajna.

The HashMap je potpomognut promjenjivim nizom veličine 2. Kada se element doda u HashMap, prvo svoje hashCode izračunava se (an int vrijednost). Tada se određeni broj donjih bitova ove vrijednosti koristi kao indeks niza. Ovaj indeks izravno pokazuje na ćeliju niza (koja se naziva segmentiranje) u koju treba smjestiti ovaj par ključ / vrijednost. Pristup elementu pomoću njegovog indeksa u nizu vrlo je brza operacija O (1), što je glavna značajka strukture hash mape.

A hashCode nije jedinstven, pa čak i za različite hashCodes, možemo primiti isti položaj niza. To se naziva sudarom. Postoji više od jednog načina rješavanja sudara u strukturama podataka hash mape. U Javi HashMap, svaki se segment zapravo ne odnosi na jedan objekt, već na crveno-crno stablo svih objekata koji su se spustili u taj segment (prije Java 8, ovo je bio povezani popis).

Pa kad HashMap je odredio skup za ključ, mora preći ovo stablo kako bi stavio par ključ / vrijednost na njegovo mjesto. Ako par s takvim ključem već postoji u segmentu, zamjenjuje se novim.

Za dohvaćanje objekta pomoću ključa, HashMap opet mora izračunati hashCode za ključ pronađite odgovarajuću kantu, pređite drvo, nazovite jednako na tipkama na drvetu i pronađite onaj koji odgovara.

HashMap ima O (1) složenost ili konstantnu složenost stavljanja i dobivanja elemenata. Naravno, puno sudara moglo bi smanjiti performanse na vremensku složenost O (log (n)) u najgorem slučaju, kada svi elementi sletnu u jednu kantu. To se obično rješava pružanjem dobre hash funkcije s jednolikom raspodjelom.

Kada HashMap popunjava se unutarnji niz (više o tome u sljedećem pitanju), automatski mu se smanjuje veličina kako bi bio dvostruko veći. Ova operacija rezultira ponovnim osmišljavanjem (ponovnom izgradnjom unutarnjih struktura podataka), što je skupo, pa biste trebali planirati veličinu svojeg HashMap unaprijed.

P6. Koja je svrha parametara početnog kapaciteta i faktora opterećenja hash-mape? Koje su njihove zadane vrijednosti?

The početni kapacitet argument HashMap konstruktor utječe na veličinu unutarnje strukture podataka HashMap, ali razmišljanje o stvarnoj veličini karte pomalo je nezgodno. The HashMapInterna struktura podataka je niz snage dvije veličine. Dakle početni kapacitet vrijednost argumenta povećava se na sljedeću snagu dva (na primjer, ako je postavite na 10, stvarna veličina unutarnjeg polja bit će 16).

Faktor opterećenja od a HashMap je omjer broja elemenata podijeljen s brojem segmenata (tj. veličina unutarnjeg polja). Na primjer, ako 16-kanta HashMap sadrži 12 elemenata, faktor opterećenja mu je 12/16 = 0,75. Visok faktor opterećenja znači puno sudara, što zauzvrat znači da bi se karta trebala promijeniti na sljedeću snagu od dva. Dakle loadFactor argument je maksimalna vrijednost faktora opterećenja karte. Kada karta postigne ovaj faktor opterećenja, ona svoj unutarnji niz mijenja na sljedeću vrijednost snage dva.

The početni kapacitet je prema zadanim postavkama 16, a loadFactor je 0,75 prema zadanim postavkama, tako da biste mogli staviti 12 elemenata u HashMap koja je instancirana sa zadanim konstruktorom i neće joj se promijeniti veličina. Isto vrijedi i za HashSet, iza kojeg stoji a HashMap primjerice interno.

Slijedom toga, nije trivijalno to smisliti početni kapacitet koji zadovoljava vaše potrebe. Zbog toga knjižnica Guava ima Maps.newHashMapWithExpectedSize () i Sets.newHashSetWithExpectedSize () metode koje vam omogućuju izgradnju a HashMap ili a HashSet koji može sadržavati očekivani broj elemenata bez promjene veličine.

P7. Opišite posebne zbirke za Enume. Koje su blagodati njihove primjene u usporedbi s redovnim prikupljanjem?

EnumSet i EnumMap su posebne implementacije Postavi i Karta sučelja sukladno tome. Uvijek biste trebali koristiti ove implementacije kada imate posla s enumima jer su vrlo učinkovite.

An EnumSet je samo bitni vektor s "one" na pozicijama koje odgovaraju rednim vrijednostima nabrajanja prisutnih u skupu. Da bi provjerila je li vrijednost enum u skupu, implementacija jednostavno mora provjeriti je li odgovarajući bit u vektoru "jedan", što je vrlo jednostavna operacija. Slično tome, an EnumMap je niz kojem se pristupa s rednom vrijednošću enuma kao indeksa. U slučaju EnumMap, nema potrebe za izračunavanjem hash kodova ili rješavanjem sudara.

P8. Koja je razlika između ubrzanih i otpornih iteratora?

Iteratori za različite zbirke su ili brzi ili sigurni, ovisno o tome kako reagiraju na istodobne modifikacije. Istodobna modifikacija nije samo modifikacija kolekcije iz druge niti, već i modifikacija iz iste niti, ali pomoću drugog iteratora ili izravna modifikacija kolekcije.

Neuspješno iteratori (oni koje je vratio HashMap, ArrayListi druge kolekcije koje nisu sigurne u niti) prelaze kroz unutarnju strukturu podataka zbirke i bacaju ConcurrentModificationException čim otkriju istodobnu modifikaciju.

Sigurno iteratori (vraćaju ih kolekcije zaštićene nitima kao što su ConcurrentHashMap, CopyOnWriteArrayList) stvoriti kopiju strukture koju ponavljaju. Jamče sigurnost od istodobnih preinaka. Njihovi nedostaci uključuju prekomjernu potrošnju memorije i ponavljanje moguće zastarjelih podataka u slučaju da je zbirka izmijenjena.

P9. Kako možete koristiti usporediva i usporedna sučelja za sortiranje zbirki?

The Usporedive sučelje je sučelje za objekte koji se mogu usporediti prema nekom redoslijedu. Njegova jedina metoda je usporediTo, koji djeluje na dvije vrijednosti: sam objekt i objekt argumenta iste vrste. Na primjer, Cijeli broj, Dugoi drugi numerički tipovi implementiraju ovo sučelje. Niz također implementira ovo sučelje i njegovo usporediTo metoda uspoređuje žice leksikografskim redoslijedom.

The Usporedive sučelje omogućuje sortiranje popisa odgovarajućih objekata pomoću Collections.sort () metodu i podržavaju redoslijed ponavljanja u zbirkama koje se implementiraju SortedSet i SortedMap. Ako se vaši objekti mogu sortirati pomoću neke logike, trebali bi implementirati Usporedive sučelje.

The Usporedive sučelje se obično provodi prirodnim uređenjem elemenata. Na primjer, svi Cijeli broj brojevi su poredani od manjih prema većim vrijednostima. No ponekad ćete možda htjeti primijeniti drugu vrstu naručivanja, na primjer, za sortiranje brojeva u silaznom redoslijedu. The Usporednik sučelje ovdje može pomoći.

Klasa objekata koje želite sortirati ne treba implementirati ovo sučelje. Jednostavno stvorite izvedbenu klasu i definirate usporedi metoda koja prima dva predmeta i odlučuje kako ih naručiti. Tada možete upotrijebiti instancu ove klase da nadjačate prirodni poredak Collections.sort () metoda ili SortedSet i SortedMap instance.

Kao Usporednik sučelje je funkcionalno sučelje, možete ga zamijeniti lambda izrazom, kao u sljedećem primjeru. Prikazuje naručivanje popisa pomoću prirodnog redoslijeda (Cijeli broj‘S Usporedive sučelje) i pomoću prilagođenog iteratora (Usporednik sučelje).

Lista popisa1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (list1); assertEquals (novi Integer (1), list1.get (0)); Lista popisa1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (list1, (a, b) -> b - a); assertEquals (novi Integer (5), list1.get (0));
Sljedeći » Pitanja o intervjuu za sustav tipa Java