Vragen tijdens sollicitatiegesprekken met Java Collections

Dit artikel maakt deel uit van een reeks: • Interviewvragen over Java Collections (huidig ​​artikel) • Interviewvragen over Java Type System

• Vragen over Java Concurrency-sollicitatiegesprekken (+ antwoorden)

• Vragen over Java-klassenstructuur en initialisatie

• Java 8 sollicitatievragen (+ antwoorden)

• Geheugenbeheer in Java-interviewvragen (+ antwoorden)

• Java Generics sollicitatievragen (+ antwoorden)

• Vragen over Java Flow Control-interview (+ antwoorden)

• Interviewvragen over Java-uitzonderingen (+ antwoorden)

• Vragen over Java-annotaties tijdens sollicitatiegesprekken (+ antwoorden)

• Topvragen tijdens het Spring Framework-interview

1. Inleiding

Java-verzamelingen is een onderwerp dat vaak ter sprake komt in technische interviews voor Java-ontwikkelaars. In dit artikel worden enkele belangrijke vragen besproken die het vaakst worden gesteld en die lastig te beantwoorden kunnen zijn.

2. Vragen

V1. Beschrijf de hiërarchie van het type collectie. Wat zijn de belangrijkste interfaces en wat zijn de verschillen daartussen?

De Herhaalbaar interface vertegenwoordigt elke verzameling die kan worden herhaald met behulp van de voor elk lus. De Verzameling interface erft van Herhaalbaar en voegt generieke methoden toe om te controleren of een element zich in een verzameling bevindt, elementen toe te voegen en te verwijderen uit de verzameling, de grootte ervan te bepalen enz.

De Lijst, Set, en Wachtrij interfaces erven van de Verzameling koppel.

Lijst is een geordende verzameling en de elementen ervan zijn toegankelijk via hun index in de lijst.

Set is een ongeordende verzameling met verschillende elementen, vergelijkbaar met de wiskundige notie van een set.

Wachtrij is een verzameling met aanvullende methoden voor het toevoegen, verwijderen en onderzoeken van elementen, handig om elementen vast te houden voordat ze worden verwerkt.

Kaart interface maakt ook deel uit van het verzamelingsraamwerk, maar breidt zich niet uit Verzameling. Dit is zo ontworpen om het verschil te benadrukken tussen verzamelingen en mappings die moeilijk te verzamelen zijn onder een gemeenschappelijke abstractie. De Kaart interface vertegenwoordigt een sleutelwaarde-gegevensstructuur met unieke sleutels en niet meer dan één waarde voor elke sleutel.

Q2. Beschrijf verschillende implementaties van de kaartinterface en hun verschillen in gebruiksscenario's.

Een van de meest gebruikte implementaties van de Kaart interface is de Hash kaart. Het is een typische datastructuur met hash-kaarten waarmee toegang kan worden verkregen tot elementen in constante tijd, of O (1), maar behoudt de orde niet en is niet draadveilig.

Om de invoegvolgorde van elementen te behouden, kunt u de LinkedHashMap klasse die de extensie Hash kaart en bindt bovendien de elementen in een gekoppelde lijst, met voorzienbare overhead.

De TreeMap class slaat zijn elementen op in een rood-zwarte boomstructuur, waardoor toegang tot elementen in logaritmische tijd of O (log (n)) mogelijk is. Het is langzamer dan de Hash kaart in de meeste gevallen, maar het maakt het volgens sommigen mogelijk om de elementen op orde te houden Comparator.

De ConcurrentHashMap is een threadveilige implementatie van een hash-map. Het biedt volledige gelijktijdigheid van opvragingen (zoals de krijgen operatie brengt geen vergrendeling met zich mee) en hoog verwachte gelijktijdigheid van updates.

