Как определяется временная сложность операции добавления элемента в хеш-таблицу?

Временная сложность операции добавления элемента в хеш-таблицу обычно считается амортизированно O(1). Это означает, что в среднем добавление происходит за постоянное время, так как элемент сразу помещается в соответствующую корзину (бакет) по хешу. Однако в худшем случае, если происходит коллизия (несколько элементов попадают в один бакет), или когда требуется расширение таблицы (ре-хеширование), операция может занять O(n) времени, где n — количество элементов в таблице. Но благодаря хорошему хешированию и контролю загрузки таблицы, такие случаи редки.