Ho implementato le mie proprie funzioni di tabella hash in C, ma attualmente non supporta il ridimensionamento. Mi stavo chiedendo quali algoritmi esistono oltre al modo bruto di creare una nuova tabella hash vuota e spostare tutto lì?Quali algoritmi sono disponibili per ridimensionare una tabella hash?
C'è un ridimensionamento incrementale.
Da Wikipedia:
incrementale ridimensionamento
Alcune implementazioni tabella hash, particolare nei sistemi in tempo reale, non può pagare il prezzo di allargare la tabella hash tutto in una volta, perché può interrupt operazioni critiche. Se uno non può evitare il ridimensionamento dinamico, una soluzione è quello di eseguire il ridimensionamento a poco a poco:
Durante il ridimensionamento, allocare la nuova tabella hash, ma mantenere il vecchio tavolo invariato. In ogni operazione di ricerca o cancellazione, controllare entrambe le tabelle. Esegue le operazioni di inserimento solo nella nuova tabella. Ad ogni inserimento si spostano anche gli elementi r dalla vecchia tabella alla nuova tabella . Quando tutti gli elementi vengono rimossi dalla vecchia tabella, rilasciarlo.
Per assicurarsi che la vecchia tabella sarà completamente copiato prima del nuovo tabella stessa deve essere allargata, si è necessario aumentare le dimensioni del tabella di un fattore di almeno (r + 1)/r durante il ridimensionamento.
Quindi questo non è un modo intelligente di spostare tutti gli elementi dal vecchio tavolo nella nuova tabella (e se ce n'è uno, non l'ho visto); piuttosto, alleggerisce l'onere del ridimensionamento consentendo che la migrazione avvenga gradualmente.
Wikipedia ha qualche words of wisdom sull'argomento.
Inoltre, non è una soluzione, ma potrebbe far parte di uno: se ci si trova in Windows è possibile utilizzare la famiglia di funzioni VirtualAlloc che consente di riservare lo spazio degli indirizzi senza impegnare effettivamente le pagine di memoria. Cioè, in parole povere, dovresti fare qualcosa come un "malloc" e dirgli di "prenotare 1000 MB, ma rendere solo i primi 10 disponibili". Quindi, se scriverai oltre i 10 MB, avresti il solito crash. Ma quando arriva il momento di espandersi, basta dire "OK, dammi un altro 10 MB dopo i primi". E i prossimi 10 MB sono resi disponibili all'indirizzo subito dopo i primi 10 MB. È come ridimensionare un array. L'attuale RAM in uso sarà sufficiente quanto necessario, ma gli indirizzi di memoria saranno riservati in anticipo in modo che altre operazioni di allocazione della memoria non li utilizzino.
Il solito errore è lasciare il codice cliente per indovinare il miglior numero di benne in anticipo. È utile, il cliente di solito ha una ragionevole ipotesi su quanti elementi finiranno nella tabella. Se vuoi farlo automaticamente, devi prima dichiarare una serie di numeri primi per le dimensioni della benna. Quando si vede il fattore di caricamento di un secchio troppo alto, selezionare il primo principale dell'array, ricreare l'elenco dei bucket e spostare gli elementi dai vecchi bucket alla nuova tabella.
Questo è un modo abbastanza intelligente per ridimensionare un array - se si dispone di spazio indirizzo da masterizzare (x64) - ma non funzionerà con le hash, sarà comunque necessario ripetere tutto (ed è più complesso farlo in posto.) – Eloff
@Eloff - Beh, come ho detto - non è una soluzione in sé, solo una parte di uno. E non devi prenotare molto più spazio per gli indirizzi. Solo una quantità ragionevole. Non è un proiettile d'argento, ma rende l'operazione di ridimensionamento più veloce. –
Vedo dove stai andando ora con questo, ma è dubbio che in realtà ridurrebbe il ridimensionamento più velocemente. La maggiore spesa qui non è l'allocazione della memoria, che presenta a malapena le caratteristiche. Tutto il tempo va in errori di pagina soft per portare la nuova memoria nello spazio di indirizzamento del processo (di solito accade nell'allocatore di memoria quando azzera la memoria) e nel costo richiesto per re-hash e reinserire tutti gli elementi nella hashtable . Ma per gli array dinamici, non è necessario copiare nulla e puoi pagare gli errori di pagina soft uno alla volta (crescendo di una pagina alla volta) ora è eccellente! – Eloff