Во второй версии анализа структур данных и алгоритмов в C, касающейся хеш-таблицы, есть упражнение, в котором говорится, что при хешировании цепей, если мы выполняем много удалений, мы сделаем таблицу разреженной, что будет занимать много места.мы можем перефразировать с меньшей таблицей, размер которой равен половине оригинальной. Между тем, если размер таблицы равен N, а количество элементов около 2N, нам необходимо перефразировать таблицу большего размера. Вопрос в том, прежде чем перефразировать таблицу меньшего размеранасколько разреженной может быть таблица.
Ниже приведен ответ:
Мы должны быть осторожны, чтобы не перефразировать слишком часто.Пусть p будет порогом (доля размера таблицы), при котором мы перефразируем таблицу меньшего размера.Тогда, если новая таблица имеет размер N, она содержит 2pN элементов.Эта таблица потребует перефразирования либо после вставки 2N - 2pN, либо после удаления pN.Балансировка этих затрат предполагает, что хорошим выбором является p = 2/3.
Например, предположим, что у нас есть таблица размером 300. Если мы перефразируем 200 элементов, то новый размер таблицы будет N = 150,и мы можем сделать 100 вставок или 100 удалений, пока не потребуется новая перефразировка.Если мы знаем, что вставки происходят чаще, чем удаления, тогда мы можем выбрать p, чтобы оно было несколько больше.Однако, если p слишком близко к 1,0, то последовательность небольшого количества удалений, за которыми следуют вставки, может вызвать частую перефразировку.В худшем случае, если p = 1,0, то чередующиеся удаления и вставки требуют перефразирования.
Я знаю, как получить значение p, но я не могу понять, почему в ответе говорится, что элементы составляют 2pN, ядумаю, что это только одно из этих условий, или оно связано с хэшированием цепочки? Спасибо за помощь.