Spørgsmål om Java-samlinger

Denne artikel er en del af en serie: • Spørgsmål til Java Collections Interview (nuværende artikel) • Spørgsmål om Java Type System Interview

• Java-spørgsmål om samtidige samtaler (+ svar)

• Interviewspørgsmål om Java-klassestruktur og initialisering

• Java 8 interviewspørgsmål (+ svar)

• Hukommelsesstyring i Java Interview-spørgsmål (+ svar)

• Interviews med Java Generics (+ svar)

• Interviewspørgsmål til Java Flow Control (+ svar)

• Spørgsmål om Java-undtagelser (+ svar)

• Spørgsmål om Java-annotationer (+ svar)

• Top forårssamarbejdsspørgsmål

1. Introduktion

Java Collections er et emne, der ofte opdrages i tekniske interviews for Java-udviklere. Denne artikel gennemgår nogle vigtige spørgsmål, der ofte stilles og kan være vanskelige at få ret.

2. Spørgsmål

Q1. Beskriv hierarkiets samlingstype. Hvad er de vigtigste grænseflader, og hvad er forskellen mellem dem?

Det Iterabel interface repræsenterer enhver samling, der kan gentages ved hjælp af for hver løkke. Det Kollektion interface arver fra Iterabel og tilføjer generiske metoder til at kontrollere, om et element er i en samling, tilføje og fjerne elementer fra samlingen, bestemme dets størrelse osv.

Det Liste, Sætog grænseflader arver fra Kollektion interface.

Liste er en ordnet samling, og dens elementer kan tilgås ved hjælp af deres indeks på listen.

Sæt er en uordnet samling med forskellige elementer, der ligner den matematiske forestilling om et sæt.

er en samling med yderligere metoder til tilføjelse, fjernelse og undersøgelse af elementer, der er nyttige til tilbageholdelse af elementer før behandling.

Kort grænsefladen er også en del af samlingsrammen, men alligevel udvides den ikke Kollektion. Dette er ved design for at understrege forskellen mellem samlinger og kortlægninger, som er svære at samle under en fælles abstraktion. Det Kort interface repræsenterer en nøgleværdidatastruktur med unikke nøgler og ikke mere end en værdi for hver nøgle.

Q2. Beskriv forskellige implementeringer af kortgrænsefladen og deres forskelle i brugssager.

En af de mest anvendte implementeringer af Kort interface er HashMap. Det er en typisk hash-kort datastruktur, der giver adgang til elementer i konstant tid, eller O (1), men bevarer ikke orden og er ikke trådsikker.

For at bevare elementernes indsætningsrækkefølge kan du bruge LinkedHashMap klasse, der udvider HashMap og binder desuden elementerne til en sammenkædet liste med overskuelige omkostninger.

Det TreeMap klasse gemmer sine elementer i en rød-sort træstruktur, som giver adgang til elementer i logaritmisk tid eller O (log (n)). Det er langsommere end HashMap i de fleste tilfælde, men det giver mulighed for at holde elementerne i orden ifølge nogle Komparator.

Det ConcurrentHashMap er en trådsikker implementering af et hash-kort. Det giver fuld sammenfald af hentninger (som operation medfører ikke låsning) og høj forventet samtidighed af opdateringer.

Det Hashtable klasse har været i Java siden version 1.0. Det er ikke forældet, men betragtes for det meste som forældet. Det er et trådsikkert hash-kort, men i modsætning til det ConcurrentHashMap, alle dens metoder er simpelthen synkroniseret, hvilket betyder, at alle operationer på dette kort blokerer, endda hentning af uafhængige værdier.

Q3. Forklar forskellen mellem Linkedlist og Arraylist.

ArrayList er en implementering af Liste interface, der er baseret på en matrix. ArrayList internt håndterer størrelsen på dette array, når elementerne tilføjes eller fjernes. Du kan få adgang til dets elementer i konstant tid ved hjælp af deres indeks i arrayet. Hvis du indsætter eller fjerner et element, skifter det imidlertid alle de efterfølgende elementer, der kan være langsomme, hvis arrayet er stort, og det indsatte eller fjernede element er tæt på begyndelsen af ​​listen.

LinkedList er en dobbeltkoblet liste: enkeltelementer indsættes Node objekter, der har henvisninger til forrige og næste Node. Denne implementering kan virke mere effektiv end ArrayList hvis du har mange indsættelser eller sletninger i forskellige dele af listen, især hvis listen er stor.

