Как получить O(1) при обращении к элементу по ключу

В Python словарь (dict) обеспечивает O(1) среднюю сложность доступа к элементу по ключу благодаря хеш-таблице. Хеш-функция преобразует ключ в индекс, по которому значение хранится в памяти.

Пример:

my_dict = {'a': 1, 'b': 2, 'c': 3}
value = my_dict['b']  # O(1) - быстрое получение значения по ключу

Важные нюансы:

1. Ключ должен быть хешируемым (неизменяемым типом)
2. Коллизии хешей могут немного снизить производительность
3. В худшем случае (при многих коллизиях) сложность может деградировать до O(n)

Для пользовательских объектов нужно правильно реализовать методы __hash__ и __eq__:

class User:
    def __init__(self, id):
        self.id = id
    
    def __hash__(self):
        return hash(self.id)
    
    def __eq__(self, other):
        return self.id == other.id

users = {User(1): 'Alice', User(2): 'Bob'}