O que exatamente (e precisamente) é "hash"?

38

Eu ouvi a palavra "hash" sendo usada em diferentes contextos (todos no mundo da computação) com significados diferentes. Por exemplo, no livro Aprenda Python da maneira mais difícil, no capítulo sobre dicionários , diz-se "Python os chama de" dictos ". Outras línguas os chamam de" hashes "." Então, são dicionários de hashes?

O outro uso comum da palavra está relacionado à criptografia. Também ouvi (e li) pessoas usando a palavra "hash" como uma função específica dentro da programação de alto nível.

Então, o que exatamente é isso?

Alguém (com o tempo e com conhecimento) pode explicar gentilmente os detalhes de "hash (ou hashes)"?

agraciado
fonte
8
A Wikipedia possui artigos detalhados sobre tabelas de hash e funções de hash criptográfico . O que você está procurando que não está naqueles?
David Richerby
11
Você já lista vários usos do termo "hash" e há mais. Então, como exatamente você espera obter uma resposta para "o que exatamente é isso?"
Raphael
4
"Hash" nesse sentido é um encurtamento de "Hash tables", por exemplo, tabelas que usam hashes para organização de chaves. É como chamar gasolina de "gás" - você não espera que "gás" seja gasoso ou que gases tenham propriedades semelhantes à gasolina, não é? Isso acontece o tempo todo com o idioma - o encurtamento, em particular, é uma fonte muito comum de sobreposição de palavras.
Luaan
11
"Não há definição para esta palavra - ninguém sabe o que é hash". - Dicionário do Diabo
jpmc26 6/16
Nos diferentes trens de pensamento o que é uma função hash: uma função hash é apenas uma função com várias propriedades, mas não é como é definido que é relevante, são as propriedades que queremos que ele tenha - das quais derivamos como queremos para usar a função - isso é relevante. Como queremos usá-lo para acessar coisas rapidamente, queremos que seja computado com eficiência. Como não temos espaço infinito disponível, queremos que o codomain seja finito. Como queremos evitar colisões da melhor maneira possível, queremos que a função hash espalhe os hashes uniformemente.
G. Bach

Respostas:

44

O artigo da Wikipedia sobre funções de hash é muito bom, mas eu darei aqui minha opinião.


O que é um hash?

"Hash" é realmente um termo amplo, com diferentes significados formais em diferentes contextos. Não existe uma única resposta perfeita para sua pergunta. Vou explicar o conceito geral subjacente e mencionar alguns dos usos mais comuns do termo.

Um "hash" é uma função denominada função de hash que recebe como objetos de entrada e gera uma string ou número. Os objetos de entrada geralmente são membros de tipos de dados básicos, como seqüências de caracteres, números inteiros ou maiores compostos por outros objetos, como estruturas definidas pelo usuário. A saída é tipicamente um número ou uma sequência. O substantivo "hash" geralmente se refere a essa saída. O verbo "hash" geralmente significa "aplicar uma função hash". As principais propriedades que uma função hash deve ter são:h

  1. Deve ser fácil calcular e
  2. As saídas devem ser relativamente pequenas.

Exemplo:

Digamos que queremos números de hash no intervalo de 0 a 999.999.999 para numerar entre 0 e 99. Uma função simples de hash pode ser .h(x)=xmod100

Propriedades adicionais comuns:

Dependendo do caso de uso, podemos desejar que a função hash satisfaça propriedades adicionais. Aqui estão algumas propriedades adicionais comuns:

  1. Uniformidade : Muitas vezes queremos que os hashes dos objetos sejam distintos. Além disso, podemos querer que os hashes sejam "espalhados". Se eu quiser misturar alguns objetos em 100 buckets (para que a saída da minha função hash seja um número de 0 a 99), normalmente espero que cerca de 1/100 de objetos cheguem ao balde 0, e cerca de 1/100 balde 1 e assim por diante.

  2. Resistência à colisão criptográfica : Às vezes, isso é levado ainda mais longe, por exemplo, na criptografia, eu posso querer uma função hash de modo que seja computacionalmente difícil para um adversário encontrar duas entradas diferentes que mapeiam a mesma saída.

  3. Compactação : muitas vezes eu quero misturar entradas arbitrariamente grandes em uma saída de tamanho constante ou em um número fixo de buckets.

  4. Determinismo : talvez eu queira uma função hash cuja saída não mude entre as execuções, ou seja, a saída da função hash no mesmo objeto permanecerá sempre a mesma. Isso pode parecer conflitar com a uniformidade acima, mas uma solução é escolher a função hash aleatoriamente uma vez e não alterá-la entre as execuções.


