Как устроен словарь в Python?

При записи d[key] = value Python вычисляет hash(key) и по нему выбирает ячейку во внутренней таблице. При чтении происходит то же самое, и в ячейке сравниваются ключи: сначала хеши, затем ==. Поэтому поиск, вставка и удаление в среднем занимают O(1) и не зависят от размера словаря.

Коллизии. Разные ключи могут попасть в одну ячейку. CPython использует открытую адресацию: при занятой ячейке проверяет следующие по определённой последовательности. Когда таблица заполняется примерно на две трети, она увеличивается и элементы перераскладываются. В худшем случае, если хеши «плохие», поиск деградирует до O(n), но на практике это редкость.

Требования к ключу. Объект должен быть хешируемым: иметь __hash__, согласованный с __eq__ (равные объекты дают равный хеш), и хеш не должен меняться. Поэтому list, dict, set ключами быть не могут, а str, int, tuple из неизменяемых элементов, frozenset — могут.

Порядок. С Python 3.7 словарь гарантированно хранит ключи в порядке вставки: в CPython он устроен как компактный массив записей плюс отдельная таблица индексов.

d = {"a": 1}
d[(1, 2)] = "кортеж — можно"
d[[1, 2]] = "список"      # TypeError: unhashable type: 'list'

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y
    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)
    def __hash__(self):
        return hash((self.x, self.y))   # согласован с __eq__