Qual algoritmo de hash é melhor para exclusividade e velocidade? Exemplos de usos (bons) incluem dicionários de hash.

Eu sei que existem coisas como SHA-256 e outras, mas esses algoritmos são projetados para serem seguros , o que geralmente significa que eles são mais lentos que os algoritmos menos exclusivos . Eu quero um algoritmo de hash projetado para ser rápido, mas ainda assim ser único para evitar colisões.

Testei alguns algoritmos diferentes, medindo a velocidade e o número de colisões.

Eu usei três conjuntos de chaves diferentes:

• Uma lista de 216.553 palavras em inglês (em minúsculas)
• Os números "1"para "216553"(pense em códigos postais e como um hash ruim derrubou o msn.com )
• 216.553 GUIDs "aleatórios" (isto é, uuid tipo 4 )

Para cada corpus, foi registrado o número de colisões e o tempo médio gasto em hash.

Eu testei:

• DJB2
• DJB2a (variante usando em xorvez de +)
• FNV-1 (32 bits)
• FNV-1a (32 bits)
• SDBM
• CRC32
• Murmur2 (32 bits)
• SuperFastHash

Resultados

Cada resultado contém o tempo médio de hash e o número de colisões

Hash           Lowercase      Random UUID  Numbers
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis▪
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis▪▪▪
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis▪▪▪
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis

Notas :

• O algoritmo LoseLose (onde hash = hash + caractere) é realmente terrível . Tudo colide com os mesmos 1.375 baldes
• O SuperFastHash é rápido, com coisas bem dispersas; pelo meu Deus, o número de colisões. Espero que o cara que a transportou tenha algo errado; é muito ruim
• CRC32 é muito bom . Mais lento e uma tabela de pesquisa de 1k

As colisões realmente acontecem?

Sim. Comecei a escrever meu programa de teste para ver se as colisões de hash realmente acontecem - e não são apenas uma construção teórica. Eles realmente acontecem:

Colisões FNV-1

• creamwove colide com quists

Colisões FNV-1a

• costarring colide com liquid
• declinate colide com macallums
• altarage colide com zinke
• altarages colide com zinkes

Colisões Murmur2

• cataract colide com periti
• roquette colide com skivie
• shawl colide com stormbound
• dowlases colide com tramontane
• cricketings colide com twanger
• longans colide com whigs

Colisões DJB2

• hetairas colide com mentioner
• heliotropes colide com neurospora
• depravement colide com serafins
• stylist colide com subgenera
• joyful colide com synaphea
• redescribed colide com urites
• dram colide com vivency

Colisões DJB2a

• haggadot colide com loathsomenesses
• adorablenesses colide com rentability
• playwright colide com snush
• playwrighting colide com snushing
• treponematoses colide com waterbeds

Colisões CRC32

• codding colide com gnu
• exhibiters colide com schlager

Colisões SuperFastHash

• dahabiah colide com drapability
• encharm colide com enclave
• grahams colide com gramary
• ... corta 79 colisões ...
• night colide com vigil
• nights colide com vigils
• finks colide com vinic

Randomnessification

A outra medida subjetiva é a distribuição aleatória dos hashes. O mapeamento das HashTables resultantes mostra a distribuição uniforme dos dados. Todas as funções hash mostram boa distribuição ao mapear linearmente a tabela:

Ou como um mapa de Hilbert (o XKCD é sempre relevante ):

Exceto quando hash cadeias numéricas ( "1", "2", ..., "216553") (por exemplo, zip codes ), onde os padrões começam a surgir na maioria dos algoritmos de hash:

SDBM :

DJB2a :

FNV-1 :

Todos, exceto o FNV-1a , que ainda parecem bastante aleatórios para mim:

Na verdade, Murmur2 parece ter ainda melhor aleatoriedade com Numbersque FNV-1a:

Quando olho para o FNV-1amapa "número", acho que vejo padrões verticais sutis. Com Murmur, não vejo nenhum padrão. O que você acha?

O extra *na tabela indica quão ruim é a aleatoriedade. Com FNV-1asendo o melhor e DJB2xser o pior:

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

Originalmente, escrevi este programa para decidir se eu precisava me preocupar com colisões: sim.

