Quando o hash (n) == n está em Python?

100

Tenho brincado com a função hash do Python . Para números inteiros pequenos, aparece hash(n) == nsempre. No entanto, isso não se estende a grandes números:

>>> hash(2**100) == 2**100
False

Não estou surpreso, entendo que o hash assume uma faixa finita de valores. Qual é esse alcance?

Tentei usar a pesquisa binária para encontrar o menor númerohash(n) != n

>>> import codejamhelpers # pip install codejamhelpers
>>> help(codejamhelpers.binary_search)
Help on function binary_search in module codejamhelpers.binary_search:

binary_search(f, t)
    Given an increasing function :math:`f`, find the greatest non-negative integer :math:`n` such that :math:`f(n) \le t`. If :math:`f(n) > t` for all :math:`n \ge 0`, return None.

>>> f = lambda n: int(hash(n) != n)
>>> n = codejamhelpers.binary_search(f, 0)
>>> hash(n)
2305843009213693950
>>> hash(n+1)
0

O que há de especial em 2305843009213693951? Eu noto que é menos quesys.maxsize == 9223372036854775807

Edit: Estou usando Python 3. Eu executei a mesma pesquisa binária no Python 2 e obtive um resultado diferente 2147483648, que observo é sys.maxint+1

Eu também brinquei com [hash(random.random()) for i in range(10**6)]para estimar o intervalo da função hash. O máximo está consistentemente abaixo de n acima. Comparando o min, parece que o hash do Python 3 é sempre valorizado positivamente, enquanto o hash do Python 2 pode assumir valores negativos.

Coronel Panic
fonte
9
Você verificou a representação binária do número?
John Dvorak
3
'0b11111111111111111111111111111111111111111111111111111111111111111' curioso! Portanto n+1 == 2**61-1
Coronel Panic
2
parece ser dependente do sistema. Com meu python, o hash é npara todo o intervalo int de 64 bits.
Daniel
1
Observe a finalidade declarada do valor de hash: eles são usados ​​para comparar rapidamente as chaves do dicionário durante uma pesquisa no dicionário. Em outras palavras, definido pela implementação, e em virtude de ser mais curto do que muitos valores que podem ter valores de hash, pode muito bem ter colisões mesmo em espaços de entrada razoáveis.
um CVn
2
Hum, não é 2147483647igual a sys.maxint(não sys.maxint+1) e se 'n = 0b11111111111111111111111111111111111111111111111111111111111111111' então não é n+1 == 2**61ou n == 2**61-1(não n+1 == 2**61-1)?
phoog de

Respostas:

73

Com base na documentação do Python no pyhash.carquivo:

Para tipos numéricos, o hash de um número x é baseado na redução de x módulo do primo P = 2**_PyHASH_BITS - 1. Ele é projetado para que hash(x) == hash(y)sempre que x e y sejam numericamente iguais, mesmo que x e y tenham tipos diferentes.

Portanto, para uma máquina de 64/32 bits, a redução seria 2 _PyHASH_BITS - 1, mas o que é _PyHASH_BITS?

Você pode encontrá-lo no pyhash.harquivo de cabeçalho, que para uma máquina de 64 bits foi definido como 61 (você pode ler mais explicações no pyconfig.harquivo).

#if SIZEOF_VOID_P >= 8
#  define _PyHASH_BITS 61
#else
#  define _PyHASH_BITS 31
#endif

Então, em primeiro lugar, é baseado na sua plataforma, por exemplo, na minha plataforma Linux de 64 bits, a redução é 2 61 -1, que é 2305843009213693951:

>>> 2**61 - 1
2305843009213693951

Você também pode usar math.frexppara obter a mantissa e o expoente da sys.maxintqual, para uma máquina de 64 bits, mostra que o int máximo é 2 63 :

>>> import math
>>> math.frexp(sys.maxint)
(0.5, 64)

E você pode ver a diferença por um teste simples:

>>> hash(2**62) == 2**62
True
>>> hash(2**63) == 2**63
False

Leia a documentação completa sobre o algoritmo de hash Python https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Conforme mencionado no comentário, você pode usar sys.hash_info(em python 3.X), que fornecerá uma sequência de estrutura de parâmetros usados ​​para calcular hashes.

>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> 

Juntamente com o módulo que descrevi nas linhas anteriores, você também pode obter o infvalor da seguinte maneira:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159
Kasravnd
fonte
3
Seria bom mencionar sys.hash_info, para completar.
Mark Dickinson
78

