Как работает словарь в Python

Образцовый ответ: «dict это хеш-таблица. При вставке Python вычисляет hash(key), по младшим битам выбирает слот в таблице индексов, и если слот занят другим ключом, перебирает следующие по псевдослучайной последовательности проб, то есть открытая адресация. Найдя кандидата, сравнивает хеши, потом ключи через ==. Поэтому поиск в среднем O(1). Когда таблица заполняется примерно на две трети, её перестраивают в большую, это амортизируется. Сами записи CPython хранит в плотном массиве в порядке вставки, отсюда гарантированный порядок с 3.7 и экономия памяти. Требование к ключу: хешируемый, хеш не меняется, равные объекты дают равный хеш. Если положить объект ключом, а потом изменить поля, участвующие в хеше, ключ станет ненаходимым. При плохой хеш-функции, например все хеши одинаковые, словарь остаётся корректным, но вырождается в линейный поиск, и вставка n ключей стоит O(n²). На этом строили DoS, поэтому хеш строк в Python рандомизируется при каждом запуске».