O que é uma boa função Hash?

O que é uma boa função Hash? Vi muitas funções e aplicativos de hash em meus cursos de estruturas de dados na faculdade, mas percebi que é muito difícil criar uma boa função de 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 idiomas semelhantes)

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

Para fazer pesquisas "normais" da tabela de hash em basicamente qualquer tipo de dados - este de Paul Hsieh é o melhor que eu já usei.

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

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

Não existe uma “boa função hash” para hashes universais (ed. Sim, eu sei que existe algo como “hash 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 SHA. Este é um hash criptográfico e não é bom para tabelas de hash, o que você provavelmente quer dizer.

As tabelas de hash têm requisitos muito diferentes. Ainda assim, é difícil encontrar uma boa função de hash universalmente, porque tipos de dados diferentes expõem informações diferentes que podem ser hash. Como regra geral, é bom considerar todas as informações que um tipo mantém igualmente. Isso nem sempre é fácil ou até possível. Por razões de estatística (e, portanto, colisão), também é importante gerar uma boa dispersão no espaço do problema, ou seja, todos os objetos possíveis. Isso significa que, ao fazer o 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 determinam o hash.

Da mesma forma, ao fazer hash de strings, é importante considerar todos os caracteres - exceto quando se sabe de antemão que os três primeiros caracteres de todas as strings serão os mesmos; considerando estes, então, é um desperdício.

Este é realmente um dos casos em que aconselho a ler o que Knuth tem a dizer em The Art of Computer Programming , vol. 3. Outra boa leitura é The Art of Hashing, de Julienne Walker .

Existem dois objetivos principais das funções de hash:

• 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 de hash em um programa, não precisa se preocupar com o quão reversível ou hackável é o algoritmo ... SHA-1 ou AES é completamente desnecessário para isso, é melhor usar uma variação do FNV . O FNV alcança melhor dispersão (e, portanto, menos colisões) do que um mod simples, como você mencionou, e é mais adaptável a diferentes tamanhos de entrada.

Se você estiver usando os hashes para ocultar e autenticar informações públicas (como hash de uma senha ou de um documento), use um dos principais algoritmos de hash verificados pelo escrutínio público. O Hash Function Lounge é um bom lugar para começar.

Este é um exemplo de uma boa e também um exemplo de por que você nunca iria querer escrever uma. É um Hash Fowler / Noll / Vo (FNV) que é 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 seu site o algoritmo FVN-1A sobre o algoritmo original FVN-1: O algoritmo aprimorado dispersa melhor o último byte no hash. Eu ajustei o algoritmo de acordo.

Eu diria que a principal regra geral é não rolar a sua. Tente usar algo que foi completamente testado, por exemplo, SHA-1 ou algo nesse sentido.

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

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

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

Os dois casos não são os mesmos. No primeiro caso, existe um hash pré-existente para o qual você está tentando encontrar uma colisão. No segundo caso, você está tentando encontrar quaisquer duas mensagens que se chocam. A segunda tarefa é significativamente mais fácil devido ao "paradoxo" do aniversário.

Onde o desempenho não é um problema tão grande, você sempre deve 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, se protegerá disso.

Não use MD5 ou SHA-1 em novos modelos. 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 essas construções. Se um invasor pode gerar duas mensagens, m e m ', que ambos hash com o mesmo valor, eles podem usar essas mensagens contra você. O SHA-1 e o 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 com 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 que um que use tenha resistência à colisão. Tente usar o SHA-2. Ou tente usar uma (boa) cifra de bloco em uma função de compressão unidirecional (nunca tentei isso antes), como o AES no modo Miyaguchi-Preenel. O problema é que você precisa:

1) ter um IV. Tente usar os primeiros 256 bits das partes fracionárias da constante de Khinchin ou algo assim. 2) tem um esquema de preenchimento. Fácil. Carrinho de mão 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), veja o FNV ou o lookup2 de Bob Jenkins (na verdade, eu sou o primeiro a recomendar lookup2). Tente também o MurmurHash, é rápido (verifique: 0,16 cpb )