2305843009213693951 é 2^61 - 1 . É o maior número primo de Mersenne que cabe em 64 bits.

Se você tiver que fazer um hash apenas tomando o valor mod algum número, então um grande número primo de Mersenne é uma boa escolha - é fácil de calcular e garante uma distribuição uniforme de possibilidades. (Embora eu pessoalmente nunca fizesse um hash dessa forma)

É especialmente conveniente calcular o módulo para números de ponto flutuante. Eles têm um componente exponencial que multiplica o número inteiro por 2^x. Uma vez que 2^61 = 1 mod 2^61-1você só precisa considerar o(exponent) mod 61 .

Veja: https://en.wikipedia.org/wiki/Mersenne_prime

Matt Timmermans
fonte
8
Você diz que nunca faria um hash dessa maneira. Você tem sugestões alternativas de como isso poderia ser feito de uma forma que torne razoavelmente eficiente o cálculo de ints, floats, decimais, frações e garanta que haja x == ygarantias hash(x) == hash(y)entre os tipos? (Números como Decimal('1e99999999')são especialmente problemáticos, por exemplo: você não quer ter que expandi-los para o número inteiro correspondente antes do hash.)
Mark Dickinson
@MarkDickinson Suspeito que ele esteja tentando fazer uma distinção entre esse hash rápido e simples e os hashes criptográficos que também se preocupam em fazer a saída parecer aleatória.
Mike Ounsworth
4
@MarkDickinson O módulo é um bom começo, mas eu poderia misturá-lo um pouco mais, especialmente misturando algumas das partes altas com as baixas. Não é incomum ver sequências de inteiros divisíveis por potências de 2. Também não é incomum ver tabelas de hash com capacidades que são potências de 2. Em Java, por exemplo, se você tiver uma sequência de inteiros divisíveis por 16, e você os usa como chaves em um HashMap, você usará apenas 1/16 dos baldes (pelo menos na versão da fonte que estou olhando)! Acho que os hashes devem ter uma aparência pelo menos um pouco aleatória para evitar esses problemas
Matt Timmermans
Sim, os hashes de estilo de mixagem de bits são muito superiores aos inspirados na matemática. As instruções de mixagem de bits são tão baratas que você pode ter muitas pelo mesmo custo. Além disso, os dados do mundo real parecem não ter padrões que não funcionam bem com a mistura de bits. Mas existem padrões horríveis para o módulo.
usr
9
@usr: Claro, mas um hash de mistura bit é inviável aqui: a exigência de que o trabalho de hash para int, float, Decimale Fractionobjetos e que x == yimplica hash(x) == hash(y), mesmo quando xe yter tipos diferentes impõe algumas restrições ao invés graves. Se fosse apenas uma questão de escrever uma função hash para inteiros, sem se preocupar com os outros tipos, seria uma questão totalmente diferente.
Mark Dickinson
9

A função hash retorna um int simples, o que significa que o valor retornado é maior -sys.maxinte menor que sys.maxint, o que significa que se você passar sys.maxint + xpara ele o resultado será -sys.maxint + (x - 2).

hash(sys.maxint + 1) == sys.maxint + 1 # False
hash(sys.maxint + 1) == - sys.maxint -1 # True
hash(sys.maxint + sys.maxint) == -sys.maxint + sys.maxint - 2 # True

Enquanto isso, 2**200é um nvezes maior do que sys.maxint- meu palpite é que o hash ultrapassaria o intervalo-sys.maxint..+sys.maxint n vezes até que parasse em um inteiro simples nesse intervalo, como nos trechos de código acima.

Então, geralmente, para qualquer n <= sys.maxint :

hash(sys.maxint*n) == -sys.maxint*(n%2) +  2*(n%2)*sys.maxint - n/2 - (n + 1)%2 ## True

Observação: isso é verdade para o python 2.

Andriy Ivaneyko
fonte
8
Isso pode ser verdade para Python 2, mas definitivamente não para Python 3 (que não tem sys.maxint, e que usa uma função hash diferente).
intervalo de
0

A implementação para o tipo int em cpython pode ser encontrada aqui.

Ele apenas retorna o valor, exceto por -1, que retorna -2:

static long
int_hash(PyIntObject *v)
{
    /* XXX If this is changed, you also need to change the way
       Python's long, float and complex types are hashed. */
    long x = v -> ob_ival;
    if (x == -1)
        x = -2;
    return x;
}
Jieter
fonte
6
Isso não inclui valores grandes, que são implementados por em PyLongvez de PyInt.
intervalo de