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

Question

При расчете коэффициента загрузки хеш-таблицы с использованием массива с открытой адресацией я использую:

numberOfKeysInArray/sizeOfArray

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

Я думаю, что при оценке среднего числа зондов для поиска записи удаленные записи должны учитываться в качестве коэффициента загрузки, но при вставке нового ключа они не должны.

Какой правильный расчет: включая удаленные ключи или нет?

Answer 1

Нет, по определению, коэффициент загрузки - это отношение количества элементов к размеру массива сегмента.См., Например, Википедия или в этой лекции .

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