Implementazioni delle interfacce Set e Queue

"Beh, com'è il tuo processore?"

"Va tutto bene. Mi sono seduto in azoto liquido per un'ora, quindi ora sono come nuovo!"

"Fantastico. Allora continuiamo."

"Imposta raccolte".

Matematicamente parlando, un insieme è un gruppo di elementi unici. Quindi, in programmazione, un Set è una raccolta di elementi univoci, cioè una raccolta che non consente di memorizzare elementi identici.

"Non so se Ellie ti ha mostrato la gerarchia dell'eredità di Set. In caso contrario, eccola qui:"

"Un HashSet è una raccolta che memorizza gli elementi internamente utilizzando i valori hash restituiti dal metodo hashCode ()."

"Per semplicità, HashSet<E> memorizza un oggetto HashMap<E, Object> che memorizza i valori di HashSet come chiavi."

"Ehi!"

"L'utilizzo di codici hash ti consente di cercare, aggiungere e rimuovere rapidamente elementi dal set."

"Ma tieni presente che la tua classe deve implementare correttamente i metodi hashCode & equals per aggiungere oggetti delle tue classi a un Set e trovarli correttamente lì."

"Entrambi i metodi sono usati molto all'interno di HashSet/HashMap. "

"Se dimentichi di implementare il metodo hashCode (), rischi di non riuscire a trovare il tuo oggetto nel Set, anche se è presente."

"Sì, mi ricordo, mi ricordo. Me ne hai parlato prima. Ne ho sentito parlare tutto."

"OK. Allora ecco alcune informazioni più utili per te."

"Supponi di aver implementato correttamente hashCode e uguali  nella tua classe e di archiviare felicemente i tuoi oggetti in un Set."

"Ma poi vai e cambi uno degli oggetti, e così facendo cambi i dati interni usati per calcolare il suo hash . Quindi l'hash dell'oggetto cambia."

"E questo significa che quando lo cerchi nel Set, probabilmente non lo troverai."

"Whoa! Come funziona?"

"Questa è una trappola ben nota quando si lavora con gli hash. In sostanza, è garantito che le ricerche HashSet (e HashMap) funzionino correttamente solo se gli oggetti sono immutabili ."

"Whoa! E cosa, nessuno fa niente?"

"Tutti fingono che il problema non esista. Ma questo emerge spesso nelle interviste, quindi potrebbe valere la pena ricordare..."

"Un LinkedHashSet è un HashSet i cui elementi sono anch'essi memorizzati in un elenco collegato. Gli HashSet normali non supportano l'ordinamento degli elementi. In primo luogo, semplicemente non è un'operazione ufficiale. In secondo luogo, anche l'ordine interno può cambiare in modo significativo quando un singolo elemento viene aggiunto."

Ma puoi ottenere un iteratore da un LinkedHashSet e usarlo per esaminare tutti gli elementi nell'ordine in cui sono stati aggiunti a LinkedHashSet . Non succede spesso, ma a volte questo è davvero necessario".

"Capisco. Mi piace quando esistono classi per questi scenari 'just in case'. Tali casi non sono poi così rari."

" TreeSet è una raccolta che memorizza gli elementi sotto forma di un albero ordinato per valori. Un TreeSet <E> contiene una TreeMap <E, Object> che memorizza tutti questi valori. E questa TreeMap utilizza un albero bilanciato rosso - nero per memorizzare elements . Di conseguenza, supporta operazioni di aggiunta, rimozione e contiene molto veloci."

"Sì, ricordo. Ne abbiamo discusso di recente. E ho anche pensato a dove viene usato."

"E si scopre che alcune delle raccolte più popolari di Java lo usano."

"Sì. A proposito, gli intervistatori spesso chiedono informazioni su TreeSet . Di solito cercano di ingannarti. Diranno, 'se un TreeSet utilizza un albero binario, allora tutti gli elementi possono formare un lungo ramo, quindi le ricerche richiederanno un molto tempo. «Questo è solo il momento di mettere al suo posto l'insolente affermando: "Anche un bambino sa che TreeSet e TreeMap usano alberi rosso-neri bilanciati , quindi quella situazione è effettivamente impossibile.""

"Ah. Mi piacerebbe vedere la faccia della persona che ha fatto quella domanda. Potrei anche memorizzare quella frase...."

"Ma in pratica, Set si è rivelato non essere così semplice come pensavo inizialmente."

"D'altra parte, la situazione con Queue è molto più semplice:"

" Queue implementa una coda. Gli elementi vengono aggiunti alla fine della coda e prelevati dalla parte anteriore."

" PriorityQueue è in realtà l'unica implementazione classica dell'interfaccia Queue , senza contare LinkedList , che tecnicamente è anche una coda."

"Okay, mi sto stancando. Per oggi è tutto. Alla prossima volta."