Intervju spørsmål om Java Collections
• Java-samtalespørsmål om samtidighet (+ svar)
• Spørsmål om Java-klassestruktur og initialisering
• Java 8 intervjuspørsmål (+ svar)
• Minnehåndtering i Java-intervjuspørsmål (+ svar)
• Java Generics intervjuspørsmål (+ svar)
• Intervju med Java Flow Control (+ svar)
• Java-unntaksspørsmål (+ svar)
• Spørsmål om Java-merknader (+ svar)
• Spørsmål om topp vårrammeverk
1. Introduksjon
Java Collections er et tema som ofte blir tatt opp på tekniske intervjuer for Java-utviklere. Denne artikkelen gjennomgår noen viktige spørsmål som ofte blir stilt, og som kan være vanskelig å få rett.
2. Spørsmål
Q1. Beskriv hierarkiet for samlingstype. Hva er de viktigste grensesnittene, og hva er forskjellen mellom dem?
De Iterabel grensesnittet representerer enhver samling som kan gjentas ved hjelp av for hver Løkke. De Samling grensesnitt arver fra Iterabel og legger til generiske metoder for å sjekke om et element er i en samling, legge til og fjerne elementer fra samlingen, bestemme størrelsen etc.
De Liste, Sett, og Kø grensesnitt arver fra Samling grensesnitt.
Liste er en bestilt samling, og dens elementer kan nås med indeksen i listen.
Sett er en uordnet samling med distinkte elementer, som ligner den matematiske forestillingen om et sett.
Kø er en samling med tilleggsmetoder for å legge til, fjerne og undersøke elementer, nyttig for å holde elementer før behandlingen.
Kart grensesnittet er også en del av samlingsrammen, men utvider seg ikke Samling. Dette er designet, for å understreke forskjellen mellom samlinger og kartlegginger som er vanskelig å samle under en felles abstraksjon. De Kart grensesnitt representerer en nøkkelverdidatastruktur med unike nøkler og ikke mer enn en verdi for hver nøkkel.
Q2. Beskriv forskjellige implementeringer av kartgrensesnittet og deres forskjeller i bruksfall.
En av de mest brukte implementeringene av Kart grensesnittet er HashMap. Det er en typisk hash-kart datastruktur som gir tilgang til elementer i konstant tid, eller O (1), men bevarer ikke orden og er ikke trådsikker.
For å bevare innsettingsrekkefølgen for elementer, kan du bruke LinkedHashMap klasse som utvider HashMap og knytter i tillegg elementene til en koblet liste, med påregnelig overhead.
De TreeMap klasse lagrer elementene i en rød-svart trestruktur, som gir tilgang til elementer i logaritmisk tid, eller O (log (n)). Det er tregere enn HashMap i de fleste tilfeller, men det tillater å holde elementene i orden ifølge noen Komparator.
De ConcurrentHashMap er en trådsikker implementering av et hash-kart. Det gir full samvær av hentinger (som få operasjon medfører ikke låsing) og høy forventet samtidighet av oppdateringer.
De Hashtable klasse har vært i Java siden versjon 1.0. Det avskrives ikke, men regnes for det meste som foreldet. Det er et trådsikkert hash-kart, men i motsetning til det ConcurrentHashMap, alle metodene er ganske enkelt synkronisert, som betyr at alle operasjoner på dette kartet blokkerer, til og med henting av uavhengige verdier.
Q3. Forklar forskjellen mellom Linkedlist og Arraylist.
ArrayList er en implementering av Liste grensesnitt som er basert på en matrise. ArrayList internt håndterer størrelsen på denne matrisen når elementene legges til eller fjernes. Du kan få tilgang til elementene i konstant tid ved hjelp av indeksen i matrisen. Hvis du setter inn eller fjerner et element, skifter imidlertid alle påfølgende elementer som kan være treg hvis matrisen er stor og det innsatte eller fjernede elementet er nær begynnelsen av listen.
LinkedList er en dobbeltkoblet liste: enkeltelementer settes inn Node objekter som har referanser til forrige og neste Node. Denne implementeringen kan virke mer effektiv enn ArrayList hvis du har mange innsettinger eller slettinger i forskjellige deler av listen, spesielt hvis listen er stor.
I de fleste tilfeller ArrayList utkonkurrerer LinkedList. Selv elementer som skifter inn ArrayList, mens det er en O (n) -operasjon, implementeres som en veldig rask System.arraycopy () anrop. Det kan til og med virke raskere enn LinkedList‘S O (1) innsetting som krever øyeblikkelig a Node innvending og oppdatering av flere referanser under panseret. LinkedList kan også ha et stort minne overhead på grunn av oppretting av flere små Node gjenstander.
Q4. Hva er forskjellen mellom Hashset og Treeset?
Både HashSet og TreeSet klasser implementerer Sett grensesnitt og representerer sett med forskjellige elementer. I tillegg TreeSet implementerer NavigableSet grensesnitt. Dette grensesnittet definerer metoder som utnytter bestillingen av elementer.
HashSet er internt basert på en HashMap, og TreeSet støttes av en TreeMap forekomst, som definerer egenskapene deres: HashSet holder ikke elementer i en bestemt rekkefølge. Iterasjon over elementene i a HashSet produserer dem i en blandet rekkefølge. TreeSetderimot, produserer elementer i rekkefølge ifølge noen forhåndsdefinerte Komparator.
Q5. Hvordan implementeres Hashmap i Java? Hvordan bruker implementeringen Hashcode og like metoder for gjenstander? Hva er tidskompleksiteten med å sette og få et element fra en slik struktur?
De HashMap klasse representerer en typisk hash-kart datastruktur med visse designvalg.
De HashMap støttes av en størrelse som kan endres, og som har en størrelse på to. Når elementet legges til a HashMap, først dens hashCode beregnes (an int verdi). Deretter brukes et visst antall nedre biter av denne verdien som en matriseindeks. Denne indeksen peker direkte på cellen i matrisen (kalt en bøtte) der dette nøkkelverdiparet skal plasseres. Å få tilgang til et element med indeksen i en matrise er en veldig rask O (1) -operasjon, som er hovedfunksjonen til en hash-kartstruktur.
EN hashCode er imidlertid ikke unikt og til og med for forskjellige hashCodes, kan vi motta den samme matriseposisjonen. Dette kalles en kollisjon. Det er mer enn én måte å løse kollisjoner i hash-kartdatastrukturene på. På Java HashMap, hver bøtte refererer faktisk ikke til et enkelt objekt, men til et rød-svart tre av alle objekter som landet i denne bøtta (før Java 8 var dette en lenket liste).
Så når HashMap har bestemt bøtta for en nøkkel, må den krysse dette treet for å sette nøkkelverdiparet på plass. Hvis det allerede finnes et par med en slik nøkkel i bøtta, erstattes det med en ny.
For å hente gjenstanden med nøkkelen, HashMap igjen må beregne hashCode for nøkkelen, finn tilsvarende bøtte, kryss treet, ring er lik på nøklene i treet og finn den matchende.
HashMap har O (1) kompleksitet, eller konstant tidskompleksitet, for å sette og få elementene. Selvfølgelig kan mange kollisjoner degradere ytelsen til O (log (n)) tidskompleksitet i verste fall når alle elementer lander i en enkelt bøtte. Dette løses vanligvis ved å gi en god hashfunksjon med en jevn fordeling.
Når HashMap intern matrise er fylt ut (mer om det i neste spørsmål), blir den automatisk endret til å være dobbelt så stor. Denne operasjonen bygger på rehashing (gjenoppbygging av interne datastrukturer), noe som er kostbart, så du bør planlegge størrelsen på HashMap på forhånd.
Q6. Hva er formålet med de første parametrene for kapasitet og lastfaktor for en Hashmap? Hva er standardverdiene?
De initialCapacity argument av HashMap konstruktør påvirker størrelsen på den interne datastrukturen til HashMap, men resonnement om den faktiske størrelsen på et kart er litt vanskelig. De HashMapSin interne datastruktur er en matrise med kraften av to størrelser. Så initialCapacity argumentverdien økes til neste power-of-two (for eksempel hvis du setter den til 10, vil den faktiske størrelsen på den interne matrisen være 16).
Lastfaktoren til a HashMap er forholdet mellom elementtellingen delt på antall bøtter (dvs. intern arraystørrelse). For eksempel hvis en 16-bøtte HashMap inneholder 12 elementer, dens belastningsfaktor er 12/16 = 0,75. En høy belastningsfaktor betyr mange kollisjoner, noe som igjen betyr at kartet skal endres til neste kraft på to. Så loadFactor argument er en maksimumsverdi av lastfaktoren til et kart. Når kartet oppnår denne belastningsfaktoren, endres størrelsen på det interne arrayet til neste power-of-two-verdi.
De initialCapacity er 16 som standard, og loadFactor er 0,75 som standard, så du kan sette 12 elementer i en HashMap som ble instantiert med standardkonstruktøren, og den ville ikke endre størrelse. Det samme gjelder for HashSet, som støttes av en HashMap eksempel internt.
Derfor er det ikke trivielt å komme på initialCapacity som tilfredsstiller dine behov. Dette er grunnen til at Guava-biblioteket har Maps.newHashMapWithExpectedSize () og Sets.newHashSetWithExpectedSize () metoder som lar deg bygge en HashMap eller a HashSet som kan inneholde forventet antall elementer uten å endre størrelse.
Q7. Beskriv spesielle samlinger for Enums. Hva er fordelene med implementeringen deres sammenlignet med vanlige samlinger?
EnumSet og EnumMap er spesielle implementeringer av Sett og Kart grensesnitt tilsvarende. Du bør alltid bruke disse implementeringene når du har å gjøre med enums fordi de er veldig effektive.
An EnumSet er bare en liten vektor med "en" i posisjonene som tilsvarer ordinære verdier av enums tilstede i settet. For å sjekke om en enumverdi er i settet, må implementeringen bare sjekke om den tilsvarende biten i vektoren er en "en", noe som er en veldig enkel operasjon. Tilsvarende an EnumMap er en matrise med enums ordinale verdi som en indeks. I tilfelle av EnumMap, det er ikke behov for å beregne hash-koder eller løse kollisjoner.
Q8. Hva er forskjellen mellom feil- og feilsikre ikteratorer?
Iteratorer for forskjellige samlinger er enten feilsøkte eller feilsikre, avhengig av hvordan de reagerer på samtidige modifikasjoner. Den samtidige modifikasjonen er ikke bare en modifisering av samlingen fra en annen tråd, men også modifikasjon fra den samme tråden, men ved å bruke en annen iterator eller endre samlingen direkte.
Mislykkes raskt iteratorer (de returnerte av HashMap, ArrayList, og andre ikke-trådsikre samlinger) gjentas over samlingens interne datastruktur, og de kaster ConcurrentModificationException så snart de oppdager en samtidig modifikasjon.
Feilsikker iteratorer (returnert av trådsikre samlinger som ConcurrentHashMap, CopyOnWriteArrayList) lage en kopi av strukturen de gjentar. De garanterer sikkerhet fra samtidige modifikasjoner. Ulempene inkluderer overdreven minneforbruk og iterasjon over mulig utdaterte data i tilfelle samlingen ble endret.
Q9. Hvordan kan du bruke sammenlignbare og komparatorgrensesnitt for å sortere samlinger?
De Sammenlignelig grensesnitt er et grensesnitt for objekter som kan sammenlignes i en eller annen rekkefølge. Den eneste metoden er sammenligne med, som opererer på to verdier: selve objektet og argumentobjektet av samme type. For eksempel, Heltall, Langog andre numeriske typer implementerer dette grensesnittet. String implementerer også dette grensesnittet, og dets sammenligne med metode sammenligner strenger i leksikografisk rekkefølge.
De Sammenlignelig grensesnitt lar deg sortere lister over tilsvarende objekter med Collections.sort () metode og opprettholde iterasjonsrekkefølgen i samlinger som implementeres SortedSet og SortedMap. Hvis objektene dine kan sorteres med logikk, bør de implementere Sammenlignelig grensesnitt.
De Sammenlignelig grensesnitt er vanligvis implementert ved hjelp av naturlig rekkefølge av elementene. For eksempel alle Heltall tall er ordnet fra mindre til større verdier. Men noen ganger vil du kanskje implementere en annen type bestilling, for eksempel for å sortere tallene i synkende rekkefølge. De Komparator grensesnitt kan hjelpe her.
Klassen til objektene du vil sortere trenger ikke å implementere dette grensesnittet. Du oppretter ganske enkelt en implementeringsklasse og definerer sammenligne metode som mottar to objekter og bestemmer hvordan de skal bestilles. Du kan da bruke forekomsten av denne klassen til å overstyre den naturlige rekkefølgen av Collections.sort () metode eller SortedSet og SortedMap tilfeller.
Som den Komparator grensesnitt er et funksjonelt grensesnitt, du kan erstatte det med et lambda-uttrykk, som i følgende eksempel. Det viser bestilling av en liste ved hjelp av en naturlig bestilling (Heltall‘S Sammenlignelig grensesnitt) og bruker en tilpasset iterator (Komparator grensesnitt).
Liste liste1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (liste1); assertEquals (nytt heltal (1), list1.get (0)); Liste liste1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (liste1, (a, b) -> b - a); assertEquals (nytt heltall (5), list1.get (0));
