Qual algoritmo de hash é melhor para exclusividade e velocidade?

1388

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.

Earlz
fonte
9
Com que finalidade, segurança ou outra?
Orbling
19
@Orbling, para implementação de um dicionário de hash. Portanto, as colisões devem ser reduzidas ao mínimo, mas não têm nenhum objetivo de segurança.
19611 Earlz
4
Note que você terá que esperar pelo menos algumas colisões na sua tabela de hash, caso contrário, a tabela terá que ser enorme para ser capaz de manipular até mesmo um número relativamente pequeno de chaves ...
Dean Harding
19
Ótimo post! Você também pode conferir o xxHash de Yann Collet (criador ou LZ4), que é duas vezes mais rápido que Murmur? Página inicial: code.google.com/p/xxhash Mais informações: fastcompression.blogspot.fr/2012/04/…
24
@zvrba Depende do algoritmo. O bcrypt foi projetado para ser lento.
Izkata

Respostas:

2461

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

Digite a descrição da imagem aqui

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

Digite a descrição da imagem aqui

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 :

Digite a descrição da imagem aqui

DJB2a :

Digite a descrição da imagem aqui

FNV-1 :

Digite a descrição da imagem aqui

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

Digite a descrição da imagem aqui

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

Digite a descrição da imagem aqui

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

Ian Boyd
fonte
41
Seria realmente interessante ver como o SHA se compara, não porque é um bom candidato para um algoritmo de hash aqui, mas seria realmente interessante ver como qualquer hash criptográfico se compara com os algoritmos criados para os algoritmos de velocidade.
285 Michael
8
Um novo hash chamado 'xxHash', de Yann Collet, estava circulando recentemente. Sempre desconfio de um novo hash. Seria interessante vê-lo em sua comparação, (se você não está cansado de pessoas sugerindo hashes aleatórios que ouviu a ser adicionado ...)
th_in_gs
7
De fato. Os números de desempenho anunciados pela página do projeto xxHash parecem impressionantes, talvez demais para ser verdade. Bem, pelo menos, é um projeto open-source: code.google.com/p/xxhash
ATTracker
9
Oi Ian, minha implementação do SuperFastHash em Delphi está correta. Ao implementar, criei um conjunto de testes em C e Delphi para comparar os resultados da minha implementação e a implementação de referência. Não há diferenças. Então, o que você vê é a maldade real do hash ... (é por isso que também publicou uma implementação MurmurHash: landman-code.blogspot.nl/2009/02/... )
Davy Landman
19
O pôster sabe que essa não é apenas uma resposta impressionante - esse é o recurso de referência de fato do mundo sobre o assunto? Sempre que preciso lidar com hashes, isso resolve meu problema com tanta rapidez e autoridade que eu não preciso mais de nada.
MaiaVictor
59

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.

Damien
fonte
2
Aqui está mais sobre (mínimo) Perfeito Hashing burtleburtle.net/bob/hash/perfect.html incluindo dados de desempenho, apesar de não usar o mais atual processador etc.
Ellie Kesselman
4
É bastante óbvio, mas vale ressaltar que, para garantir nenhuma colisão, as chaves teriam que ter o mesmo tamanho dos valores, a menos que haja restrições nos valores que o algoritmo pode capitalizar.
precisa saber é o seguinte
1
@ devios1 Sua declaração não faz sentido. Primeiro, os valores em uma tabela de hash, perfeitos ou não, são independentes das chaves. Segundo, uma tabela de hash perfeita é apenas uma matriz linear de valores, indexada pelo resultado da função criada para que todos os índices sejam exclusivos.
Jim Balter
1
@MarcusJ O hash perfeito geralmente é usado com menos de 100 teclas, mas dê uma olhada no cmph.sourceforge.net ... ainda muito longe do seu alcance.
Jim Balter
1
@DavidCary Nada no seu link suporta sua reivindicação. Possivelmente você confundiu O (1) com "sem colisões", mas elas não são a mesma coisa. Obviamente, o hash perfeito não garante colisões, mas exige que todas as chaves sejam conhecidas antecipadamente e que existam relativamente poucas. (Mas veja o link para cmph acima.)
Jim Balter
34

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;
}
Dean Harding
fonte
6
Na verdade, o djb2 é sensível a zero, como a maioria das funções simples de hash, para que você possa quebrar facilmente esses hashes. Ele tem um viés ruim de muitas colisões e uma distribuição ruim, é interrompido na maioria dos testes de qualidade de smhasher: consulte github.com/rurban/smhasher/blob/master/doc/bernstein O banco de dados cdb dele o usa, mas eu não o usaria com acesso público.
rurbano
2
DJB é muito ruim do ponto de vista de desempenho e distribuição. Eu não usaria hoje.
Conrad Meyer
@ConradMeyer Eu aposto que o DJB pode ser acelerado por um fator de três, como nesta questão minha, e provavelmente venceria os algoritmos mais utilizáveis. Em relação à distribuição, eu concordo. Um hash produzindo colisões, mesmo para duas seqüências de letras, não pode ser realmente bom.
Maaartinus
28

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.