E, em seguida, tornou-se garantir que as funções de hash fossem suficientemente aleatórias.

Algoritmo FNV-1a

O hash FNV1 vem em variantes que retornam hashes de 32, 64, 128, 256, 512 e 1024 bits.

O algoritmo FNV-1a é:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Onde as constantes FNV_offset_basise FNV_primedependem do tamanho do hash de retorno desejado:

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

Veja a página principal do FNV para detalhes.

Todos os meus resultados estão com a variante de 32 bits.

FNV-1 melhor que FNV-1a?

Não. O FNV-1a está bem melhor. Houve mais colisões com o FNV-1a ao usar a palavra em inglês corpus:

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

Agora compare letras minúsculas e maiúsculas:

Hash    lowercase word Collisions  UPPERCASE word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

Nesse caso, o FNV-1a não é "400%" pior que o FN-1, apenas 20% pior.

Penso que o mais importante é que existem duas classes de algoritmos quando se trata de colisões:

• colisões raras : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
• colisões comuns : SuperFastHash, Loselose

E ainda há a distribuição uniforme dos hashes:

• excelente distribuição: Murmur2, FNV-1a, SuperFastHas
• excelente distribuição: FNV-1
• boa distribuição: SDBM, DJB2, DJB2a
• distribuição horrível: Loselose

Atualizar

Murmúrio? Claro, por que não

Atualizar

@whatshisname imaginou como seria o desempenho de um CRC32 , acrescentando números à tabela.

CRC32 é muito bom . Poucas colisões, porém mais lentas, e a sobrecarga de uma tabela de pesquisa de 1k.

Cortar todas as coisas erradas sobre a distribuição de CRC - meu mal

Até hoje eu usava o FNV-1a como meu algoritmo de hash de tabela de hash de fato . Mas agora estou mudando para o Murmur2:

• Mais rápido
• Melhor aleatorização de todas as classes de entrada

E eu realmente, realmente espero que haja algo de errado com o SuperFastHashalgoritmo que eu encontrei ; é muito ruim ser tão popular quanto é.

Update: A partir da página inicial MurmurHash3 no Google :

(1) - O SuperFastHash possui propriedades de colisão muito ruins, que foram documentadas em outros lugares.

Então acho que não sou só eu.

Atualização: eu percebi por que Murmuré mais rápido que os outros. MurmurHash2 opera em quatro bytes de cada vez. A maioria dos algoritmos é byte a byte :

for each octet in Key
   AddTheOctetToTheHash

Isso significa que, à medida que as teclas ficam mais longas, o Murmur tem a chance de brilhar.

Atualizar

Os GUIDs são projetados para serem exclusivos, não aleatórios

Uma publicação oportuna de Raymond Chen reitera o fato de que os GUIDs "aleatórios" não devem ser usados ​​por sua aleatoriedade. Eles, ou um subconjunto deles, não são adequados como chave de hash:

Mesmo o algoritmo GUID da versão 4 não é garantido como imprevisível, porque o algoritmo não especifica a qualidade do gerador de números aleatórios. O artigo da Wikipedia para GUID contém pesquisas primárias que sugerem que GUIDs futuros e anteriores podem ser previstos com base no conhecimento do estado do gerador de números aleatórios, já que o gerador não é criptograficamente forte.

Aleatoriedade não é o mesmo que evitar colisões; é por isso que seria um erro tentar inventar seu próprio algoritmo de "hash" usando um subconjunto de um guia "aleatório":

int HashKeyFromGuid(Guid type4uuid)
{
   //A "4" is put somewhere in the GUID.
   //I can't remember exactly where, but it doesn't matter for
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);
}

Nota : Mais uma vez, coloquei "GUID aleatório" entre aspas, porque é a variante "aleatória" de GUIDs. Uma descrição mais precisa seria Type 4 UUID. Mas ninguém sabe o que são os tipos 4 ou 1, 3 e 5. Portanto, é mais fácil chamá-los de GUIDs "aleatórios".

Todas as palavras em inglês mirrors

• https://web.archive.org/web/20070221060514/http://www.sitopreferito.it/html/all_english_words.html
• https://drive.google.com/file/d/0B3BLwu7Vb2U-dEw1VkUxc3U4SG8/view?usp=sharing

