Immediato vs. incrementale copia nella dinamica Hash Table Resize

Question

Quali sono i vantaggi e gli svantaggi di ciascuno? Se sto implementazione di una tabella hash in cui il tempo di ricerca rapida è cruciale, sembra che dovrei usare immediato, perché questo si sarebbe verificato solo su inserzioni e delezioni, mentre incrementale rallenterebbe ricerca pure. Ha senso?

che sto facendo questo in C, se è importante.

Answer 1

A meno che non hanno vincoli di tempo stretti su ogni operazione di tabella di hash, il ridimensionamento subito probabilmente rende più senso. Come dici tu, che migliorerà di ricerca volte nel corso di ridimensionamento incrementale, e in generale ammortizzare il costo di inserimento e cancellazione. ridimensionamento incrementale è più applicabile ai casi in cui tutti operazioni devono procedere in misura fissa e rigorosamente limitato di tempo.