Изменение компромиссов при реализации Hashtable с использованием линейного зондирования

Question

Я пытаюсь реализовать хеш-таблицу с использованием линейного зондирования.

Прежде чем вставить пару (ключ, значение) в хеш-таблицу, я хочу проверить, заполнена ли она наполовину. Если это так, мне нужно удвоить размер базового массива.

Очевидно, что есть два способа сделать это:

Один из них - создать другой массив с удвоенным размером, перефразировать все записи в старом и добавить их в новый массив. Затем перепривязать старый массив к новому. Этот способ прост в реализации, но занимает много места.

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

Какой способ я должен использовать?

Answer 1

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