Implementeringar av gränssnitten Set och Queue

"Tja, hur är din processor?"

"Det är OK. Jag satt i flytande kväve i en timme, så nu är jag som ny!"

"Jättebra. Låt oss sedan fortsätta."

"Ställ in samlingar."

Matematiskt sett är en uppsättning en grupp unika element. I programmering är alltså en uppsättning en samling unika element, dvs en samling som inte låter dig lagra identiska element.

"Jag vet inte om Ellie visade dig Sets arvshierarki. Om inte, här är den:"

"En HashSet är en samling som lagrar element internt med hjälp av hash-värdena som returneras av hashCode ()-metoden."

"För enkelhetens skull lagrar HashSet<E> ett HashMap<E, Object>-objekt som lagrar HashSets värden som nycklar."

"Oj!"

"Med hash-koder kan du snabbt söka efter, lägga till och ta bort element från uppsättningen."

"Men tänk på att din klass måste implementera hashCode & equals -metoderna korrekt för att kunna lägga till objekt från dina klasser till en uppsättning och hitta dem på rätt sätt där."

"Båda metoderna används mycket i HashSet/HashMap. "

"Om du glömmer att implementera hashCode ()-metoden riskerar du att inte hitta ditt objekt i Setet, även om det finns."

"Ja, jag minns, jag minns. Du berättade om det här tidigare. Jag har hört allt om det."

"OK. Då kommer här lite mer användbar information för dig."

"Anta att du har implementerat hashCode och lika  i din klass korrekt, och att du gärna lagrar dina objekt i en uppsättning."

"Men sedan går du och ändrar ett av objekten, och genom att göra det ändrar du den interna data som används för att beräkna dess hash . Så objektets hash ändras."

"Och detta betyder att när du söker efter det i uppsättningen, kommer du förmodligen inte att hitta det."

"Whoa! Hur fungerar det?"

"Detta är en välkänd fallgrop när man arbetar med hash. I huvudsak är HashSet-sökningar (och HashMap) bara garanterade att fungera korrekt om objekten är oföränderliga ."

"Wow! Och vad gör ingen något åt ​​det?"

"Alla låtsas att problemet inte existerar. Men detta kommer ofta upp i intervjuer, så det kan vara värt att komma ihåg..."

"En LinkedHashSet är en HashSet vars element också lagras i en länkad lista. Normala HashSets stöder inte ordning av elementen. För det första är det helt enkelt inte en officiell operation. För det andra kan även den interna ordningen förändras avsevärt när en enda element läggs till."

Men du kan hämta en iterator från en LinkedHashSet och använda den för att gå igenom alla element i den ordning de lades till i LinkedHashSet . Det händer inte ofta, men ibland är det här väldigt välbehövligt."

"Jag förstår. Jag älskar när det finns klasser för dessa "bara utifall"-scenarier. Sådana fall är inte så sällsynta."

" TreeSet är en samling som lagrar element i form av ett träd ordnat efter värden. En TreeSet <E> innehåller en TreeMap <E, Object> som lagrar alla dessa värden. Och denna TreeMap använder ett balanserat röd -svart träd för att lagra element . Som ett resultat stöder den mycket snabba lägg till, ta bort och innehåller operationer."

"Ja, jag minns. Vi diskuterade det nyss. Och jag funderade också på var detta används."

"Och det visar sig att några av Javas mest populära samlingar använder det."

"Japp. Förresten, intervjuare frågar ofta om TreeSet . De försöker vanligtvis lura dig. De kommer att säga," om en TreeSet använder ett binärt träd, då kan alla element bilda en lång gren, så sökningar kommer att ta en lång tid. «Detta är precis dags att sätta den oförskämda mannen på sin plats genom att säga: "Till och med ett barn vet att TreeSet och TreeMap använder balanserade röd-svarta träd, så den situationen är faktiskt omöjlig."

"Ah. Jag skulle älska att se ansiktet på personen som ställde den frågan. Jag kanske till och med memorerar den frasen. …"

"Men i praktiken visade sig Set inte vara så enkelt som jag först trodde."

"Å andra sidan är situationen med Queue mycket enklare:"

" Queue implementerar en kö. Element läggs till i slutet av kön och tas från fronten."

" PriorityQueue är faktiskt den enda klassiska implementeringen av Queue- gränssnittet, utan att räkna LinkedList , som tekniskt sett också är en kö."

"Okej, jag börjar tröttna. Det var allt för idag. Tills nästa gång."