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

Question

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

numberOfKeysInArray/sizeOfArray

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

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

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

Answer 1

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

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