Algumas aplicações

Um aplicativo comum está em estruturas de dados, como uma tabela de hash, que são uma maneira de implementar dicionários. Aqui, você aloca um pouco de memória, digamos, 100 "baldes"; quando solicitado a armazenar um par (chave, valor) no dicionário, você hash a chave em um número de 0 a 99 e armazene o par no intervalo correspondente na memória. Em seguida, quando você for solicitado a procurar uma chave, faça o hash da chave em um número de 0 a 99 com a mesma função de hash e verifique o balde para ver se essa chave está lá. Nesse caso, você retorna seu valor.

Observe que você também pode implementar dicionários de outras maneiras, como em uma árvore de pesquisa binária (se seus objetos forem comparáveis).

Outra aplicação prática são as somas de verificação, que são maneiras de verificar se dois arquivos são iguais (por exemplo, o arquivo não foi corrompido em sua versão anterior). Como é improvável que as funções de hash mapeiem duas entradas para a mesma saída, você calcula e armazena um hash do primeiro arquivo, geralmente representado como uma string. Esse hash é muito pequeno, talvez apenas algumas dezenas de caracteres ASCII. Então, quando você obtém o segundo arquivo, faz o hash e verifica se a saída é a mesma. Nesse caso, quase certamente é exatamente o mesmo arquivo, byte por byte.

Outra aplicação é na criptografia, onde esses hashes devem ser difíceis de "inverter" - ou seja, dada a saída e a função hash, deve ser computacionalmente difícil descobrir as entradas que levaram a essa saída. Um uso disso é para senhas: em vez de armazenar a senha em si, você armazena um hash criptográfico da senha (talvez com alguns outros ingredientes). Em seguida, quando um usuário digita uma senha, você calcula seu hash e verifica se ele corresponde ao hash correto; Nesse caso, você diz que a senha está correta. (Agora, mesmo alguém que pode procurar e descobrir o hash salvo no servidor não fica tão fácil fingir ser o usuário.) Esse aplicativo pode ser um caso em que a saída seja tão longa ou mais longa que a entrada, pois a entrada é tão curta.

usul
fonte
11
Boa explicação, mas não concordo com "muito improvável". Veja: programmers.stackexchange.com/questions/49550/... : colisão fazer ocorrer, e às vezes com uma freqüência surpreendente.
Olivier Dulac
8
Observe também que, no contexto da criptografia, o termo "hash" implica fortemente uma operação "unidirecional" que não pode ser facilmente revertida na prática. Quando pode ser facilmente revertida, é chamada de "criptografia". É por isso que as pessoas no Security.SE dizem para você sempre hash as senhas dos seus clientes, nunca para criptografá-las.
Ixrec
4
Um hash que não "se espalha" ainda é um hash, talvez não seja muito bom para o seu aplicativo.
parar de prejudicar Monica
11
Claro, todos esses são bons pontos.
usul
10

Uma função hash é uma função que recebe uma entrada e produz um valor de tamanho fixo. Por exemplo, você pode ter uma função de hash stringHashque aceita um stringde qualquer tamanho e produz um número inteiro de 32 bits.

Normalmente, é correto dizer que a saída de uma função de hash é um hash (também conhecido como valor de hash ou soma de hash). No entanto, às vezes as pessoas se referem à função em si como um hash . Isso é tecnicamente incorreto, mas geralmente é ignorado, pois geralmente é entendido (no contexto) que a pessoa quis dizer função hash .