De Hashtable class is in Java sinds versie 1.0. Het is niet verouderd, maar wordt meestal als achterhaald beschouwd. Het is een thread-veilige hash-map, maar in tegenstelling tot ConcurrentHashMap, al zijn methoden zijn eenvoudig gesynchroniseerd, wat betekent dat alle bewerkingen op dit kaartblok, zelfs het ophalen van onafhankelijke waarden.

Q3. Leg het verschil uit tussen Linkedlist en Arraylist.

ArrayList is een implementatie van de Lijst interface die is gebaseerd op een array. ArrayList verwerkt intern het vergroten of verkleinen van deze array wanneer de elementen worden toegevoegd of verwijderd. U kunt de elementen in constante tijd benaderen door hun index in de array. Het invoegen of verwijderen van een element leidt er echter toe dat alle daaropvolgende elementen worden verschoven, wat traag kan zijn als de array enorm is en het ingevoegde of verwijderde element zich dicht bij het begin van de lijst bevindt.

LinkedList is een dubbel gelinkte lijst: er worden enkele elementen in geplaatst Knooppunt objecten met verwijzingen naar vorige en volgende Knooppunt. Deze implementatie lijkt misschien efficiënter dan ArrayList als u veel invoegingen of verwijderingen heeft in verschillende delen van de lijst, vooral als de lijst groot is.

In de meeste gevallen ArrayList overtreft LinkedList. Zelfs elementen verschuiven naar binnen ArrayList, hoewel het een O (n) -bewerking is, wordt het geïmplementeerd als een zeer snelle System.arraycopy () bellen. Het kan zelfs sneller verschijnen dan het LinkedList‘S O (1) -invoeging waarvoor het instantiëren van een Knooppunt object en het bijwerken van meerdere referenties onder de motorkap. LinkedList kan ook een grote geheugenoverhead hebben vanwege het maken van meerdere kleine Knooppunt voorwerpen.

V4. Wat is het verschil tussen Hashset en Treeset?

Beide HashSet en TreeSet klassen implementeren het Set interface en vertegenwoordigen sets van verschillende elementen. Bovendien, TreeSet implementeert het NavigableSet koppel. Deze interface definieert methoden die profiteren van de ordening van elementen.

HashSet is intern gebaseerd op een Hash kaart, en TreeSet wordt ondersteund door een TreeMap instantie, die hun eigenschappen definieert: HashSet houdt elementen niet in een bepaalde volgorde. Herhaling van de elementen in een HashSet produceert ze in een willekeurige volgorde. TreeSet, aan de andere kant, produceert elementen in volgorde volgens een aantal voorgedefinieerde Comparator.

V5. Hoe wordt Hashmap geïmplementeerd in Java? Hoe gebruikt de implementatie ervan hashcode en is gelijk aan methoden van objecten? Wat is de tijdcomplexiteit van het plaatsen en verkrijgen van een element uit een dergelijke structuur?

De Hash kaart class vertegenwoordigt een typische hash-kaartgegevensstructuur met bepaalde ontwerpkeuzes.

De Hash kaart wordt ondersteund door een array die kan worden aangepast met een grootte van twee macht. Wanneer het element wordt toegevoegd aan een Hash kaart, eerst zijn hashCode wordt berekend (an int waarde). Vervolgens wordt een bepaald aantal lagere bits van deze waarde gebruikt als een array-index. Deze index verwijst rechtstreeks naar de cel van de array (een bucket genoemd) waar dit sleutel / waarde-paar moet worden geplaatst. Toegang krijgen tot een element via zijn index in een array is een zeer snelle O (1) -bewerking, wat het belangrijkste kenmerk is van een hash-mapstructuur.

EEN hashCode is echter niet uniek, en zelfs voor verschillend hashCodes, kunnen we dezelfde arraypositie ontvangen. Dit wordt een aanrijding genoemd. Er is meer dan één manier om botsingen op te lossen in de datastructuren van de hash-map. In Java's Hash kaartverwijst elke bucket eigenlijk niet naar een enkel object, maar naar een rood-zwarte boom van alle objecten die in deze bucket zijn beland (vóór Java 8 was dit een gekoppelde lijst).

