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

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)"?

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) = x \mod 100$

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.

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.

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.

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

*

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.

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.

2. 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".