O uso típico de uma função de hash é implementar uma tabela de hash . Uma tabela de hash é uma estrutura de dados que associa valores a outros valores geralmente chamados de chaves. Ele faz isso usando uma função de hash na chave para produzir um valor de hash de tamanho fixo que pode ser usado para pesquisar rapidamente os dados que ele armazena. Não vou entrar em detalhes completos sobre como isso acontece, mas o fato principal aqui é que ela é chamada de tabela de hash porque depende de uma função de hash para produzir valores de hash (hashes).

É aqui que entra a confusão, porque algumas pessoas (novamente, de maneira incorreta) se referem a uma tabela de hash como um hash. Conforme declarado em outras respostas, às vezes a implementação de uma tabela de hash de um determinado idioma se refere à tabela de hash como um hash (notavelmente o Perl faz isso, embora eu espere que outros idiomas também). Outros idiomas optam por se referir à implementação de uma tabela de hash como um dicionário. O Python é uma dessas linguagens, mas, devido ao quão arraigadas elas são, muitos usuários do Python abreviam o termo dicionário para 'ditar'.

Portanto, embora o uso correto do termo hash seja para se referir ao valor de hash produzido por uma função de hash , as pessoas também usam o termo informalmente para se referir a funções de hash e tabelas de hash , criando assim a confusão.

Pharap
fonte
2
Não tenho certeza se é realmente incorreto referir-se a uma tabela de hash ou função de hash como um "hash" (não parece pior do que, por exemplo, usar "Washington" para significar "os Estados Unidos", como em " Washington recebeu com cautela a declaração da China "). Mas concordo que é confuso e é bom que você seja muito claro sobre isso em sua resposta.
precisa saber é o seguinte
11
@DavidRicherby Formalmente, eu diria que o trabalho "hash" é indefinido. "Função hash", "valor hash", "tabela hash" e "hash uma string" têm definições matemáticas precisas, mas "hash" é ambíguo. Da mesma forma, eu sei o que você quer dizer com "Washington", mas sua sentença ainda faz sentido se eu interpretar "Washington" como "George Washington" ou "Denzel Washington" em vez de "A cidade de Washington", que é uma maneira altamente informal para se referir ao governo federal. Conclusão: tenha cuidado para não confundir "saber o que você quer dizer" com uma definição formal rigorosa.
Mike Ounsworth
@DavidRicherby Isso não é realmente uma analogia equivalente. O erro é discutível, mas a informalidade não.
Pharap
2

Uma função hash é amplamente qualquer função em que a imagem seja menor que o domínio . A saída dessa função f(x)pode ser chamada de "o hash de x".

Na ciência da computação, normalmente encontramos duas aplicações de funções hash.

O primeiro é para estruturas de dados como tabelas de hash , nas quais queremos mapear o domínio da chave (por exemplo, números inteiros de 32 bits ou cadeias de comprimento arbitrário) para um índice de matriz (por exemplo, número inteiro entre 0 e 100). O objetivo aqui é maximizar o desempenho da estrutura de dados; As propriedades da função hash que normalmente são desejáveis ​​são a simplicidade e a distribuição uniforme da saída.

O Perl chama seu tipo de array associativo interno de "hash" , que parece ser o que está causando sua confusão aqui. Não conheço outras línguas que fazem isso. Vagamente, a estrutura de dados pode ser vista como uma função de hash (onde o domínio é o conjunto de chaves atual), mas também é implementada como uma tabela de hash.

O segundo é para criptografia : autenticação de mensagens, verificação de senha / assinatura, etc. O domínio é tipicamente seqüências de bytes arbitrárias. Aqui estamos preocupados com a segurança - que às vezes significa desempenho deliberadamente baixo - em que propriedades úteis são resistência à colisão e à pré-imagem.

