Implementări ale interfețelor Set și Queue

„Ei bine, cum este procesorul tău?”

"E în regulă. Am stat o oră în azot lichid, așa că acum sunt ca nou!"

— Grozav. Atunci hai să continuăm.

„Setați colecții”.

Matematic vorbind, un set este un grup de elemente unice. Astfel, în programare, un Set este o colecție de elemente unice, adică o colecție care nu vă lasă să stocați elemente identice.

„Nu știu dacă Ellie ți-a arătat ierarhia moștenirii lui Set. Dacă nu, iată-o:”

„Un HashSet este o colecție care stochează elemente în interior utilizând valorile hash returnate de metoda hashCode ()”.

„Pentru simplitate, HashSet<E> stochează un obiect HashMap<E, Object> care stochează valorile HashSet-ului ca chei.”

"Uau!"

„Folosirea codurilor hash vă permite să căutați, să adăugați și să eliminați rapid elemente din set.”

„Dar rețineți că clasa dvs. trebuie să implementeze corect metodele hashCode & equals pentru a adăuga obiecte din clasele dvs. la un set și pentru a le găsi corect acolo.”

„Ambele metode sunt folosite foarte mult în HashSet/HashMap. ”

„Dacă uitați să implementați metoda hashCode (), atunci riscați să nu vă puteți găsi obiectul în set, chiar dacă este prezent.”

"Da, îmi amintesc, îmi amintesc. Mi-ai spus despre asta mai devreme. Am auzit totul despre asta."

"OK. Atunci iată câteva informații utile pentru tine."

„Să presupunem că ați implementat corect hashCode și equals  în clasa dvs. și vă stocați cu bucurie obiectele într-un set.”

„Dar apoi te duci și schimbi unul dintre obiecte și, prin aceasta, schimbi datele interne folosite pentru a-și calcula hash -ul . Deci hash-ul obiectului se schimbă.”

„Și asta înseamnă că atunci când îl cauți în Set, probabil că nu îl vei găsi.”

"Woa! Cum funcționează?"

„Acesta este o capcană binecunoscută atunci când lucrați cu hashuri. În esență, căutările HashSet (și HashMap) sunt garantate să funcționeze corect numai dacă obiectele sunt imuabile .”

"Woa! Și ce, nimeni nu face nimic în privința asta?"

"Toată lumea pretinde că problema nu există. Dar acest lucru apare frecvent în interviuri, așa că ar putea merita să ne amintim..."

„Un LinkedHashSet este un HashSet ale cărui elemente sunt, de asemenea, stocate într-o listă legată. HashSets normale nu acceptă ordonarea elementelor. În primul rând, pur și simplu nu este o operație oficială. elementul este adăugat”.

Dar puteți obține un iterator de la un LinkedHashSet și îl puteți utiliza pentru a parcurge toate elementele în ordinea în care au fost adăugate la LinkedHashSet . Nu se întâmplă des, dar uneori este foarte necesar acest lucru”.

„Înțeleg. Îmi place când există cursuri pentru aceste scenarii „doar pentru orice eventualitate”. Astfel de cazuri nu sunt chiar atât de rare.”

„ TreeSet este o colecție care stochează elemente sub forma unui arbore ordonat după valori. Un TreeSet <E> conține un TreeMap <E, Object> care stochează toate aceste valori. Și acest TreeMap folosește un arbore echilibrat roșu -negru pentru a stoca elemente . Drept urmare, acceptă operațiuni foarte rapide de adăugare, eliminare și conținut."

"Da, îmi amintesc. Am discutat despre asta recent. Și m-am gândit și unde se folosește asta."

„Și se dovedește că unele dintre cele mai populare colecții ale Java îl folosesc”.

„Da. Apropo, intervievatorii întreabă adesea despre TreeSet . De obicei încearcă să te păcălească. Ei vor spune: „Dacă un TreeSet folosește un arbore binar, atunci toate elementele pot forma o ramură lungă, așa că căutările vor dura un „Acesta este momentul să-l puneți pe insolentul în locul lui, afirmând: „Chiar și un copil știe că TreeSet și TreeMap folosesc copaci echilibrați roșu-negru , astfel încât această situație este de fapt imposibilă.”

„Ah. Mi-ar plăcea să văd fața persoanei care a pus acea întrebare. Aș putea chiar să memorez acea frază...”

„Dar, în practică, Set s-a dovedit a nu fi atât de simplu pe cât credeam inițial.”

„Pe de altă parte, situația cu Queue este mult mai simplă:”

" Queue implementează o coadă. Elementele sunt adăugate la sfârșitul cozii și luate din față."

„ PriorityQueue este de fapt singura implementare clasică a interfeței Queue , fără a lua în considerare LinkedList , care din punct de vedere tehnic este și o coadă.”

"Bine, obosesc. Asta-i tot pentru azi. Până data viitoare."