Šta je hash tabela, kako je predstavljena u Python-u i koje su joj složenosti operacija?

Хэш-таблица — это структура данных, которая хранит пары ключ-значение и обеспечивает быстрый доступ к значениям по ключу за амортизированное время O(1).

В Python хэш-таблица реализована через встроенный тип данных dict. Он использует хэш-функцию для вычисления индекса в массиве, где хранится значение.

Сложности операций в среднем:

• Вставка: O(1)
• Поиск: O(1)
• Удаление: O(1)

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

Пример использования:

my_dict = {'apple': 1, 'banana': 2}
print(my_dict['apple'])  # 1
my_dict['orange'] = 3