Pare de prejudicar Monica
fonte
E ainda tenho objeções à sua primeira frase, porque ao fazer o hash de senhas de 32 caracteres com o SHA-512, o espaço de entrada é realmente menor que o espaço de saída. Ao encadear funções de hash, o domínio e o intervalo são os mesmos; o tamanho do espaço de entrada é irrelevante. A resposta de Pharap tem a definição correta: "Uma função hash é qualquer função com uma saída de comprimento fixo". É isso, é tudo o que você precisa, todas as outras condições de que você está falando estão implícitas nisso.
Mike Ounsworth
@MikeOunsworth, mas o domínio do SHA-512 é uma sequência binária de comprimento arbitrário. Suponho que poderia roubar as palavras de Pharaps, mas estava tentando explicitar as condições para o benefício do OP. Na verdade, não tenho certeza de que "de comprimento fixo" seja necessário, nem definido de forma inequívoca.
parar de prejudicar Monica
@OrangeDog Ok, mas posso envolver o SHA-512 dentro de uma função chamada MikesHash()que aceita cadeias de comprimento 12 e as passa para o SHA-512 e retorna a saída. Tenho certeza de que MikesHash()ainda atende à definição de uma função hash. (Na prática, você está certo, as funções hash que usamos aceitar entradas arbitrária de comprimento, mas eu não acho que algo falha em ser uma função hash se isso não acontecer.)
Mike Ounsworth
@ MikeOunsworth da mesma forma, posso envolvê-lo de modo que a saída seja truncada ou preenchida se o msb for um. A saída não é mais de comprimento fixo, mas ainda é uma função de hash?
parar de prejudicar Monica
@OrangeDog, eu diria que não. Meu argumento o tempo todo foi que uma função hash deve mapear para uma saída de tamanho fixo, mas o tamanho da entrada é irrelevante. Chegamos muito longe do assunto. Sua resposta tem coisas boas nele, basta ter cuidado com a sua definição formal ;-)
Mike Ounsworth
0

Grande pergunta Basil Ajith,

Aqui está a minha perspectiva do que é um hash para algo em que estou trabalhando hoje.

*

Use a soma de verificação para verificar se o tarball possui é congruente com a página de download

*

insira a descrição da imagem aqui Coloca o chapéu de auditor, quero dizer roupão de mago

hash é um valor / string / qualquer que seja / label, verifique se é o mesmo em sua máquina como a fonte de um download.

Jesse MacDougall
fonte
3
Este é apenas um uso para um hash. Existem muitos outros usos.
Yuval Filmus
Bem vindo ao site! O uso de hashes criptográficos como somas de verificação já está coberto pela resposta aceita, para que sua resposta não adicione nada de novo, além de ocupar muito espaço na tela.
precisa saber é o seguinte
-1

Vou tentar apenas adicionar um breve resumo do que os outros dizem.

Função hash

Há um tipo especial de funções chamadas funções de hash.

"SHA256 é uma função hash bem conhecida que é criptograficamente segura"

Três aplicações principais são * tabelas de hash, * somas de verificação (verificações de integridade de dados, por exemplo, em discos rígidos ou protocolos ADSL) * e criptografia (várias formas de autenticação criptográfica, incluindo, entre outras, assinaturas digitais e armazenamento seguro de senhas).

Tabela de hash

A tabela de hash é uma estrutura de dados para pesquisa rápida. Ele usa funções de hash internamente, daí o nome.

"Os bancos de dados usam tabelas de hash e árvores de pesquisa internamente para acelerar a execução de solicitações de pesquisa"

Jogo da velha

  1. um tipo de dados abstratos do dicionário

"Hash" é o nome oficial dos dicionários internos no Perl. São tabelas de hash internamente, daí o nome. "Esta sub-rotina aceita um hash como seu primeiro argumento". Estes dias podem ser usados ​​para qualquer matriz associativa, não necessariamente uma tabela de hash.

  1. resultado da aplicação de uma função hash em alguma entrada

"Os hashes MD5 das imagens .iso são fornecidos para verificar sua integridade após o download".

nponeccop
fonte