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

Usei três conjuntos de chaves diferentes:

• Uma lista de 216.553 palavras em inglês ^{🕗  arquivo} (em minúsculas)
• Os números "1" a "216553" (pense em códigos postais e como um hash ruim derrubou msn.com ^{🕗  arquivo} )
• 216.553 ” random “(ou seja, tipo 4 uuid ) GUIDs

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

Eu testei:

• DJB2
• DJB2a (variante usando xor em vez 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 

Observações :

• O O algoritmo LoseLose (onde hash = hash + character) é verdadeiramente terrível Tudo colide nos mesmos 1.375 baldes
• SuperFastHash é rápido, com as coisas parecendo bastante dispersas; pelo meu Deus o número de colisões. Espero que o cara que portou 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

FNV -1a colisões

• 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
• colide com vigils
• finks colide com vinic

Randomnessification

A outra medida subjetiva é o quão aleatoriamente os hashes são distribuídos. O mapeamento das HashTables resultantes mostra como os dados são distribuídos uniformemente. Todas as funções hash mostram boa distribuição ao mapear a tabela linearmente:

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

Exceto ao hash de strings de número ("1", "2", …, "216553") (por exemplo, códigos postais ), onde os padrões começam para emergir na maioria dos algoritmos de hash:

SDBM :

DJB2a :

FNV-1 :

Todos, exceto

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

Comentários

• Aqui ‘ s mais sobre Hashing perfeito (mínimo) burtleburtle.net/bob/hash/perfect.html incluindo dados de desempenho, embora não ‘ não use o processador mais atual, etc.
• É ‘ bastante óbvio, mas vale ressaltar que, para garantir que não haja colisões, as chaves teriam que ser do mesmo tamanho que os valores, a menos que th Existem restrições sobre os valores que o algoritmo pode capitalizar.
• @ devios1 Sua declaração não tem sentido. Primeiro, os valores em uma tabela hash, perfeitos ou não, são independentes das chaves. Em segundo lugar, uma tabela de hash perfeita é apenas uma matriz linear de valores, indexada pelo resultado da função que foi criada para que todos os índices sejam únicos.
• @MarcusJ Hashing perfeito é geralmente usado com menos de 100 mas dê uma olhada em cmph.sourceforge.net … ainda muito aquém do seu alcance.
• @DavidCary Nada em seu o link apóia sua reivindicação. Possivelmente você confundiu O (1) com ” sem colisões “, mas eles não estão ‘ t absolutamente a mesma coisa. Obviamente, o hashing perfeito não garante colisões, mas requer que todas as chaves sejam conhecidas com antecedência e que haja relativamente poucas delas. (Mas veja o link para cmph acima.)

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

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

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

Comentários

• Na verdade, djb2 é sensível a zero, como a maioria dessas funções de hash simples, então você pode facilmente quebrar esses hashes.Tem um viés ruim, muitas colisões e uma distribuição ruim, ele quebra na maioria dos testes de qualidade smhasher: Veja github.com/rurban/smhasher/blob/master/doc/bernstein Seu banco de dados cdb o usa, mas eu não ‘ não o usaria com acesso público.
• DJB é muito ruim do ponto de vista de desempenho e distribuição. Eu não ‘ não o usaria hoje.
• @ConradMeyer I ‘ d aposto que DJB pode ser acelerado por um fator de três, exatamente como esta minha pergunta e então ‘ d provavelmente superou a maioria dos algoritmos utilizáveis. Quanto à distribuição, eu concordo. Um hash que produz colisões, mesmo para strings de duas letras, pode ‘ não ser muito bom.
• Pessoal, tenho dúvidas. Você está dizendo que djb2 é ruim, mas os resultados do teste da resposta aceita mostram que é bom.
• Você pode pelo menos usar um primo sensível que produza menos colisões em vez de 33. stackoverflow.com/a/2816747/21499

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

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

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

Sobre o suporte de 32 bits:

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

Comentários

• CityHash é pronunciado de forma semelhante a ” City Sushi? ”
• veja SipHash também, ele deve substituir MurmurHash / CityHash / etc.: 131002.net/siphash
• Consulte também FarmHash, a sucessor do CitHash. code.google.com/p/farmhash
• xxHash afirma ser 5x mais rápido do que CityHash.
• plain C port link quebrado

Eu plotei uma pequena comparação de velocidade de diferentes algoritmos de hash ao fazer hash de arquivos.

Os gráficos individuais diferem apenas ligeiramente no método de leitura e podem ser ignorados aqui, uma vez que todos os arquivos foram armazenados em um tmpfs. Portanto, o benchmark não foi limitado por IO, se você estiver se perguntando.

• Escala linear
• Escala logarítmica

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 são muito próximas. Deve-se notar que Cityhash pode ser mais rápido em CPUs com instrução SSE 4.2s CRC, que minha CPU não possui. No meu caso, o SpookyHash sempre foi um pouco antes do CityHash.
• MD5 parece ser uma boa opção ao usar funções de hash criptográficas, embora SHA256 possa ser mais seguro para o vulnerabilidades de colisão de MD5 e SHA1.
• A complexidade de todos os algoritmos é linear – o que realmente não é surpreendente, já que funcionam em blocos. (Eu queria ver se o método de leitura faz alguma diferença, para que você possa comparar os valores mais à direita).
• SHA256 era mais lento que SHA512.
• Não investiguei a aleatoriedade de as funções hash. Mas aqui é uma boa comparação das funções hash que estão faltando na resposta de Ian Boyds . Isso indica que o CityHash tem alguns problemas em casos extremos.

A fonte usada para os gráficos:

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

Comentários

• O gráfico de escala linear corta o rótulo do eixo y que diz a quantidade que está traçando. Eu acho que provavelmente seria ” tempo em segundos “, o mesmo que a escala logarítmica. ‘ Vale a pena corrigir.

Eu sei que existem coisas como SHA-256 e tal, mas esses algoritmos são projetados para ser seguro , o que geralmente significa que eles são mais lentos do que algoritmos menos exclusivos .

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

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

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

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

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

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

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, eles estão se dispersando minimamente diferentes entradas mais amplamente do que uma função de hash criptográfica ideal faria. (Observação: isso significa que a avaliação gráfica de Ian de que FNV-1a e MurmurHash2 “parecem aleatórios” para ele no conjunto de dados de números pode ser refutada a partir de seus próprios dados. Zero colisões em um conjunto de dados desse tamanho, para ambas funções hash, é surpreendentemente não aleatório!)

Isso não é uma surpresa porque este é um comportamento desejável para muitos usos de funções hash. Por exemplo, as chaves da tabela hash são frequentemente 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ão em entradas prováveis vence o comportamento de tipo aleatório.

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

• CRC é projetado para capturar erros resultantes de canais de comunicação ruidosos , que provavelmente serão um pequeno número de mudanças de bits;
• Os hashes criptográficos são projetados para capturar modificações feitas por atacantes maliciosos , a quem são atribuídos recursos computacionais limitados, mas arbitrariamente muita inteligência.

Portanto, para o CRC, é novamente bom ter menos colisões do que aleatórias em entradas minimamente diferentes. Com criptografia hashes, isso é impossível!

Os algoritmos SHA (incluindo SHA-256) são projetado para ser rápido .

Na verdade, 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) 

