Implementeringer af sæt- og kø-grænseflader

"Nå, hvordan er din processor?"

"Det er OK. Jeg sad i flydende nitrogen i en time, så nu er jeg så god som ny!"

"Fantastisk. Så lad os fortsætte."

"Indstil samlinger."

Matematisk set er et sæt en gruppe af unikke elementer. I programmering er et sæt således en samling af unikke elementer, dvs. en samling, der ikke lader dig gemme identiske elementer.

"Jeg ved ikke, om Ellie viste dig Sets arvehierarki. Hvis ikke, så er det her:"

"Et HashSet er en samling, der gemmer elementer internt ved hjælp af de hash-værdier, der returneres af hashCode ()-metoden."

"For nemheds skyld gemmer HashSet<E> et HashMap<E, Object>-objekt, der gemmer HashSets værdier som nøgler."

"Hov!"

"Ved at bruge hash-koder kan du hurtigt søge efter, tilføje og fjerne elementer fra sættet."

"Men husk på, at din klasse skal implementere hashCode & equals -metoderne korrekt for at tilføje objekter fra dine klasser til et sæt og finde dem korrekt der."

"Begge metoder bruges meget i HashSet/HashMap. "

"Hvis du glemmer at implementere hashCode () metoden, risikerer du ikke at kunne finde dit objekt i sættet, selvom det er til stede."

"Ja, jeg kan huske, jeg kan huske. Du fortalte mig om det tidligere. Jeg har hørt alt om det."

"OK. Så er her nogle flere nyttige oplysninger til dig."

"Antag, at du har implementeret hashCode og ligeværdige  korrekt i din klasse, og du gemmer gerne dine objekter i et sæt."

"Men så går du hen og ændrer et af objekterne, og ved at gøre det ændrer du de interne data, der bruges til at beregne dets hash . Så objektets hash ændres."

"Og det betyder, at når du søger efter det i sættet, vil du sandsynligvis ikke finde det."

"Hvaa! Hvordan virker det?"

"Dette er en velkendt faldgrube, når man arbejder med hashes. I det væsentlige er HashSet (og HashMap)-søgninger kun garanteret at fungere korrekt, hvis objekterne er uforanderlige ."

"Hov! Og hvad, ingen gør noget ved det?"

"Alle lader, som om problemet ikke eksisterer. Men det kommer ofte op i interviews, så det kan være værd at huske..."

"Et LinkedHashSet er et HashSet, hvis elementer også er gemt i en linket liste. Normale HashSets understøtter ikke bestilling af elementerne. For det første er det simpelthen ikke en officiel operation. For det andet kan selv den interne rækkefølge ændre sig væsentligt, når en enkelt element tilføjes."

Men du kan få en iterator fra et LinkedHashSet og bruge den til at gennemgå alle elementerne i den rækkefølge, de blev tilføjet til LinkedHashSet . Det sker ikke tit, men nogle gange er der meget brug for det her«.

"Jeg forstår det. Jeg elsker, når der eksisterer klasser til disse «just in case»-scenarier. Sådanne tilfælde er ikke så sjældne."

" TreeSet er en samling, der gemmer elementer i form af et træ ordnet efter værdier. Et TreeSet <E> indeholder et TreeMap <E, Object>, der gemmer alle disse værdier. Og dette TreeMap bruger et balanceret rød -sort træ til at gemme elementer . Som et resultat understøtter den meget hurtig tilføjelse, fjernelse og indeholder operationer."

"Ja, det kan jeg huske. Det diskuterede vi for nylig. Og jeg tænkte også på, hvor det her bruges."

"Og det viser sig, at nogle af Javas mest populære samlinger bruger det."

"Jep. Forresten spørger interviewere ofte om TreeSet . De forsøger normalt at narre dig. De vil sige, 'hvis et TreeSet bruger et binært træ, så kan alle elementer danne en lang gren, så søgninger vil tage en lang tid. «Dette er bare tiden til at sætte den uforskammede fyr på hans sted ved at sige: "Selv et barn ved, at TreeSet og TreeMap bruger balancerede rød-sorte træer , så den situation er faktisk umulig."

"Ah. Jeg ville elske at se ansigtet på den person, der stillede det spørgsmål. Jeg kunne endda huske den sætning. …"

"Men i praksis viste Set sig ikke at være så simpel, som jeg først troede."

"På den anden side er situationen med Queue meget enklere:"

" Kø implementerer en kø. Elementer tilføjes til slutningen af ​​køen og tages fra forsiden."

" PriorityQueue er faktisk den eneste klassiske implementering af Queue- grænsefladen, ikke medregnet LinkedList , som teknisk set også er en kø."

"Okay, jeg er ved at være træt. Det var alt for i dag. Indtil næste gang."