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

Например: Индекс: 0 1 2 3 4 . A B C .

Допустим, мы хотим удалить B. Самое очевидное решение: просто очистить ячейку.

Индекс: 0 1 2 3 4 . A . C .

Но здесь появляется проблема.

Что произойдёт при поиске C?

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

Поэтому поиск остановится.

Хотя C на самом деле находится в следующей ячейке! Для этого и нужен tombstone

Вместо полного удаления элемента мы оставляем специальную отметку:

Индекс: 0 1 2 3 4 . A † C .

Теперь ячейка не считается пустой.

Она означает: здесь раньше находился элемент; поиск должен продолжаться;

при вставке сюда потенциально можно записать новый элемент. Поиск C проходит через tombstone и находит нужный ключ. Но tombstones тоже создают проблему Представим, что мы постоянно удаляем и добавляем элементы.

Со временем таблица может заполниться такими отметками:

Индекс: 0 1 2 3 4 5 6 † A † † C † . Даже если реальных элементов немного, поиск может проходить через множество tombstones.

Это увеличивает количество проверок и ухудшает производительность. Поэтому реализации хеш-таблиц могут периодически перестраивать таблицу (rehash), избавляясь от накопившихся отметок.

Главная идея: Пустая ячейка и удалённая ячейка - не одно и то же.

Empty: поиск можно остановить.

Tombstone: поиск нужно продолжить.

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

Кстати, это не означает, что Go map устроена именно так. Здесь мы рассматриваем классическую реализацию с open addressing и linear probing. Внутреннее устройство map в Go отличается.