O que é uma boa função Hash?

StackOverflow https://stackoverflow.com/questions/34595

Pergunta

O que é uma boa função Hash?Eu vi muitas funções e aplicativos hash em meus cursos de estruturas de dados na faculdade, mas principalmente percebi que é muito difícil criar uma boa função hash.Como regra geral para evitar colisões, meu professor disse que:

function Hash(key)
  return key mod PrimeNumber
end

(mod é o operador % em C e linguagens similares)

com o número primo sendo o tamanho da tabela hash.Entendo que é uma função boa para evitar colisões e rápida, mas como posso fazer uma função melhor?Existem funções hash melhores para chaves de string em relação a chaves numéricas?

Foi útil?

Solução

Para fazer pesquisas "normais" em tabelas hash em basicamente qualquer tipo de dados - esta de Paul Hsieh é a melhor que já usei.

http://www.azillionmonkeys.com/qed/hash.html

Se você se preocupa com segurança criptográfica ou qualquer outra coisa mais avançada, então YMMV.Se você deseja apenas uma função hash de uso geral incrível para uma pesquisa de tabela hash, então é isso que você está procurando.

Outras dicas

Não existe uma “boa função hash” para hashes universais (ed.sim, eu sei que existe “hashing universal”, mas não foi isso que eu quis dizer).Dependendo do contexto, diferentes critérios determinam a qualidade de um hash.Duas pessoas já mencionaram o SHA.Este é um hash criptográfico e não é nada bom para tabelas hash, o que você provavelmente quer dizer.

As tabelas hash têm requisitos muito diferentes.Mesmo assim, encontrar uma boa função hash universalmente é difícil porque diferentes tipos de dados expõem informações diferentes que podem ser criptografadas.Como regra geral, é bom considerar todos informações que um tipo contém igualmente.Isto nem sempre é fácil ou mesmo possível.Por razões estatísticas (e, portanto, de colisão), também é importante gerar uma boa distribuição no espaço do problema, ou seja,todos os objetos possíveis.Isso significa que ao fazer hash de números entre 100 e 1050, não é bom deixar o dígito mais significativo desempenhar um papel importante no hash porque para ~ 90% dos objetos, esse dígito será 0.É muito mais importante deixar os três últimos dígitos determinarem o hash.

Da mesma forma, ao fazer hash de strings, é importante considerar todos os caracteres – exceto quando for conhecido antecipadamente que os três primeiros caracteres de todas as strings serão iguais;considerá-los então é um desperdício.

Este é na verdade um dos casos em que aconselho a ler o que Knuth tem a dizer em A arte da programação de computadores, vol.3.Outra boa leitura é Julienne Walker A arte do hash.

Existem dois propósitos principais das funções hash:

  • para dispersar pontos de dados uniformemente em n bits.
  • para identificar com segurança os dados de entrada.

É impossível recomendar um hash sem saber para que você o está usando.

Se você está apenas criando uma tabela hash em um programa, não precisa se preocupar com o quão reversível ou hackeável é o algoritmo...SHA-1 ou AES é completamente desnecessário para isso, seria melhor usar um variação do FNV.O FNV atinge melhor dispersão (e, portanto, menos colisões) do que um simples mod principal como você mencionou e é mais adaptável a diversos tamanhos de entrada.

Se você estiver usando hashes para ocultar e autenticar informações públicas (como hash de uma senha ou de um documento), você deve usar um dos principais algoritmos de hash examinados pelo escrutínio público. Salão de funções Hash é um bom lugar para começar.

Este é um bom exemplo e também um exemplo de por que você nunca iria querer escrever um.É um Hash Fowler / Noll / Vo (FNV) que é em partes iguais de gênio da ciência da computação e puro vodu:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Editar:

  • Landon Curt Noll recomenda em o site dele o algoritmo FVN-1A sobre o algoritmo FVN-1 original:O algoritmo aprimorado dispersa melhor o último byte do hash.Eu ajustei o algoritmo de acordo.

Eu diria que a regra principal é não criar o seu próprio.Tente usar algo que tenha sido exaustivamente testado, por exemplo, SHA-1 ou algo parecido.

Uma boa função hash tem as seguintes propriedades:

  1. Dado um hash de uma mensagem, é computacionalmente inviável para um invasor encontrar outra mensagem de forma que seus hashes sejam idênticos.

  2. Dado um par de mensagens, m' e m, é computacionalmente inviável encontrar duas tais que h(m) = h(m')

Os dois casos são não o mesmo.No primeiro caso, há um hash pré-existente para o qual você está tentando encontrar uma colisão.No segundo caso, você está tentando encontrar qualquer duas mensagens que colidem.A segunda tarefa é significativamente mais fácil devido ao “paradoxo” do aniversário.

Onde o desempenho não for um problema tão grande, você deve sempre usar uma função hash segura.Existem ataques muito inteligentes que podem ser executados forçando colisões em um hash.Se você usar algo forte desde o início, você estará protegido contra isso.

Não use MD5 ou SHA-1 em novos designs.A maioria dos criptógrafos, inclusive eu, os consideraria quebrados.A principal fonte de fraqueza em ambos os projetos é que a segunda propriedade, que descrevi acima, não se aplica a estas construções.Se um invasor puder gerar duas mensagens, m e m', com hash do mesmo valor, ele poderá usar essas mensagens contra você.SHA-1 e MD5 também sofrem ataques de extensão de mensagem, que podem enfraquecer fatalmente seu aplicativo se você não tomar cuidado.

Um hash mais moderno como o Whirpool é uma escolha melhor.Ele não sofre esses ataques de extensão de mensagem e usa a mesma matemática que o AES usa para provar a segurança contra uma variedade de ataques.

Espero que ajude!

O que você está dizendo aqui é que deseja ter um que tenha resistência à colisão.Tente usar SHA-2.Ou tente usar uma (boa) cifra de bloco em uma função de compactação unilateral (nunca tentei isso antes), como AES no modo Miyaguchi-Preenel.O problema com isso é que você precisa:

1) ter um IV.Tente usar os primeiros 256 bits das partes fracionárias da constante de Khinchin ou algo parecido.2) tenha um esquema de preenchimento.Fácil.Carregue-o a partir de um hash como MD5 ou SHA-3 (Keccak [pronuncia-se 'ket-chak']).Se você não se importa com a segurança (alguns outros disseram isso), dê uma olhada em FNV ou lookup2 de Bob Jenkins (na verdade sou o primeiro que recomendo lookup2) Experimente também MurmurHash, é rápido (verifique isto:0,16 cpb).

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top