ti-enxame.com

Qual algoritmo de hash é melhor para exclusividade e velocidade?

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 tal, mas esses algoritmos são projetados para serem seguro , o que geralmente significa que eles são mais lentos que os algoritmos que são menos únicos. Quero um algoritmo de hash projetado para ser rápido, mas ainda assim ser único para evitar colisões.

1444
Earlz

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

Eu usei três conjuntos de chaves diferentes:

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

Eu testei:

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 :

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 a tabela linearmente:

Enter image description here

Ou como um Hilbert Map ( XKCD é sempre relevante ):

Enter image description here

Exceto ao fazer hash de sequências numéricas ("1", "2", ..., "216553") (por exemplo, CEP ), onde os padrões começam a surgir na maioria dos algoritmos de hash:

[~ # ~] sdbm [~ # ~] :

Enter image description here

DJB2a :

Enter image description here

FNV-1 :

Enter image description here

Todos, exceto FNV-1a , que ainda me parecem bastante aleatórios:

Enter image description here

De fato, Murmur2 parece ter uma aleatoriedade ainda melhor com Numbers do que FNV-1a:

Enter image description here

Quando olho para o FNV-1a "numere" o mapa, eu pense eu 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-1a sendo o melhor e DJB2x sendo o pior:

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

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

E então, 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_basis e FNV_prime depende do tamanho do hash de retorno que você deseja:

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 da 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 o corpus do Word em inglês:

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.

Acho 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:

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

Atualização

Murmúrio? Claro, por que não


Atualização

@whatshisname imaginou como seria um desempenho CRC32 adicionado números à tabela.

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

Recorte 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 randomnessification de todas as classes de entrada

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

Atualização: De a página inicial do 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 porque 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.


Atualização

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

Uma publicação oportuna de Raymond Chen reitera o fato de que "random" GUIDs 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 da versão 4 GUID não é garantido como imprevisível, porque o algoritmo não especifica a qualidade do gerador de números aleatórios. Artigo da Wikipedia para GUID contém pesquisa primária que sugere que GUIDs futuros e anteriores podem ser previstos com base no conhecimento do estado do gerador de números aleatórios, uma vez 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 : Novamente, eu coloquei "random GUID" entre aspas, porque é a variante "aleatória" dos 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

2530
Ian Boyd

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

61
Damien

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

Se você deseja 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;
}
34
Dean Harding

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 obter mais detalhes e o o código está disponível aqui .

CityHash é escrito em C++. Também existe um porta C simples .

Sobre o suporte de 32 bits:

Todas as funções do CityHash são ajustadas para processadores de 64 bits. Dito isto, 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.

29
Vipin Parakkat

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.

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

Conclusões:

  • Funções 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 instrução SSE 4.2s CRC, 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 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 é uma boa comparação das funções de hash que estão faltando em resposta de Ian Boyds . Isso indica que o CityHash tem alguns problemas nos casos de canto.

A fonte usada para as parcelas:

21
Sahib

Os algoritmos SHA (incluindo SHA-256) são 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)
18
yfeldblum

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 que são menos únicos.

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, isso é inverso. Em verdade:

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

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

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

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

Ao conectar n = 216.553 e d = 2 ^ 32, obtemos 5,5 colisões esperadas . Os testes de Ian mostram principalmente resultados nessa vizinhança, mas com uma exceção dramática: a maioria das funções obteve 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 testados por Ian estão interagindo favoravelmente com o conjunto de dados de números consecutivos - ou seja, eles estão dispersando entradas minimamente diferentes mais amplamente do que uma função hash criptográfica ideal. (Nota: 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 ambos funções 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 m problema que o MSN já teve com tabelas de código postal . Este é um uso em que a prevenção de colisão nas entradas provável 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 atacantes mal-intencionados , que recebem 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!

15
sacundim

Use SipHash . Possui 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 seus probes da tabela de hash se tornarem tempo linear devido a colisões. Com o SipHash, você sabe que obterá um desempenho médio de caso em média, 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.

10
Demi

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. :)

9
user712092

Java usa this 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]

usando int aritmética, onde s[i] é o i -ésimo caractere da sequência, n é o comprimento da sequência 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.

6
biziclop

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;
}
4
user17754