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

Средняя алгоритмическая сложность чтения из хэш-таблицы обычно считается O(1) — то есть константной. Это достигается за счёт прямого доступа к элементу по хэш-коду ключа.

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