Vipin Parakkat
fonte
11
CityHash é pronunciado semelhante a "City Sushi?"
Eric
2
Dê uma olhada no SipHash também, ele pretende substituir o MurmurHash / CityHash / etc. : 131002.net/siphash
Török Edwin
3
Veja também FarmHash, um sucessor do CitHash. code.google.com/p/farmhash
stevendaniels
7
O xxHash afirma ser 5x mais rápido que o CityHash.
Clay Bridges
plain C portlink está quebrado
makerj
20

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.

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:

Sahib
fonte
1
O gráfico de escala linear corta o rótulo do eixo y, que diz qual quantidade está plotando. Eu acho que provavelmente seria "tempo em segundos", o mesmo que a escala logarítmica. Vale a pena consertar.
Craig McQueen
18

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)
yfeldblum
fonte
57
É relativamente rápido, com certeza, para um algoritmo de hash criptográfico . Mas o OP só deseja armazenar valores em uma hashtable, e não acho que uma função hash criptográfica seja realmente apropriada para isso.
22611 Dean Harding
6
A questão levantada (tangencialmente, agora parece) o assunto das funções hash criptográficas. É para isso que estou respondendo.
22611 yfeldblum
15
Apenas para afastar as pessoas da idéia 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, isso é estúpido. Existem algoritmos projetados para esses cenários, por exemplo bcrypt,. Use as ferramentas certas.
TC1 14/10
3
Os hashes criptográficos são projetados para ter uma alta taxa de transferência, mas isso geralmente significa que eles têm altos custos de configuração, desmontagem .rodatae / ou estado. Quando você deseja um algoritmo para uma hashtable, geralmente possui teclas muito curtas e muitas delas, mas não precisa das garantias adicionais de uma criptografia. Eu mesmo uso uma Jenkins ajustada de uma vez.
mirabilos
1
@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, de modo que cada execução dos programas ou mesmo em cada hashtable, para que os dados não sejam agrupados no mesmo intervalo de cada vez .
Lie Ryan
14

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!

sacundim
fonte
10

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.

Demi
fonte
1
O SipHash não é um exagero, a menos que você precise de segurança? Requer uma chave de 128 bits, que é apenas uma semente de hash glorificada. Sem mencionar que o MurmurHash3 possui uma saída de 128 bits e o SipHash apenas uma saída de 64 bits. Obviamente, o resumo maior tem uma chance menor de colisão.
Bryc #
@bryc A diferença é que o SipHash continuará sendo bem-comportado, mesmo com informações maliciosas. Uma tabela de hash baseada no SipHash pode ser usada para dados de fontes potencialmente hostis e pode usar um algoritmo como a sondagem linear que é muito sensível aos detalhes da função de hash.
Demi
9

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

user712092
fonte
6

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.

Biziclop
fonte
12
Eu não usaria exatamente o mesmo usado aqui, pois ainda é relativamente fácil produzir colisões com isso. É definitivamente não é terrível, mas há muito melhores lá fora. E se não houver motivo significativo para ser compatível com Java, ele não deve ser escolhido.
Joachim Sauer
4
Se você ainda escolher esse modo de hash por algum motivo, poderá usar pelo menos um primo melhor como 92821 como multiplicador. Isso reduz muito as colisões. stackoverflow.com/a/2816747/21499
Hans-Peter Störr
1
Você também pode usar o FNV1a. Também é um hash simples baseado em multiplicação, mas usa um multiplicador maior, que dispersa melhor o hash.
bryc 15/01
4

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

fonte
2
A variante FNV-1a é um pouco melhor com aleatoriedade. Troque a ordem do *e ^: h = (h * 16777619) ^ p[i]==>h = (h ^ p[i]) * 16777619
Ian Boyd