O que o hash faz em python?

Eu vi um exemplo de código onde a hashfunção é aplicada a uma tupla. Como resultado, ele retorna um número inteiro negativo. Eu me pergunto o que essa função faz? O Google não ajuda. Encontrei uma página que explica como o hash é calculado, mas não explica por que precisamos dessa função.

Um hash é um número inteiro de tamanho fixo que identifica um valor específico . Cada valor precisa ter seu próprio hash, portanto, para o mesmo valor, você obterá o mesmo hash, mesmo que não seja o mesmo objeto.

>>> hash("Look at me!")
4343814758193556824
>>> f = "Look at me!"
>>> hash(f)
4343814758193556824

Os valores de hash precisam ser criados de forma que os valores resultantes sejam distribuídos uniformemente para reduzir o número de colisões de hash que você obtém. As colisões de hash ocorrem quando dois valores diferentes têm o mesmo hash. Portanto, mudanças relativamente pequenas geralmente resultam em hashes muito diferentes.

>>> hash("Look at me!!")
6941904779894686356

Esses números são muito úteis, pois permitem a consulta rápida de valores em uma grande coleção de valores. Dois exemplos de seu uso são Python's sete dict. Em a list, se você quiser verificar se um valor está na lista, com if x in values:, Python precisa percorrer toda a lista e comparar xcom cada valor na lista values. Isso pode levar muito tempo list. Em a set, o Python rastreia cada hash e, quando você digita if x in values:, o Python obtém o valor do hash para x, procura-o em uma estrutura interna e depois compara apenas xcom os valores que têm o mesmo hash que x.

A mesma metodologia é usada para pesquisa de dicionário. Isso torna a pesquisa em sete dictmuito rápida, enquanto a pesquisa em listé lenta. Também significa que você pode ter objetos não hashable em a list, mas não em a setou como chaves em a dict. O exemplo típico de objetos sem hash é qualquer objeto mutável, o que significa que você pode alterar seu valor. Se você tiver um objeto mutável, ele não deve ser hash, pois seu hash mudará ao longo de sua vida útil, o que causaria muita confusão, pois um objeto poderia terminar com o valor de hash errado em um dicionário.

Observe que o hash de um valor só precisa ser o mesmo para uma execução do Python. No Python 3.3, eles mudarão de fato a cada nova execução do Python:

$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
1849024199686380661
>>> 
$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
-7416743951976404299

Isso torna mais difícil adivinhar qual valor hash uma determinada string terá, que é um recurso de segurança importante para aplicativos da web, etc.

Os valores de hash, portanto, não devem ser armazenados permanentemente. Se você precisar usar valores de hash de forma permanente, poderá dar uma olhada nos tipos mais "sérios" de hashes, funções de hash criptográficas , que podem ser usados ​​para fazer somas de verificação verificáveis ​​de arquivos etc.

TL; DR:

Consulte o glossário : hash()é usado como um atalho para a comparação de objetos, um objeto é considerado hashable se puder ser comparado a outros objetos. é por isso que usamos hash(). Ele também é usado para acessar dicte setelementos que são implementados como tabelas hash redimensionáveis ​​em CPython .

Considerações técnicas

• geralmente comparar objetos (o que pode envolver vários níveis de recursão) é caro.
• de preferência, a hash()função é uma ordem de magnitude (ou várias) menos cara.
• comparar dois hashes é mais fácil do que comparar dois objetos, é aqui que está o atalho.

Se você ler sobre como os dicionários são implementados , eles usam tabelas hash, o que significa que derivar uma chave de um objeto é uma pedra angular para recuperar objetos em dicionários em O(1). No entanto, isso depende muito da sua função hash para ser resistente a colisões . O pior caso para obter um item em um dicionário é realmente O(n).

Nessa nota, objetos mutáveis ​​geralmente não são hashable. A propriedade hashable significa que você pode usar um objeto como uma chave. Se o valor hash for usado como uma chave e o conteúdo desse mesmo objeto for alterado, o que a função hash deve retornar? É a mesma chave ou diferente? Ele depende de como você define a sua função hash.

Aprendendo pelo exemplo:

Imagine que temos esta aula:

>>> class Person(object):
...     def __init__(self, name, ssn, address):
...         self.name = name
...         self.ssn = ssn
...         self.address = address
...     def __hash__(self):
...         return hash(self.ssn)
...     def __eq__(self, other):
...         return self.ssn == other.ssn
... 

Observação: tudo isso se baseia na suposição de que o SSN nunca muda para um indivíduo (nem mesmo sei onde verificar esse fato de uma fonte confiável).

E nós temos Bob:

>>> bob = Person('bob', '1111-222-333', None)

Bob vai ver um juiz para mudar seu nome:

>>> jim = Person('jim bo', '1111-222-333', 'sf bay area')

Isso é o que sabemos:

>>> bob == jim
True

Mas esses são dois objetos diferentes com memória alocada diferente, assim como dois registros diferentes da mesma pessoa:

>>> bob is jim
False

Agora vem a parte em que o hash () é útil:

>>> dmv_appointments = {}
>>> dmv_appointments[bob] = 'tomorrow'

Adivinha:

>>> dmv_appointments[jim] #?
'tomorrow'

A partir de dois registros diferentes, você pode acessar as mesmas informações. Agora tente isto:

>>> dmv_appointments[hash(jim)]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 9, in __eq__
AttributeError: 'int' object has no attribute 'ssn'
>>> hash(jim) == hash(hash(jim))
True

O que acabou de acontecer? Isso é uma colisão. Porque hash(jim) == hash(hash(jim))ambos são inteiros btw, precisamos comparar a entrada de __getitem__com todos os itens que colidem. O embutido intnão tem um ssnatributo, então ele desarma.

>>> del Person.__eq__
>>> dmv_appointments[bob]
'tomorrow'
>>> dmv_appointments[jim]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: <__main__.Person object at 0x7f611bd37110>

Neste último exemplo, mostro que mesmo com uma colisão, a comparação é realizada, os objetos não são mais iguais, o que significa que levanta a com sucesso KeyError.

A documentação dohash() Python para o estado:

Os valores de hash são inteiros. Eles são usados ​​para comparar rapidamente as chaves do dicionário durante uma pesquisa no dicionário.

Os dicionários Python são implementados como tabelas hash. Portanto, sempre que você usa um dicionário, hash()é chamado nas chaves que você passa para a atribuição, ou consulta.

Além disso, os documentos para odict estado do tipo :

Os valores que não são hashable , ou seja, os valores que contêm listas, dicionários ou outros tipos mutáveis ​​(que são comparados por valor em vez de identidade de objeto) não podem ser usados ​​como chaves.

O hash é usado por dicionários e conjuntos para pesquisar rapidamente o objeto. Um bom ponto de partida é o artigo da Wikipedia sobre tabelas de hash .

Você pode usar o Dictionarytipo de dados em python. É muito semelhante ao hash - e também suporta aninhamento, semelhante ao hash aninhado.

Exemplo:

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School" # Add new entry

print ("dict['Age']: ", dict['Age'])
print ("dict['School']: ", dict['School'])

Para obter mais informações, consulte este tutorial sobre o tipo de dados do dicionário .