Comentários

• É ‘ relativamente rápido, claro, para um algoritmo de hash criptográfico . Mas o OP deseja apenas armazenar valores em uma tabela de hash e eu não ‘ não acho que uma função de hash criptográfica seja realmente apropriada para isso.
• A questão levantada (tangencialmente, parece agora) o assunto das funções hash criptográficas. Esse ‘ é a parte a que estou respondendo.
• Apenas para afastar as pessoas da ideia de ” 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 ” – embora comum, que ‘ é simplesmente estúpido. Existem algoritmos projetados para esses cenários, por exemplo, bcrypt. Use as ferramentas certas.
• Hashes criptográficos são projetados para ter um alto rendimento, mas isso geralmente significa que eles têm alta configuração, desmontagem, .rodata e / ou custos de estado .Quando você quer um algoritmo para uma tabela de hash, normalmente você tem chaves muito curtas, e muitas delas, mas não precisa das garantias adicionais de uma criptografia. Eu mesmo uso um Jenkins de cada vez ajustado.
• @ChrisMorgan: em vez de usar um hash criptograficamente seguro, o HashTable DoS pode ser resolvido com muito mais eficiência usando a randomização de hash, para que cada execução de os programas ou até mesmo em cada hashtable, de modo que os dados não ‘ sejam agrupados no mesmo intervalo todas as vezes.

