Tabelle hash usando VLists

Question

Phil Bagwell, nel suo 2002 paper on the VList data structure, indica che è possibile utilizzare un VList per implementare una tabella hash persistente. Tuttavia, la sua spiegazione di come funzionava non includeva molti dettagli, e io non la capisco. Qualcuno può darmi una spiegazione più dettagliata, o anche esempi?

Inoltre, mi sembra di vedere che questa struttura dati, sebbene possa avere la stessa complessità Big-O di un Hashtable, sarà più lenta perché esegue ulteriori ricerche. Qualcuno si preoccupa di fare un'analisi dettagliata di quanto è più lento, preferibilmente includendo il comportamento della cache? Come cambia la relazione di prestazione tra i due nel caso in cui non ci siano collisioni o molti?

Answer 1

Ho dato un'occhiata a questo documento, e appare molto preliminare. Il fatto che nessuna versione successiva sia stata pubblicata e che l'originale sia apparso in IFL (che è una specie di riunione in corso d'opera), suggerisce che potresti perdere tempo.

Answer 2

Hrmm sembrano esserci numerosi problemi con le strutture dati proposte dal documento in questione.

Al di fuori del polsino, le vliste ingenue menzionate per prime sembrano aver bisogno di riferimenti unici al fine di ottenere qualcosa in prossimità delle garanzie di tempo proposte. Perdi la maggior parte della capacità di condividere le code. È possibile condividere i piccoli nodi verso la parte posteriore dell'elenco, ma si finisce per dover duplicare il nodo vlist più grande nel momento in cui si configura qualcosa nel cdr di vlist che è ancora attivo. Questo costo è proporzionale al costo di copiare l'intera lista.

Con le modifiche 2d menzionate in seguito, esso diventa di nuovo costante, ma è una costante piuttosto grande, poiché si finisce almeno copiando la testa di un elenco di pagine (o peggio, una vlist) e la prima pagina nell'elenco .

Il funzionale elenco di hash non sembrava avere senso per me. Era solo una breve descrizione che sembrava essere imbullonata su un foglio altrimenti non correlato, senza dettagli sufficienti per capire quanto fosse pratico.