Se você deseja criar um mapa de hash a partir de um dicionário imutável, considere https://en.wikipedia.org/wiki/Perfect_hash_function - durante a construção da função e da tabela de hash, você pode garantir, para um determinado conjunto de dados, que não haverá colisões.

Aqui está uma lista de funções de hash, mas a versão curta é:

Se você quer apenas ter uma boa função de hash e não pode esperar, djb2é uma das melhores funções de hash de string que eu conheço. Possui excelente distribuição e velocidade em diversos conjuntos de chaves e tamanhos de mesa

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

O CityHash do Google é o algoritmo que você está procurando. Não é bom para criptografia, mas é bom para gerar hashes exclusivos.

Leia o blog para mais detalhes e o código está disponível aqui .

CityHash é escrito em C ++. Também há uma porta C simples .

Sobre o suporte de 32 bits:

Todas as funções do CityHash são ajustadas para processadores de 64 bits. Dito isso, eles serão executados (exceto os novos que usam SSE4.2) no código de 32 bits. Eles não serão muito rápidos. Você pode usar Murmur ou outra coisa no código de 32 bits.

Plotamos uma comparação rápida de velocidade de diferentes algoritmos de hash ao fazer o hash de arquivos.

Os gráficos individuais diferem apenas ligeiramente no método de leitura e podem ser ignorados aqui, pois todos os arquivos foram armazenados em um tmpfs. Portanto, a referência não era vinculada a IO se você está se perguntando.

• Escala linear
• Escala logarítmica

Algoritmos incluem: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Conclusões:

• Funções de hash não criptográficas como Murmur3, Cityhash e Spooky estão bem próximas. Deve-se notar que o Cityhash pode ser mais rápido em CPUs com CRCinstruções SSE 4.2s , que minha CPU não possui. O SpookyHash estava no meu caso sempre um pouquinho antes do CityHash.
• O MD5 parece ser uma boa alternativa ao usar funções hash criptográficas, embora o SHA256 possa ser mais seguro para as vulnerabilidades de colisão do MD5 e SHA1.
• A complexidade de todos os algoritmos é linear - o que não é realmente surpreendente, pois eles funcionam em blocos. (Eu queria ver se o método de leitura faz diferença, para que você possa comparar os valores mais à direita).
• O SHA256 foi mais lento que o SHA512.
• Não investiguei a aleatoriedade das funções de hash. Mas aqui está uma boa comparação das funções de hash que estão faltando na resposta de Ian Boyds . Isso indica que o CityHash tem alguns problemas nos casos de canto.

A fonte usada para as parcelas:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (desculpe pelo código feio)

Os algoritmos SHA (incluindo SHA-256) foram projetados para serem rápidos .

De fato, sua velocidade pode ser um problema às vezes. Em particular, uma técnica comum para armazenar um token derivado de senha é executar um algoritmo de hash rápido padrão 10.000 vezes (armazenando o hash do hash do hash do hash da senha ...).

#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }
  v
end

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end

Resultado:

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

Eu sei que existem coisas como SHA-256 e outras, mas esses algoritmos são projetados para serem seguros , o que geralmente significa que eles são mais lentos que os algoritmos menos exclusivos .

A suposição de que as funções de hash criptográfico são mais exclusivas está errada e, de fato, pode ser demonstrado que, na prática, muitas vezes é invertido. Em verdade:

1. Idealmente, as funções de hash criptográfico devem ser indistinguíveis de aleatórias ;
2. Mas com funções hash não criptográficas, é desejável que elas interajam favoravelmente com entradas prováveis .

O que significa que uma função hash não criptográfica pode ter menos colisões que uma função criptográfica para um conjunto de dados "bom" - conjuntos de dados para os quais foi projetado.

Podemos demonstrar isso com os dados da resposta de Ian Boyd e um pouco de matemática: o problema do aniversário . A fórmula para o número esperado de pares em colisão, se você escolher nnúmeros inteiros aleatoriamente do conjunto, [1, d]é esta (retirada da Wikipedia):

n - d + d * ((d - 1) / d)^n

