Se mantieni una struttura dati separata lungo il tuo heap, questo probabilmente risolverà il tuo problema. Questo è l'approccio che utilizza la LinkedHashMap (una lista collegata lungo il lato HashMap) per consentire una cache LRU e un ben noto ordinamento delle voci in LinkedHashMap (ordine di inserimento) (grepcode LinkedHashMap.Entry ).
Questa struttura dati potrebbe apparire come Deque o qualcosa di simile ed è ordinato per ordine di inserimento. Nessun altro ordine è imposto su questa struttura.
Il problema più grande con questo, però, è che le due strutture (l'heap e il deque) non sono sincronizzate, si dovrebbe fare la conservazione del libro per rimuovere dal deque quando qualcosa viene rimosso dall'heap.
Un approccio a questo sarebbe utilizzare un riferimento debole (Java Riferimento , C # WeakRefrence classe). Quando percorri la deque, esegui il polling del Reference per get() per vedere se è effettivamente lì, e in tal caso restituiscilo, altrimenti scarti quell'elemento nel deque e continua a camminare fino a trovare un elemento Riferimento a cui è collegato un oggetto.
Il trucco qui è che se stai puntando all'oggetto su cui punta l'heap, è possibile che un'altra parte del codice abbia preso una strong presa sull'oggetto e pensi che sia ancora nell'Heap .
Per evitare ciò, il deque dovrebbe invece puntare all'elemento heap piuttosto che all'oggetto a cui punta l'elemento heap, ed essere molto pulito con la rimozione dell'elemento dall'heap quando viene eliminato (e non lasciarlo trapelare al di fuori dell'heap - tranne che per la deque (che dovrebbe probabilmente essere all'interno dell'heap)). Ammetto di non sapendo per quanto tempo il Reference continuerà a puntare a qualcosa e quali condizioni sono necessarie per deterministicamente risolverlo.
Questo permetterebbe al garbage collector di fare il lavoro per te di tenere una contabilità. Il trade off è invece di ogni volta che l'inserto o la rimozione viene eseguito dall'heap e la conservazione del libro viene eseguita, quindi la conservazione del libro viene eseguita quando il deque viene interrogato o sbirciato. Qual è il modo in cui il trade off va considerato in base all'inserimento, alla rimozione e al polling che l'applicazione fa sullo heap.
Un pensiero di incollare un'altra struttura di dati all'interno dell'heap potrebbe consentire problemi di riferimenti deterministici. Se si dispone di una HashMap nell'heap che contiene anche tutti gli oggetti (sebbene si noti che in realtà non è in grado di contenere copie dei propri forti riferimenti agli oggetti). Quando qualcosa viene aggiunto o rimosso dall'heap, viene anche aggiunto o rimosso da HashMap. Quindi, la deque, invece di contenere riferimenti deboli all'oggetto, ha un strong riferimento. Quando il deque viene interrogato, controlla HashMap per vedere se l'oggetto si trova ancora nell'heap.
In ogni caso, ciò che in definitiva fornisce è una deque tale che il primo elemento restituito dalla deque è il più vecchio nell'heap e l'ultimo elemento restituito dalla deque è il più nuovo oggetto nell'heap.