Тонкости Python

Когда Python обрабатывает выражение-словарь, он сначала строит новый пустой объект-словарь, а затем присваивает ему ключи и значения в том порядке, в каком они переданы в выражение-словарь.

Тогда, когда мы его разложим на части, наше выражение-словарь будет эквивалентно приведенной ниже последовательности инструкций, которые исполняются по порядку:

>>> xs = dict()
>>> xs[True] = 'да'
>>> xs[1] = 'нет'
>>> xs[1.0] = 'возможно'

Как ни странно, Python считает все ключи, используемые в этом примере словаря, эквивалентными:

>>> True == 1 == 1.0
True

Bool

Конечно, многие из вас уже могли быть знакомы с подобным примером. Однако, вы точно не могли подозревать (если не копались в документации), что Python рассматривает тип bool как подкласс типа int. Именно так обстоит дело в Python 2 и Python 3:

Булев тип — это подтип целочисленного типа, и булевы значения ведут себя, соответственно, как значения 0 и 1 почти во всех контекстах, при этом исключением является то, что при преобразовании в строковый тип, соответственно, возвращаются строковые значения 'False' или 'True'.

И разумеется, это означает, что в Python булевы значения технически можно использовать в качестве индексов списка или кортежа:

>>> ['нет', 'да'][True]
'да'

Использование подобного рода логических конструкций, пожалуй, снесет башню вашим коллегам.

Что касается языка Python, то все эти значения — True, 1 и 1.0 — представляют одинаковый ключ словаря. Когда интерпретатор вычисляет выражение-словарь, он неоднократно переписывает значение ключа True. Это объясняет, почему в самом конце результирующий словарь содержит всего один ключ.

Прежде чем мы пойдем дальше, взглянем еще раз на исходное выражение-словарь:

>>> {True: 'да', 1: 'нет', 1.0: 'возможно'}
{True: 'возможно'}

Почему здесь в качестве ключа мы по-прежнему получаем True? Разве не должен ключ из-за повторных присваиваний в самом конце тоже поменяться на 1.0?

Hash

После небольших изысканий в исходном коде интерпретатора Python становится понятно, что когда с объектом-ключом ассоциируется новое значение, словари Python сам этот объект-ключ не обновляют:

>>> ys = {1.0: 'нет'}
>>> ys[True] = 'да'
>>> ys
{1.0: 'да'}

Безусловно, это имеет смысл в качестве оптимизации производительности: если ключи рассматриваются идентичными, то зачем тратить время на обновление оригинала?

В последнем примере мы видели, что первоначальный объект True как ключ никогда не заменяется. По этой же причине, строковое представление словаря по-прежнему печатает ключ как True (вместо 1 или 1.0).

С тем, что мы знаем теперь, по всей видимости, значения в результирующем словаре переписываются только потому, что сравнение всегда будет показывать их как эквивалентные друг другу. Вместе с тем оказывается, что этот эффект не является следствием проверки на эквивалентность методом __eq__ тоже.

Словари Python опираются на структуру данных "хеш-таблица". Первая мысль, которая приходит на ум, заключалась в том, что такое поведение должно быть как-то связано с хэш-конфликтами.

Дело в том, что хеш-таблица во внутреннем представлении хранит имеющиеся в ней ключи в различных «корзинах» в соответствии с хеш-значением каждого ключа. Хеш-значение выводится из ключа как числовое значение фиксированной длины, которое однозначно идентифицирует ключ.

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

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

Когда два ключа имеют одинаковое хеш-значение, такая ситуация называется хеш-конфликтом и является особым случаем, с которым должны разбираться алгоритмы вставки и нахождения элементов в хеш-таблице.

Исходя из этой оценки, весьма вероятно, что хеширование как-то связано с неожиданным результатом, который получается из выражения-словаря. Поэтому давайте выясним, играют ли хеш-значения ключей здесь тоже какую-то определенную роль.

class AlwaysEquals:
    def __eq__(self, other):
        return True
    def __hash__(self):
        return id(self)

Этот класс характерен двумя аспектами.

Во-первых, поскольку метод __eq__ всегда возвращает True, все экземпляры этого класса притворяются, что они эквивалентны любому объекту:

>>> AlwaysEquals() == AlwaysEquals()
True
>>> AlwaysEquals() == 42
True
>>> AlwaysEquals() == 'штаа?'
True

И во-вторых, каждый экземпляр AlwaysEquals также будет возвращать уникальное хеш-значение, генерируемое встроенной функцией id():

>>> objects = [AlwaysEquals(),
            AlwaysEquals(),
            AlwaysEquals()]
>>> [hash(obj) for obj in objects]
[4574298968, 4574287912, 4574287072]

В Python функция id() возвращает адрес объекта в оперативной памяти, который гарантированно является уникальным.

При помощи этого класса теперь можно создавать объекты, которые притворяются, что они являются эквивалентными любому другому объекту, но при этом с ними будет связано уникальное хеш-значение. Это позволит проверить, переписываются ли ключи словаря, опираясь только на результат их сравнения на эквивалентность.

И, как вы видите, ключи в следующем ниже примере не переписываются, несмотря на то что сравнение всегда будет показывать их как эквивалентные друг другу:

>>> {AlwaysEquals(): 'да', AlwaysEquals(): 'нет'}
{ <AlwaysEquals object at 0x110a3c588>: 'да',
<AlwaysEquals object at 0x110a3cf98>: 'нет' }

Мы также можем взглянуть на эту идею с другой стороны и проверить, будет ли возврат одинакового хеш-значения достаточным основанием для того, чтобы заставить ключи быть переписанными:

class SameHash:
    def __hash__(self):
        return 1

Сравнение экземпляров класса SameHash будет показывать их как не эквивалентные друг другу, но они все будут обладать одинаковым хеш-значением, равным 1:

>>> a = SameHash()
>>> b = SameHash()
>>> a == b
False
>>> hash(a), hash(b)
(1, 1)

Давайте посмотрим, как словари Python реагируют, когда мы пытаемся использовать экземляры класса SameHash в качестве ключей словаря:

>>> {a: 'a', b: 'b'}
{ <SameHash instance at 0x7f7159020cb0>: 'a',
<SameHash instance at 0x7f7159020cf8>: 'b' }

Как показывает этот пример, эффект «ключи переписываются» вызывается не одними только конфликтами хеш-значений.

Словари выполняют проверку на эквивалентность и сравнивают хеш-значение, чтобы определить, являются ли два ключа одинаковыми. Попробуем резюмировать результаты нашего исследования.

Выражение-словарь {True: 'да', 1: 'нет', 1.0: 'возможно'} вычисляется как {True: 'возможно'}, потому что сравнение всех ключей этого примера, True, 1, и 1.0, будет показывать их как эквивалентные друг другу, и они все имеют одинаковое хеш-значение:

>>> True == 1 == 1.0
True
>>> (hash(True), hash(1), hash(1.0))
(1, 1, 1)

Пожалуй, теперь уже не так удивительно, что мы получили именно такой результат в качестве конечного состояния словаря:

>>> {True: 'да', 1: 'нет', 1.0: 'возможно'}
{True: 'возможно'}

Если вы с трудом понимаете, что происходит в этом разделе, попробуйте поэкспериментировать по очереди со всеми примерами кода в сеансе интерпретатора Python. Вы будете вознаграждены расширением своих познаний о внутренних механизмах языка Python.

Небольшой отрывок из книги, посвященный словарям и хэш-таблицам.

P.S. Это не реклама книги, но все материалы были взяты из нее. Если вам интересно, можете почитать.

дарт вейдер