Метка: hash

Задача на ключи словаря

Имеется такой код, где мы делаем 5 записей в словарь:

d = {}

d[float('nan')] = 1
d[float('nan')] = 2
d[1.0] = 'float'
d[1] = 'int'
d[True] = 'bool'

print(len(d))

Давайте решим ее. Для ключа словаря нам важны две вещи:

  • Хэш hash(key) – ключи с разными хэшами дадут нам разные записи в словаре.
  • Равенство ключей – если хэши равны, то проверяется равенство ключей (==), и если и они равны, то считается, что ключ тот же самый – это будет одна и та же запись в словаре.

float(‘nan’)

float('nan') – создает нам новый объект типа float со значением NaN (not a number – не число). Это специально значение. Оно получается, если результат операции не определен. Например, вычитание бесконечности из бесконечности не даст нам конкретного определенного результата, потому что бесконечность – это не число:

>>> print(float('Inf') - float('Inf'))
nan

В соответствии с IEEE 754, такое состояние задаётся через установку показателя степени в зарезервированное значение 11…11, а мантиссы — во что угодно, кроме 0 (зарезервированное значение для машинной бесконечности).

У NaN есть замечательно свойство, что он не равен никакому другому float, даже самому себе или другому NaN.

>>> x = float('nan')
>>> x == x
False
>>> hash(x)
0

Но hash от NaN всегда равен 0. Таким образом, словарь видит, что мы кладем в него ключи с одинаковым хэшем, но не равные между собой. Вывод: мы можем создать сколько угодно ключей с NaN, на вид они одинаковые, даже побитово могут совпадать, но так как каждый NaN не равен другому NaN по определению, то и dict все их считает разными!

>>> d = {}
>>> d[float('nan')] = 1
>>> d[float('nan')] = 2
>>> d
{nan: 1, nan: 2}

>>> d[float('nan')]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: nan

1, 1.0 и True

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

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

Все они равны между собой! Поэтому в словаре все эти три ключа будут отвечать ровно одной записи! Посмотрите:

>>> d = {}

>>> d[1.0] = 'float'
>>> d[1] = 'int'
>>> d[True] = 'bool'

>>> d
{1.0: 'bool'}
>>> len(d)
1

>>> d[1]
'bool'
>>> d[1.0]
'bool'
>>> d[True]
'bool'

Так как первая запись была с 1.0, то и ключ останется типа float, а значение уже будет перезаписано будущими операторами присваивания.

Ответ: 3

У нас в словаре две записи от разных float('nan') и только одна запись от трех присваиваний 1.0, 1 и True. Итого ответ – 3 (три) записи будет в словаре!

Пусть вас не путает, что в условии задачи было 5 операторов.

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

А вы знали про hash(-1)?

(Речь идет о реализации CPython)

Встроенная функция hash возвращает целое число – хэш-сумму, которое используется при сравнении ключей словаря во время поиска, например. Для пользовательских классов hash вызывает магический метод класса  __hash__ , а для примитивных типов уже есть встроенная реализация на Си. 

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

def print_hash(x):
    print(f'hash({x}) = {hash(x)}')
for i in range(2, -4, -1):
    print_hash(i)

Вывод:

hash(2) = 2
hash(1) = 1
hash(0) = 0
hash(-1) = -2  <-- что?
hash(-2) = -2
hash(-3) = -3

Оказывается hash не возвращает -1, а конвертирует его явно в -2. Я изучил исходный код на Си и нашел это место. «Легенда гласит», что в CPython число -1 зарезервировано внутренне для индикации ошибок при выполнении этой функции.

Еще интереснее для рациональных чисел. От hash от NAN – ноль. Плюс еще пасхалка: hash от бесконечности возращает первые несколько цифр числа π. 

print_hash(-1.0)  # -2
print_hash(float('nan'))  # 0
print_hash(float('+inf'))  # 314159
print_hash(float('-inf'))  # -314159

🧙 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