Открытая адресация в хеш-таблицах (удаление)

Всем хай! Сходу к делу!
Дана хеш-таблица, состоящая из 10 элементов. Она должна хранить натуральные неповторяющиеся числа.
Стартовая инициализация такая (пусть С++ - индекс от нуля):
0 0 0 0 0 0 0 0 0 0 - хранимое число
---------------------
0 1 2 3 4 5 6 7 8 9 - индекс элемента

Абсолютно не важно, какой является хеш-функция, но известно, что она не является совершенной, т е возможны коллизии! Ключом выступает само значение числа.
Допустим, на вход подаются числа: 12, 16, 8, 27, 13

Я пытаюсь использовать линейное пробирование, у которого интервал шага = 1.
Для числа 12 хеш-функция вернула хеш-значение равное 4 (т е 4 - индекс в хеш-таблице, куда попадет число 12).
Для 16 индекс 9. Для 8 индекс 2. Для 27 индекс 5.
Вот что представляет из себя хеш-таблица после добавления 4-рех чисел:
0 0 8 0 12 27 0 0 0 16 - хранимое число
---------------------
0 1 2 3 4 5 6 7 8 9 - индекс элемента

Для 13 индекс получился = 4! Коллизия! Карман этот занят. Поэтому я тупо начинаю искать свободное место, добавляя +1 к индексу. Перехожу на индекс 5. Он тоже занят. Иду дальше и попадаю в позицию 6 - свободно! Значит, туда поставлю число 13 и получу:
0 0 8 0 12 27 13 0 0 16 - хранимое число
---------------------
0 1 2 3 4 5 6 7 8 9 - индекс элемента

Как работает вставка вроде все понятно. Также есть булевый флаг, показывающий свободна/занята ячейка, если свободно - вставляю, если просмотрел каждый карман и все заняты - вставка невозможна, т к ХТ заполнена (либо расширять таблицу).

Мне до конца непонятно, как будет работать удаление из этой ХТ!
Допустим, хочу удалить число 12. Хеш-функция вернула индекс 4. Обращаюсь к этой ячейке, она занята и там стоит именно 4. Ставлю флаг - свободно (типа удалил число).
0 0 8 0 12 27 13 0 0 16 - хранимое число
---------------------
0 1 2 3 4 5 6 7 8 9 - индекс элемента

И потом хочу удалить число 13. Хеш функция вернула индекс = 4. Смотрю этот карман, а там СВОБОДНО (предыдущей операцией оттуда было удалено число 12).
Что делать в этом случае? Шагать дальше в поиске числа 13? А, если этого числа изначально не было бы в хеш-таблице, тогда придется впустую просмотреть всю таблицу?

0

Можно добавить одно поле в таблицу с индексом следующего числа с таким же значением хэша

0