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

Question

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

numberOfKeysInArray/sizeOfArray 

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

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

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

Answer 1

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

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