Тонкости 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. Это не реклама книги, но все материалы были взяты из нее. Если вам интересно, можете почитать.