Dus wanneer de Hash kaart de bucket voor een sleutel heeft bepaald, moet het deze boom doorkruisen om het sleutel-waardepaar op zijn plaats te zetten. Als er al een paar met een dergelijke sleutel in de bucket bestaat, wordt deze vervangen door een nieuwe.

Om het object met zijn sleutel op te halen, moet de Hash kaart opnieuw moet de hashCode voor de sleutel, zoek de corresponderende emmer, doorkruis de boom, roep is gelijk aan op sleutels in de boom en vind de bijpassende.

Hash kaart heeft O (1) complexiteit, of constante-tijdcomplexiteit, van het plaatsen en krijgen van de elementen. Natuurlijk kunnen veel botsingen de prestatie in het ergste geval verlagen tot O (log (n)) tijdcomplexiteit, wanneer alle elementen in een enkele bucket terechtkomen. Dit wordt meestal opgelost door een goede hashfunctie te voorzien met een uniforme verdeling.

Wanneer de Hash kaart interne array is gevuld (daarover meer in de volgende vraag), wordt deze automatisch vergroot tot twee keer zo groot. Deze bewerking leidt tot rehashing (opnieuw opbouwen van interne gegevensstructuren), wat kostbaar is, dus u moet de grootte van uw Hash kaart vooraf.

V6. Wat is het doel van de initiële capaciteits- en belastingsfactorparameters van een hashmap? Wat zijn hun standaardwaarden?

De initialCapacity argument van de Hash kaart constructor beïnvloedt de grootte van de interne gegevensstructuur van het Hash kaart, maar redeneren over de werkelijke grootte van een kaart is een beetje lastig. De Hash kaartDe interne datastructuur is een array met de kracht van twee. Dus de initialCapacity argumentwaarde wordt verhoogd naar de volgende macht-van-twee (als u deze bijvoorbeeld instelt op 10, is de werkelijke grootte van de interne array 16).

De belastingsfactor van a Hash kaart is de verhouding van het aantal elementen gedeeld door het aantal emmers (d.w.z. interne array-grootte). Bijvoorbeeld als een 16-bucket Hash kaart bevat 12 elementen, de belastingsfactor is 12/16 = 0,75. Een hoge belastingsfactor betekent veel botsingen, wat op zijn beurt betekent dat de kaart moet worden verkleind naar de volgende macht van twee. Dus de ladingsfactor argument is een maximale waarde van de belastingsfactor van een kaart. Wanneer de kaart deze belastingsfactor bereikt, wordt de grootte van de interne array aangepast naar de volgende macht van twee.

De initialCapacity is standaard 16 en de loadFactor is standaard 0,75, dus u kunt 12 elementen in een Hash kaart dat werd geïnstantieerd met de standaardconstructor, en het formaat werd niet gewijzigd. Hetzelfde geldt voor de HashSet, die wordt ondersteund door een Hash kaart instantie intern.

Daarom is het niet triviaal om te bedenken initialCapacity die aan uw wensen voldoet. Dit is de reden waarom de Guava-bibliotheek heeft Maps.newHashMapWithExpectedSize () en Sets.newHashSetWithExpectedSize () methoden waarmee u een Hash kaart of een HashSet die het verwachte aantal elementen kan bevatten zonder de grootte te wijzigen.

V7. Beschrijf bijzondere collecties voor enums. Wat zijn de voordelen van hun implementatie in vergelijking met reguliere incasso's?

EnumSet en EnumMap zijn speciale implementaties van Set en Kaart interfaces dienovereenkomstig. Je moet deze implementaties altijd gebruiken als je met enums te maken hebt, omdat ze erg efficiënt zijn.