Ao nligar = 216.553 e d= 2 ^ 32, obtemos cerca de 5,5 colisões esperadas . Os testes de Ian mostram principalmente resultados em torno desse bairro, mas com uma exceção dramática: a maioria das funções teve zero colisão nos testes consecutivos de números. A probabilidade de escolher 216.553 números de 32 bits aleatoriamente e obter zero colisão é de cerca de 0,43%. E isso é apenas para uma função - aqui temos cinco famílias distintas de funções de hash com zero colisão!

Então, o que estamos vendo aqui é que os hashes que Ian testou estão interagindo favoravelmente com o conjunto de dados de números consecutivos - ou seja, estão dispersando entradas minimamente diferentes mais amplamente do que uma função de hash criptográfica ideal. (Observação: isso significa que a avaliação gráfica de Ian de que o FNV-1a e o MurmurHash2 "parecem aleatórios" para ele no conjunto de dados de números pode ser refutada de seus próprios dados. Zero colisão em um conjunto de dados desse tamanho, para ambas as funções de hash, é surpreendentemente não-aleatório!)

Isso não é uma surpresa, pois esse é um comportamento desejável para muitos usos de funções de hash. Por exemplo, chaves de tabela de hash geralmente são muito semelhantes; A resposta de Ian menciona um problema que o MSN já teve com tabelas de hash de código postal . Este é um uso em que a prevenção de colisões em entradas prováveis vence o comportamento aleatório.

Outra comparação instrutiva aqui é o contraste nos objetivos de design entre as funções de CRC e hash criptográfico:

• O CRC foi projetado para detectar erros resultantes de canais de comunicação ruidosos , que provavelmente são um pequeno número de inversões de bits;
• Os hashes criptográficos são projetados para capturar modificações feitas por invasores mal-intencionados , aos quais são atribuídos recursos computacionais limitados, mas arbitrariamente muita esperteza.

Portanto, para a CRC, é novamente bom ter menos colisões do que aleatórias em entradas minimamente diferentes. Com hashes criptográficos, isso é um não-não!

Use SipHash . Tem muitas propriedades desejáveis:

• Rápido. Uma implementação otimizada leva cerca de 1 ciclo por byte.

• Seguro. O SipHash é um forte PRF (função pseudo-aleatória). Isso significa que é indistinguível de uma função aleatória (a menos que você conheça a chave secreta de 128 bits). Conseqüentemente:

  • Não é necessário se preocupar com o fato de as sondas da tabela de hash se tornarem tempo linear devido a colisões. Com o SipHash, você sabe que, em média, obterá um desempenho médio de caso, independentemente das entradas.

  • Imunidade a ataques de negação de serviço baseados em hash.

  • Você pode usar o SipHash (especialmente a versão com uma saída de 128 bits) como um MAC (código de autenticação de mensagens). Se você receber uma mensagem e uma tag SipHash, e a tag for a mesma que a da execução do SipHash com sua chave secreta, você saberá que quem criou o hash também possui sua chave secreta e que nem a mensagem nem o hash foram alterados desde então.

Depende dos dados que você está fazendo o hash. Alguns hash funcionam melhor com dados específicos, como texto. Alguns algoritmos de hash foram projetados especificamente para serem bons para dados específicos.

Paul Hsieh fez uma vez hash rápido . Ele lista o código fonte e explicações. Mas já estava vencido. :)

Java usa este algoritmo simples de multiplicar e adicionar:

O código hash para um objeto String é calculado como

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int aritmetic, onde s[i]é o i- ésimo caractere da string, né o comprimento da string e ^indica exponenciação. (O valor do hash da cadeia vazia é zero.)

Provavelmente existem muito melhores por aí, mas isso é bastante difundido e parece ser uma boa troca entre velocidade e singularidade.

Primeiro de tudo, por que você precisa implementar seu próprio hash? Para a maioria das tarefas, você deve obter bons resultados com estruturas de dados de uma biblioteca padrão, supondo que exista uma implementação disponível (a menos que você esteja fazendo isso apenas para sua própria educação).

No que diz respeito aos algoritmos de hash reais, o meu favorito é o FNV. 1

Aqui está um exemplo de implementação da versão de 32 bits em C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
{
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

  for(i = 0; i < length; i++)
    h = (h * 16777619) ^ p[i] ;

  return h;
}