Nei giorni precedenti, nella classe delle strutture dati, abbiamo appreso come gli alberi AVL funzionavano . Lo avrei avuto in una delle mie lezioni, ma l'istruttore ha detto "non lo userai mai veramente" e invece dovremmo invece imparare 2-3 alberi e b * alberi. Erano giorni in cui la memoria era tesa ei processi erano filettati singolarmente. Non hai usato un deque quando una lista collegata singolarmente avrebbe funzionato altrettanto bene.
La skip list è molto più comune oggi con più memoria disponibile e la concorrenza è un problema (non è necessario bloccare molto quando si agisce da scrittore in un elenco di salti - rispetto a tutto con un albero AVL).
Francamente, è la mia struttura dati preferita ora che è qualcosa che posso facilmente ragionare su come funziona al di sotto e dove sarà vantaggioso o svantaggioso da usare.
Non avrai bisogno di scriverne uno da zero (a meno che non lo si ottenga come domanda per un colloquio), ma è altrettanto probabile che tu implementi un albero AVL).
Devi avere per capire perché vuoi selezionare un ConcurrentSkipListMap in Java piuttosto che un HashMap o TreeMap o una qualsiasi delle altre implementazioni di mappe.
Per capire come funziona, devi capire come funziona un albero binario. Aspetta, lascia che ti aggiusti. Devi capire come funziona un albero binario bilanciato . Senza bilanciare un albero binario, non ottieni alcun vantaggio reale con la sua ricerca.
Diciamo che abbiamo questo albero:
Einseriamoun'8'inesso.Oraabbiamo:
E non è equilibrato. Quindi, andiamo e facciamo la magia di bilanciarlo tramite un'implementazione ...
Ehaidinuovounalberoequilibrato.Maquellaeraunsaccodimagiachemihasalutatolamano.
Consentedifareunalistadisalto.
Questo sembra essere idealizzato. Pochi sono, ma mostra la natura equilibrata dell'albero binario che l'ideale di skiplist si avvicina.
Ora, vogliamo inserire un 6 in là. Questo lo sta inserendo molto come una lista collegata. Tuttavia, iniziamo in alto e scendiamo. La cima punta a 5. È 6 > 5? Sì. Ok, la cima punta alla fine ora, quindi andiamo giù nello stack (siamo al 5). Il prossimo è 7. È 6 > 7? No. Quindi scendiamo di livello e siamo al livello di base, quindi inseriamo 6 a destra del 5.
Noi lanciamo una moneta - teste che costruiamo, croce restiamo. Tails. Niente di più da fare.
Inseriamooraquell'8.8>5?Sì.8>7?Sì.Eorasiamodinuovoallivellopiùbassodopoaverseguitolefrecceelostacketestiamo8>11?No.Quindiinseriamol'8adestradel7.
Noilanciamounamoneta-testechecostruiamo,crocerestiamo.Tails.Nientedipiùdafare.
Nell'albero bilanciato, saremmo nervosi sull'albero che ora non è in equilibrio. Ma questo non è un albero - è una lista di salti. Noi approssimiamo un albero bilanciato.
Ora inseriamo un 10. Eviterò tutti i confronti.
Noi lanciamo una moneta - teste che costruiamo, croce restiamo. Teste! E giralo di nuovo, Testa di nuovo! Flip di nuovo, ok, c'è una coda. Due livelli sopra l'elenco collegato di base.
Ilvantaggioquiècheoraseinseriremoun12,possiamosaltareda5a10senzafaretuttiquestialtriconfronti.Possiamosaltarliconl'elencodeisalti.Enondobbiamopreoccuparcidell'alberobilanciato:lanaturaprobabilisticadell'impilamentolofapernoi.
Perchéècosìutile?Perchéquandoinseriscoil10possofarlobloccandolascritturasuipuntatori5e7e8piuttostochesull'interastruttura.Ementrelofaccio,ilettoripossonoancorapassareattraversolalistadeisaltisenzaavereunostatoincoerente.Perl'usosimultaneo,èpiùvelocenondoverbloccare.Periteraresullivelloinferiore,èpiùvelocediunalbero(legioiedeglialgoritmiBFSeDFSperlanavigazioneadalbero-nondevipreoccupartidiloro).
Loincontrerai?Probabilmentelovedraiinusoinalcunipunti.Epoisapraiperchél'autorehasceltoun'implementazionequellapiuttostocheunaTreeMapoHashMapperlastruttura.
Granpartediquestoèstatopresoinprestitodalmiopostsulblog: The Skip List