I de fleste tilfælde er ArrayList udkonkurrerer LinkedList. Selv elementer, der skifter ind ArrayList, mens det er en O (n) -operation, implementeres det som en meget hurtig System.arraycopy () opkald. Det kan endda se hurtigere ud end LinkedList'S O (1) indsættelse, som kræver øjeblikkelig a Node modsætning og opdatering af flere referencer under emhætten. LinkedList kan også have en stor hukommelsesomkostning på grund af oprettelse af flere små Node genstande.

Q4. Hvad er forskellen mellem Hashset og Treeset?

Begge HashSet og TreeSet klasser implementerer Sæt interface og repræsenterer sæt af forskellige elementer. Derudover TreeSet implementerer NavigableSet interface. Denne grænseflade definerer metoder, der udnytter rækkefølgen af ​​elementer.

HashSet er internt baseret på en HashMapog TreeSet er bakket op af en TreeMap eksempel, der definerer deres egenskaber: HashSet holder ikke elementer i en bestemt rækkefølge. Iteration over elementerne i a HashSet producerer dem i en blandet rækkefølge. TreeSetderimod producerer elementer i rækkefølge ifølge nogle foruddefinerede Komparator.

Q5. Hvordan implementeres Hashmap i Java? Hvordan bruger dens implementering Hashcode og ligemetoder til objekter? Hvad er tidskompleksiteten ved at sætte og få et element fra en sådan struktur?

Det HashMap klasse repræsenterer en typisk hash-kort datastruktur med visse designvalg.

Det HashMap er bakket op af en størrelse, der kan ændres, der har størrelsen power-of-two. Når elementet føjes til a HashMap, først dens hashCode beregnes (en int værdi). Derefter bruges et bestemt antal lavere bits af denne værdi som et arrayindeks. Dette indeks peger direkte på cellen i arrayet (kaldet en bucket), hvor dette nøgleværdipar skal placeres. Adgang til et element ved dets indeks i en matrix er en meget hurtig O (1) -operation, som er hovedfunktionen i en hash-kortstruktur.

EN hashCode er dog ikke unik og endda for forskellige hashCodes, modtager vi muligvis den samme matrixposition. Dette kaldes en kollision. Der er mere end en måde at løse kollisioner i hash-kortdatastrukturer på. I Java'er HashMap, hver spand refererer faktisk ikke til et enkelt objekt, men til et rød-sort træ af alle objekter, der landede i denne spand (før Java 8 var dette en sammenkædet liste).

Så når HashMap har bestemt skovlen for en nøgle, den skal krydse dette træ for at sætte nøgleværdiparet på plads. Hvis der allerede findes et par med en sådan nøgle i skovlen, erstattes det med en ny.

For at hente objektet ved hjælp af dets nøgle, HashMap igen skal beregne hashCode for nøglen, find den tilsvarende skovl, krydse træet, ring lige med på nøglerne i træet og find den matchende.

HashMap har O (1) kompleksitet eller konstant tidskompleksitet ved at sætte og få elementerne. Selvfølgelig kunne mange kollisioner i værste fald nedbryde ydeevnen til O (log (n)) tidskompleksitet, når alle elementer lander i en enkelt spand. Dette løses normalt ved at give en god hashfunktion med en ensartet fordeling.

Når HashMap intern array er udfyldt (mere om det i det næste spørgsmål), ændres den automatisk til at være dobbelt så stor. Denne operation er baseret på genvaskning (genopbygning af interne datastrukturer), hvilket er dyrt, så du skal planlægge størrelsen på din HashMap på forhånd.

Q6. Hvad er formålet med de indledende parametre for kapacitet og belastningsfaktor for en Hashmap? Hvad er deres standardværdier?

Det initialCapacity argument af HashMap konstruktør påvirker størrelsen på den interne datastruktur HashMap, men at argumentere for den aktuelle størrelse på et kort er lidt vanskelig. Det HashMap'S interne datastruktur er en matrix med magt-to-størrelse. Så initialCapacity argumentværdien øges til næste power-of-two (hvis du f.eks. indstiller den til 10, vil den faktiske størrelse af det interne array være 16).

Belastningsfaktoren for a HashMap er forholdet mellem elementtællingen divideret med antallet af skovle (dvs. intern arraystørrelse). For eksempel, hvis en 16-spand HashMap indeholder 12 elementer, dens belastningsfaktor er 12/16 = 0,75. En høj belastningsfaktor betyder mange kollisioner, hvilket igen betyder, at kortet skal ændres til den næste effekt på to. Så belastningsfaktor argument er en maksimal værdi af belastningsfaktoren på et kort. Når kortet opnår denne belastningsfaktor, ændres størrelsen på det interne array til den næste power-of-two-værdi.

