Пытаемся вставить туда, куда показала hash-функция. При возникновении коллизии ищем первый доступный пустой слот и помещаем туда ключ/значение: i-ый индекс занят, проверяем i+1, i+2 и т.д. (linear probing, см probings) При этом пока ищем место проверяем, нет ли у нас дубликатов. Есть ⇒ перезаписываем значение.
Ищем нужный элемент: переходим к ячейке, если есть коллизии, то идём по ячейкам, пока не найдём нужную или не наткнёмся на пустую. Нашли ⇒ удаляем значение И помечаем, что на этом месте ранее был элемент (!)
<aside> ❓ А что будет, если просто удалить элемент?
В таком случае алгоритмы hash table будут работать некорректно: возможна ситуация, когда после этого удалённого элемента лежали другие, которые также попали под коллизию. Но мы до них не дойдём, т.к. алгоритмы Hash Table остановятся на пустой ячейке, которая ранее была занята, но которую мы никак не пометили.
Поэтому некоторые алгоритмы Hash Table также должны не просто останавливаться при достижении пустой ячейки, а ещё и проверять, был ли элемент на этом месте ранее. Если был, то они идут дальше.
</aside>
For search hits (collisions) $\approx\frac{1}{2}(1+\frac{1}{1-\alpha})$
For search misses (or inserts) $\approx\frac{1}{2}(1+\frac{1}{(1-\alpha)^2})$