На cppref в методе .erase для хеш карты сказано, что удаление по pos имеет константную сложность, а по ключу - средний случай, что значит средняя сложность? Там указано что эта сложность равна одному вызову a.count(key), я правильно понимаю? По сути разница между удалением по pos и ключу в производительности нет, разве что вызов count метода
Ну, как бы, хеш таблицы могут быть сделаны бакетами, корзина и. То есть, у тебя в ячейке массива про хешу, хранится список или что то подобное. Чтобы в нем найти элемент, надо дефолт но, пройти из начала в конец.