Определение, свободна ли позиция в закрытом хешировании

Question

Как бы вы определили, занята ли уже позиция или нет? Когда память выделяется, все, что в ней есть, - это мусор (в C ++, который я использую в atm). Я думал об использовании вспомогательного массива bools, чтобы узнать, занята ли позиция, но это потребовало бы довольно много дополнительной памяти.

Я также мог бы установить значение для каждой позиции, но тогда я не смог бы использовать это значение. В обоих случаях я также потерял бы некоторую производительность при инициализации значений (например, значения bools равны false, остальные значения равны 0, чтобы указать, что позиция свободна).

Есть ли другие решения?

Answer 1

Обычно вы используете специальный элемент-заполнитель для указания пустых значений. В простейшем случае это может быть нулевой указатель, но это, конечно, означает, что вы вводите косвенное указание; Вы не можете хранить свои значения напрямую. Во всех остальных случаях вам придется учитывать тип фактически сохраненного. Например, если вы сохранили 32-разрядные целые числа, вам нужно было бы зарезервировать хотя бы одно предопределенное значение (например, 0) в качестве элемента часового значения, тем самым уменьшив диапазон значений, которые могут храниться в вашей хэш-таблице.

Дополнительный массив с флагами является довольно хорошим решением. Учтите, что этот массив может быть уменьшен не менее чем в 8 раз за счет хранения битовых флагов вместо целочисленных байтовых переменных (или даже значений типа bool, для которых на большинстве архитектур потребуется 4 байта каждый).

Answer 2

Вы можете использовать для этого boost::optional вместо необработанного значения. Вот почему он был создан, чтобы добавить неинициализированное значение к элементу. Он имеет снижение производительности, аналогичное первоначальной инициализации значений, но требует лишь небольшого количества дополнительной памяти на элемент.