Представьте таблицу из пяти ячеек и учебный хеш
key % 5. Ключи 1, 6 и 11 попадут в одну ячейку. Это коллизия, и таблице нужен способ сохранить все три значения.При цепочках значения остаются в одном бакете. При линейном пробировании занятая ячейка заставляет двигаться дальше: ключи займут позиции 1, 2 и 3. Поиск повторяет тот же маршрут.
Теперь удалите ключ 6. Если пометить позицию 2 как обычную пустую ячейку, поиск 11 остановится раньше времени. Поэтому используют особую метку удаления, tombstone: значения здесь уже нет, но поиск нужно продолжить.
В интерактивном разборе коллизий можно сравнить обе стратегии на одинаковых ключах. Поиск в хеш-таблице не гарантированно O(1) для любого входа: распределение ключей и способ обработки коллизий имеют значение.