Een EnumSet is gewoon een bitvector met "enen" in de posities die overeenkomen met ordinale waarden van enums die in de set aanwezig zijn. Om te controleren of er een enum-waarde in de set zit, hoeft de implementatie alleen maar te controleren of de corresponderende bit in de vector een "één" is, wat een zeer eenvoudige bewerking is. Evenzo een EnumMap is een array waartoe toegang wordt verkregen met de ordinale waarde van enum als een index. In het geval van EnumMap, is het niet nodig om hashcodes te berekenen of botsingen op te lossen.

V8. Wat is het verschil tussen Fail-Fast en Fail-Safe Iterators?

Iterators voor verschillende collecties zijn ofwel fail-fast ofwel fail-safe, afhankelijk van hoe ze reageren op gelijktijdige wijzigingen. De gelijktijdige wijziging is niet alleen een wijziging van de verzameling van een andere thread, maar ook een wijziging van dezelfde thread, maar met een andere iterator of het rechtstreeks wijzigen van de verzameling.

Fail-snel iterators (die geretourneerd door Hash kaart, ArrayList, en andere niet-thread-veilige collecties) herhalen over de interne gegevensstructuur van de collectie, en ze gooien ConcurrentModificationException zodra ze een gelijktijdige wijziging detecteren.

Faalveilig iterators (geretourneerd door threadveilige verzamelingen zoals ConcurrentHashMap, CopyOnWriteArrayList) maak een kopie van de structuur waarop ze herhalen. Ze garanderen veiligheid tegen gelijktijdige wijzigingen. Hun nadelen zijn onder meer overmatig geheugengebruik en iteratie van mogelijk verouderde gegevens voor het geval de verzameling werd gewijzigd.

V9. Hoe kunt u vergelijkbare en vergelijkende interfaces gebruiken om verzamelingen te sorteren?

De Vergelijkbaar interface is een interface voor objecten die in een bepaalde volgorde kunnen worden vergeleken. De enige methode is vergelijk met, die werkt op twee waarden: het object zelf en het argumentobject van hetzelfde type. Bijvoorbeeld, Geheel getal, Lang, en andere numerieke typen implementeren deze interface. Draad implementeert ook deze interface, en zijn vergelijk met methode vergelijkt strings in lexicografische volgorde.

De Vergelijkbaar interface maakt het mogelijk om lijsten met corresponderende objecten te sorteren met de Collections.sort () methode en handhaaf de iteratievolgorde in verzamelingen die implementeren SortedSet en SortedMap. Als uw objecten kunnen worden gesorteerd met behulp van enige logica, moeten ze de Vergelijkbaar koppel.

De Vergelijkbaar interface wordt meestal geïmplementeerd met behulp van natuurlijke ordening van de elementen. Bijvoorbeeld allemaal Geheel getal nummers zijn gerangschikt van lagere naar grotere waarden. Maar soms wilt u misschien een ander soort ordening implementeren, bijvoorbeeld om de nummers in aflopende volgorde te sorteren. De Comparator interface kan hierbij helpen.

De klasse van de objecten die u wilt sorteren, hoeft deze interface niet te implementeren. U maakt eenvoudig een implementatieklasse en definieert de vergelijken methode die twee objecten ontvangt en beslist hoe ze te bestellen. U kunt dan de instantie van deze klasse gebruiken om de natuurlijke volgorde van de Collections.sort () methode of SortedSet en SortedMap gevallen.

Zoals de Comparator interface is een functionele interface, u kunt deze vervangen door een lambda-uitdrukking, zoals in het volgende voorbeeld. Het toont het ordenen van een lijst met behulp van een natuurlijke ordening (Geheel getal‘S Vergelijkbaar interface) en met behulp van een aangepaste iterator (Comparator koppel).

Lijst lijst1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (lijst1); assertEquals (nieuw geheel getal (1), lijst1.get (0)); Lijst lijst1 = Arrays.asList (5, 2, 3, 4, 1); Collections.sort (list1, (a, b) -> b - a); assertEquals (nieuw geheel getal (5), lijst1.get (0));
De volgende » Vragen over het Java Type System-interview