Immediate vs. Incremental Copying in Dynamic Hash Table Resize

Question

What are the advantages and disadvantages of each? If I'm implementing a hash table where fast lookup time is crucial, it seems like I should use immediate, because that would occur only on insertions and deletions, whereas incremental would slow down lookup as well. Does that make sense?

I'm doing this in C, if it matters.

Answer 1

Unless you have tight time constraints on every hash table operation, resizing immediately probably makes the most sense. As you say, it will improve lookup times over incremental resizing, and just generally amortize the cost of insertion and deletion. Incremental resizing is more applicable to cases where all operations have to proceed in a fixed and strictly bounded amount of time.