Немедленное и добавочное копирование в динамическом изменении размера хэш-таблицы

Question

Каковы преимущества и недостатки каждого? Если я реализую хеш-таблицу, где быстрое время поиска имеет решающее значение, мне кажется, что я должен использовать немедленный, потому что это будет происходить только при вставках и удалениях, в то время как добавочное также замедлит поиск. Имеет ли это смысл?

Я делаю это в Си, если это имеет значение.

Answer 1

Если у вас нет жестких временных ограничений для каждой операции с хеш-таблицей, изменение размера сразу, вероятно, имеет смысл. Как вы говорите, это улучшит время поиска по сравнению с инкрементным изменением размера и просто амортизирует стоимость вставки и удаления. Инкрементное изменение размера больше применимо к случаям, когда все операции должны выполняться в фиксированное и строго ограниченное время.