Implementaties van de set- en wachtrij-interfaces

"Nou, hoe gaat het met je processor?"

"Het is oké. Ik heb een uur in vloeibare stikstof gezeten, dus nu ben ik zo goed als nieuw!"

"Geweldig. Laten we dan verder gaan."

"Stel verzamelingen in."

Wiskundig gezien is een set een groep unieke elementen. Bij het programmeren is een set dus een verzameling unieke elementen, dwz een verzameling waarin u geen identieke elementen kunt opslaan.

"Ik weet niet of Ellie je de erfenishiërarchie van Set heeft laten zien. Zo niet, hier is het:"

"Een HashSet is een verzameling die elementen intern opslaat met behulp van de hash-waarden die worden geretourneerd door de methode hashCode ()."

"Voor de eenvoud slaat HashSet<E> een HashMap<E, Object>-object op dat de waarden van de HashSet als sleutels opslaat."

"Wauw!"

"Door hashcodes te gebruiken, kunt u snel elementen uit de set zoeken, toevoegen en verwijderen."

"Maar houd er rekening mee dat uw klasse de hashCode & equals -methoden correct moet implementeren om objecten van uw klassen aan een set toe te voegen en ze daar correct te vinden."

"Beide methoden worden veel gebruikt binnen HashSet/HashMap. "

"Als je vergeet de methode hashCode () te implementeren , loop je het risico dat je je object niet kunt vinden in de Set, ook al is het aanwezig."

'Ja, ik herinner het me, ik herinner het me. Je hebt me hier eerder over verteld. Ik heb er alles over gehoord.'

"OK. Dan is hier wat meer nuttige informatie voor je."

"Stel dat je hashCode en equals  correct hebt geïmplementeerd in je klas, en je slaat je objecten met plezier op in een Set."

"Maar dan ga je een van de objecten veranderen, en door dat te doen verander je de interne gegevens die worden gebruikt om de hash te berekenen . Dus de hash van het object verandert."

"En dit betekent dat wanneer je ernaar zoekt in de Set, je het waarschijnlijk niet zult vinden."

"Ho! Hoe werkt dat?"

"Dit is een bekende valkuil bij het werken met hashes. In wezen werken HashSet (en HashMap) zoekopdrachten alleen gegarandeerd goed als de objecten onveranderlijk zijn ."

"Ho! En wat, doet niemand er iets aan?"

"Iedereen doet alsof het probleem niet bestaat. Maar dit komt vaak naar voren in interviews, dus het is misschien de moeite waard om eraan te denken..."

"Een LinkedHashSet is een HashSet waarvan de elementen ook zijn opgeslagen in een gelinkte lijst. Normale HashSets ondersteunen de volgorde van de elementen niet. Ten eerste is het gewoon geen officiële bewerking. Ten tweede kan zelfs de interne volgorde aanzienlijk veranderen wanneer een enkele onderdeel is toegevoegd."

Maar u kunt een iterator van een LinkedHashSet krijgen en deze gebruiken om alle elementen te doorlopen in de volgorde waarin ze aan de LinkedHashSet zijn toegevoegd . Het gebeurt niet vaak, maar soms is dit heel hard nodig."

"Ik snap het. Ik hou ervan als er klassen bestaan ​​voor deze 'voor het geval dat'-scenario's. Dergelijke gevallen zijn niet zo zeldzaam."

" TreeSet is een verzameling die elementen opslaat in de vorm van een boom geordend op waarden. Een TreeSet <E> bevat een TreeMap <E, Object> die al deze waarden opslaat. En deze TreeMap gebruikt een gebalanceerde rood -zwarte boom om op te slaan elementen . Daardoor ondersteunt het zeer snelle bewerkingen voor toevoegen, verwijderen en bevatten."

"Ja, dat herinner ik me. We hebben dat onlangs besproken. En ik heb ook nagedacht over waar dit wordt gebruikt."

"En het blijkt dat enkele van de populairste collecties van Java het gebruiken."

"Ja. Trouwens, interviewers vragen vaak naar TreeSet . Meestal proberen ze je te misleiden. Ze zullen zeggen: 'Als een TreeSet een binaire boom gebruikt, dan kunnen alle elementen één lange tak vormen, dus het zoeken duurt even. "Dit is precies het moment om de brutale kerel op zijn plaats te zetten door te zeggen: "Zelfs een kind weet dat TreeSet en TreeMap gebalanceerde rood -zwarte bomen gebruiken , dus die situatie is eigenlijk onmogelijk."

"Ah. Ik zou graag het gezicht zien van de persoon die die vraag stelde. Ik zou die zin zelfs uit mijn hoofd kunnen leren..."

"Maar in de praktijk bleek Set toch niet zo simpel als ik aanvankelijk dacht."

"Aan de andere kant is de situatie met Queue veel eenvoudiger:"

" Wachtrij implementeert een wachtrij. Elementen worden aan het einde van de wachtrij toegevoegd en vanaf de voorkant genomen."

" PriorityQueue is eigenlijk de enige klassieke implementatie van de Queue- interface, LinkedList niet meegerekend , wat technisch gezien ook een wachtrij is."

"Oké, ik word moe. Dat was alles voor vandaag. Tot de volgende keer."