Det initialCapacity er 16 som standard, og loadFactor er som standard 0,75, så du kan placere 12 elementer i en HashMap der blev instantieret med standardkonstruktøren, og det ville ikke ændre størrelsen. Det samme gælder for HashSet, som er bakket op af en HashMap eksempel internt.

Derfor er det ikke trivielt at komme med initialCapacity der tilfredsstiller dine behov. Dette er grunden til, at Guava-biblioteket har Maps.newHashMapWithExpectedSize () og Sets.newHashSetWithExpectedSize () metoder, der giver dig mulighed for at opbygge en HashMap eller a HashSet der kan rumme det forventede antal elementer uden at ændre størrelsen.

Q7. Beskriv specielle samlinger til enums. Hvad er fordelene ved deres implementering sammenlignet med regelmæssige samlinger?

EnumSet og EnumMap er specielle implementeringer af Sæt og Kort grænseflader tilsvarende. Du skal altid bruge disse implementeringer, når du har at gøre med enums, fordi de er meget effektive.

En EnumSet er bare en smule vektor med "en" i positionerne svarende til ordinære værdier af enums til stede i sættet. For at kontrollere, om en enumværdi er i sættet, skal implementeringen simpelthen kontrollere, om den tilsvarende bit i vektoren er en “en”, hvilket er en meget nem betjening. Tilsvarende an EnumMap er en matrix med enums ordinale værdi som et indeks. I tilfælde af EnumMap, er der ikke behov for at beregne hash-koder eller løse kollisioner.

Q8. Hvad er forskellen mellem svigtende og svigtende itteratorer?

Iteratorer til forskellige samlinger er enten fail-hurtige eller fail-safe afhængigt af hvordan de reagerer på samtidige ændringer. Den samtidige ændring er ikke kun en ændring af samlingen fra en anden tråd, men også ændring fra den samme tråd, men ved hjælp af en anden iterator eller ændring af samlingen direkte.

Fejler hurtigt iteratorer (dem, der returneres af HashMap, ArrayList, og andre ikke-trådsikre samlinger) gentages over samlingens interne datastruktur, og de kaster ConcurrentModificationException så snart de registrerer en samtidig ændring.

Fejlsikker iteratorer (returneret af trådsikre samlinger som f.eks ConcurrentHashMap, CopyOnWriteArrayList) oprette en kopi af den struktur, de gentager. De garanterer sikkerhed fra samtidige ændringer. Deres ulemper inkluderer overdrevent hukommelsesforbrug og iteration over muligvis forældede data, hvis samlingen blev ændret.

Q9. Hvordan kan du bruge sammenlignelige og komparatorgrænseflader til at sortere samlinger?

Det Sammenlignelig interface er et interface til objekter, der kan sammenlignes efter en rækkefølge. Dens eneste metode er sammenligne med, der fungerer på to værdier: selve objektet og argumentobjektet af samme type. For eksempel, Heltal, Langog andre numeriske typer implementerer denne grænseflade. Snor implementerer også denne grænseflade og dens sammenligne med metode sammenligner strenge i leksikografisk rækkefølge.

Det Sammenlignelig interface giver mulighed for at sortere lister over tilsvarende objekter med Collections.sort () metode og opretholde iterationsrækkefølgen i samlinger, der implementeres SortedSet og SortedMap. Hvis dine objekter kan sorteres ved hjælp af en eller anden logik, skal de implementere Sammenlignelig interface.

Det Sammenlignelig interface implementeres normalt ved hjælp af naturlig rækkefølge af elementerne. For eksempel alle Heltal tal ordnes fra mindre til større værdier. Men nogle gange vil du muligvis implementere en anden slags ordning, for eksempel for at sortere numrene i faldende rækkefølge. Det Komparator interface kan hjælpe her.

Klassen af ​​de objekter, du vil sortere, behøver ikke at implementere denne grænseflade. Du opretter simpelthen en implementeringsklasse og definerer sammenligne metode, der modtager to objekter og beslutter, hvordan de skal bestilles. Du kan derefter bruge forekomsten af ​​denne klasse til at tilsidesætte den naturlige rækkefølge af Collections.sort () metode eller SortedSet og SortedMap tilfælde.

Som den Komparator interface er en funktionel interface, du kan erstatte den med et lambda-udtryk, som i det følgende eksempel. Det viser bestilling af en liste ved hjælp af en naturlig rækkefølge (Heltal'S Sammenlignelig interface) og ved hjælp af en brugerdefineret iterator (Komparator interface).

Liste liste1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (liste1); assertEquals (nyt heltal (1), list1.get (0)); Liste liste1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (liste1, (a, b) -> b - a); assertEquals (nyt heltal (5), list1.get (0));
Næste » Java Type System Interview Spørgsmål