Use SipHash . Possui muitas propriedades desejáveis:

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

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

  • Não há necessidade de se preocupar com os testes da tabela hash se tornando lineares devido às colisões. Com o SipHash, você sabe que obterá desempenho médio, independentemente das entradas.

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

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

Comentários

• Isn ‘ t Exagero do SipHash, a menos que você precise de segurança? Requer uma chave de 128 bits que é apenas uma semente de hash glorificada. Sem mencionar que MurmurHash3 tem saída de 128 bits e SipHash só tem saída de 64 bits. Obviamente, o resumo maior tem uma chance de colisão menor.
• @bryc A diferença é que o SipHash continuará a se comportar bem, mesmo com entrada maliciosa. Uma tabela de hash baseada em SipHash pode ser usada para dados de fontes potencialmente hostis e pode usar um algoritmo como a análise linear que é muito sensível aos detalhes da função de hash.
• Siphash (e prng mais recente relacionado funções de estilo) é minha escolha padrão para segurança. Em termos de desempenho, xxhash é difícil de vencer. Há toneladas de conselhos ruins sobre hash na Internet, mesmo nas discussões aqui. O bom desempenho em entradas aleatórias ou semi-aleatórias não faz sentido. Qual é o pior caso de desempenho, com entradas do mundo real? Qual é o resultado com entradas maliciosas? Sua tabela de hash eventualmente se tornará um vetor de ataque.

Depende dos dados que você está fazendo 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 uma vez fez hash rápido . Ele lista o código-fonte e as explicações. Mas já foi derrotado. 🙂

Java usa esta multiplicação simples -e-adicionar algoritmo:

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 string, n é o comprimento da string e ^ indica exponenciação. (O valor hash da string vazia é zero.)

Provavelmente existem outros muito melhores por aí, mas isso é bastante difundido e parece ser um bom compensação entre velocidade e exclusividade.

Comentários

• Eu não ‘ não usaria exatamente o mesmo um usado aqui, pois ‘ ainda é relativamente fácil de produzir colisões com ele. Não ‘ é definitivamente terrível, mas existem muitos melhores por aí. E se não ‘ s nenhuma razão significativa para ser compatível com Java, ele não deve ser escolhido.
• Se você ainda escolher este forma de hash por algum motivo, você poderia pelo menos usar um número primo melhor, como 92821, como multiplicador. Isso reduz muito as colisões. stackoverflow.com/a/2816747/21499
• Você também pode usar FNV1a. Ele ‘ s também um hash simples baseado em multiplicação, mas usa um multiplicador maior, que dispersa melhor o hash.
• Você não ‘ t quero fazer s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Evite o operador de potência (^) e faça desta forma: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Sim, no código é (e deve ser) feito iterativamente, era apenas mais fácil de entender em uma fórmula fechada.

Em primeiro lugar, por que você precisa implementar seu próprio hashing? Para a maioria das tarefas, você deve obter bons resultados com estruturas de dados de uma biblioteca padrão, presumindo que haja 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, meu favorito pessoal é 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; } 

Comentários

• A variante FNV-1a é ligeiramente melhor com aleatoriedade. Troque a ordem de * e ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619