Come evitare di esaurire la memoria con un TDictionary in crescita?

Question

TDictionary<TKey,TValue> usa un array interno che viene raddoppiata se è pieno:

newCap := Length(FItems) * 2; 
if newCap = 0 then 
    newCap := 4; 
Rehash(newCap); 

Questo comporta bene con un numero medio di elementi, ma se si arriva al limite superiore è molto sfortunato, perché potrebbe gettare un EOutOfMemory eccezione anche se è disponibile quasi la metà della memoria.

C'è un modo per influenzare questo comportamento? In che modo le altre classi di raccolta si occupano di questo scenario?

Answer 1

È necessario capire come funziona un dizionario. Un dizionario contiene un elenco di "bucket hash" in cui vengono posizionati gli elementi che inserisci. Questo è un numero finito, quindi una volta che lo hai riempito devi allocare più secchi, non c'è modo di aggirarlo. Poiché l'assegnazione degli oggetti ai bucket si basa sul risultato di una funzione hash, non è possibile semplicemente aggiungere i bucket alla fine dell'array e inserire elementi, è necessario riassegnare l'intero elenco di blocchi, ripeti tutto e mettilo nei (nuovi) secchi corrispondenti.

Dato questo comportamento, l'unico modo per rendere il dizionario non riassegnare una volta pieno è assicurarsi che non si riempia mai. Se conosci il numero di elementi che inserirai nel dizionario, passalo come parametro al costruttore e sarai fatto, non più riallocazioni del dizionario.

Se non riesci a farlo (non sai il numero di elementi che avrai nel dizionario) dovrai riconsiderare ciò che ti ha fatto scegliere lo TDictionary in primo luogo e selezionare una struttura dati che offre un compromesso migliore per il tuo particolare algoritmo. Ad esempio, è possibile utilizzare gli alberi di ricerca binari, poiché eseguono il bilanciamento ruotando le informazioni nei nodi esistenti, senza necessità di riassegnazioni mai.