Ik heb verschillende algoritmen getest, waarbij ik de snelheid en het aantal botsingen heb gemeten .

Ik heb drie verschillende sleutelsets gebruikt:

• Een lijst van 216.553 Engelse woorden ^{🕗  archief} (in kleine letters)
• De cijfers "1" naar "216553" (denk aan postcodes en hoe een slechte hash msn.com heeft uitgeschakeld ^{🕗  archief} )
• 216,553 ” random “(ie type 4 uuid ) GUIDs

Voor elk corpus, het aantal botsingen en de gemiddelde tijd besteed aan hashing werd opgenomen.

Ik heb getest:

• DJB2
• DJB2a (variant met xor in plaats van +)
• FNV-1 (32-bits)
• FNV-1a (32-bits)
• SDBM
• CRC32
• Murmur2 (32-bits)
• SuperFastHash

Resultaten

Elk resultaat bevat de gemiddelde hash-tijd en het aantal botsingen

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 

Notities :

• De LoseLose-algoritme (waarbij hash = hash + teken) is echt verschrikkelijk . Alles komt in dezelfde 1.375 emmers terecht.
• SuperFastHash is snel, met dingen die er nogal versnipperd uitzien; bij mijn hemel het aantal botsingen. Ik hoop dat de man die het heeft geporteerd iets verkeerd heeft gedaan; het is behoorlijk slecht
• CRC32 is redelijk goed . Langzamer, en een 1k-opzoektabel

Gebeuren botsingen echt?

Ja. Ik ben begonnen met het schrijven van mijn testprogramma om te zien of hash-botsingen daadwerkelijk plaatsvinden – en niet alleen een theoretisch construct zijn.Ze gebeuren inderdaad:

FNV-1-botsingen

• creamwove botst met quists

FNV -1a botsingen

• costarring botst met liquid
• declinate botst met macallums
• altarage botst met zinke
• altarages botst met zinkes

Murmur2-botsingen

• cataract botst met periti
• roquette botst met skivie
• shawl botst met stormbound
• dowlases botst met tramontane
• cricketings botst met twanger
• longans botst met whigs

DJB2-botsingen

• hetairas botst met mentioner
• heliotropes botst met neurospora
• depravement botst met serafins
• stylist botst met subgenera
• joyful botst met synaphea
• redescribed botst met urites
• dram botst met vivency

DJB2a-botsingen

• haggadot botst met loathsomenesses
• adorablenesses botst met rentability
• playwright botst met snush
• playwrighting botst met snushing
• treponematoses botst met waterbeds

CRC32-botsingen

• codding botst met gnu
• exhibiters botst met schlager

SuperFastHash-botsingen

• dahabiah botst met drapability
• encharm botst met enclave
• grahams botst met gramary
• … knip 79 botsingen …
• night botst met vigil
• botst met vigils
• finks botst met vinic

Randomnessification

De andere subjectieve maatstaf is hoe willekeurig de hashes zijn verdeeld. Het in kaart brengen van de resulterende HashTables laat zien hoe gelijkmatig de gegevens zijn verdeeld. Alle hash-functies vertonen een goede verdeling bij het lineair toewijzen van de tabel:

Of als een Hilbert-kaart ( XKCD is altijd relevant ):

Behalve bij hash-nummerreeksen ("1", "2", …, "216553") (bijvoorbeeld postcodes ), waar patronen beginnen verschijnen in de meeste hash-algoritmen:

SDBM :

DJB2a :

FNV-1 :

Alles behalve

Als je een hash-map wilt maken van een onveranderlijk woordenboek, kun je perfecte hashing overwegen https://en.wikipedia.org/wiki/Perfect_hash_function – tijdens de constructie van de hash-functie en de hashtabel kunt u voor een gegeven dataset garanderen dat er geen botsingen zullen zijn.

Reacties

• Hier ‘ s meer over (minimale) Perfect Hashing burtleburtle.net/bob/hash/perfect.html inclusief prestatiegegevens, hoewel het ‘ niet de meest recente processor etc. gebruikt.
• Het ‘ is vrij voor de hand liggend, maar het is de moeite waard om erop te wijzen dat om botsingen te voorkomen, de sleutels dezelfde grootte moeten hebben als de waarden, tenzij de Er zijn beperkingen op de waarden waarop het algoritme kan inspelen.
• @ devios1 Uw bewering is zinloos. Ten eerste zijn de waarden in een hashtabel, perfect of niet, onafhankelijk van de sleutels. Ten tweede is een perfecte hashtabel slechts een lineaire reeks waarden, geïndexeerd door het resultaat van de functie die is ontworpen zodat alle indices uniek zijn.
• @MarcusJ Perfecte hashing wordt meestal gebruikt met minder dan 100 sleutels, maar kijk eens naar cmph.sourceforge.net … nog steeds ver van uw bereik.
• @DavidCary Niets bij uw link ondersteunt uw claim. Mogelijk heb je O (1) verward met ” geen botsingen “, maar ze zijn ‘ t helemaal hetzelfde. Natuurlijk garandeert perfecte hashing geen botsingen, maar het vereist dat alle sleutels van tevoren bekend zijn en dat er relatief weinig van zijn. (Maar zie de link naar cmph hierboven.)

Hier is een lijst met hash-functies, maar de korte versie is:

Als je gewoon een goede hash-functie wilt hebben , en kan niet wachten, djb2 is een van de beste string-hashfuncties die ik ken. Het heeft een uitstekende distributie en snelheid op veel verschillende sleutelsets en tafelgroottes

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

Opmerkingen

• Eigenlijk is djb2 nulgevoelig, zoals de meeste van dergelijke eenvoudige hashfuncties, dus je kunt dergelijke hashes gemakkelijk breken.Het heeft een slechte bias, te veel botsingen en een slechte distributie, het breekt bij de meeste geweldige kwaliteitstests: zie github.com/rurban/smhasher/blob/master/doc/bernstein Zijn cdb-database gebruikt het, maar ik zou het niet ‘ gebruiken voor openbare toegang.
• DJB is behoorlijk slecht vanuit het oogpunt van prestaties en distributie. Ik zou ‘ het vandaag niet gebruiken.
• @ConradMeyer Ik ‘ durfde wedden dat DJB kan worden versneld door een factor drie, net als in deze vraag van mij en daarna ‘ d waarschijnlijk de meest bruikbare algoritmen verslaan. Wat betreft de distributie ben ik het ermee eens. Een hash die botsingen produceert, zelfs voor strings van twee letters, kan ‘ niet echt goed zijn.
• Jongens, ik heb mijn twijfels. Je zegt dat djb2 slecht is, maar de testresultaten van het geaccepteerde antwoord laten zien dat het goed is.
• Je zou op zijn minst een verstandig priemgetal kunnen gebruiken dat minder botsingen veroorzaakt in plaats van 33. stackoverflow.com/a/2816747/21499

CityHash van Google is het algoritme dat u zoekt. Het is niet goed voor cryptografie, maar het is goed voor het genereren van unieke hashes.

Lees het blog voor meer details en het code is hier beschikbaar .

CityHash is geschreven in C ++. Er is ook een gewone C-poort .

Over 32-bits ondersteuning:

Alle CityHash-functies zijn afgestemd op 64-bit processors. Dat gezegd hebbende, zullen ze draaien (behalve de nieuwe die SSE4.2 gebruiken) in 32-bits code. Ze zullen echter niet erg snel zijn. Misschien wilt u Murmur of iets anders in 32-bits code gebruiken.

Reacties

• Wordt CityHash uitgesproken als ” City Sushi? ”
• Heb je een kijk ook naar SipHash, het is bedoeld om MurmurHash / CityHash / etc. te vervangen: 131002.net/siphash
• Zie ook FarmHash, een opvolger van CitHash. code.google.com/p/farmhash
• xxHash beweert 5x sneller te zijn dan CityHash.
• plain C port link is verbroken

Ik heb een korte snelheidsvergelijking uitgezet van verschillende hash-algoritmen bij het hashen van bestanden.

De individuele plots verschillen slechts in geringe mate in de leesmethode en kunnen hier worden genegeerd, aangezien alle bestanden in een tmpfs zijn opgeslagen. Daarom was de benchmark niet IO-gebonden als je je afvraagt.

• Lineaire schaal
• Logaritmische schaal

Algoritmen omvatten: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Conclusies:

• Niet-cryptografische hashfuncties zoals Murmur3, Cityhash en Spooky liggen redelijk dicht bij elkaar. Merk op dat Cityhash mogelijk sneller is op CPUs met SSE 4.2s CRC instructie, die mijn CPU niet heeft. SpookyHash was in mijn geval altijd een klein beetje vóór CityHash.
• MD5 lijkt een goede afweging te zijn bij het gebruik van cryptografische hashfuncties, hoewel SHA256 wellicht veiliger is voor de botsingskwetsbaarheden van MD5 en SHA1.
• De complexiteit van alle algoritmen is lineair – wat echt niet verrassend is aangezien ze bloksgewijs werken. (Ik wilde zien of de leesmethode een verschil maakt, zodat je gewoon de meest rechtse waarden kunt vergelijken).
• SHA256 was langzamer dan SHA512.
• Ik heb de willekeurigheid van de hash-functies. Maar hier is een goede vergelijking van de hash-functies die ontbreken in Ian Boyds antwoord . Dit wijst erop dat CityHash enkele problemen heeft in hoekgevallen.

De bron die voor de plots wordt gebruikt:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (sorry voor de lelijke code)

Reacties

• De lineaire schaalgrafiek snijdt het y-aslabel af dat aangeeft hoeveel het aan het plotten is. Ik denk dat het waarschijnlijk ” tijd in seconden ” zou zijn, hetzelfde als de logaritmische schaal. Het ‘ is de moeite waard om te corrigeren.

Ik weet dat er dingen zijn zoals SHA-256 en dergelijke, maar deze algoritmen zijn ontworpen veilig te zijn, wat gewoonlijk betekent dat ze langzamer zijn dan algoritmen die minder uniek zijn.

De aanname dat cryptografische hashfuncties unieker zijn, is onjuist, en in de praktijk kan in feite worden aangetoond dat het vaak achterstevoren is. In werkelijkheid:

1. Cryptografische hashfuncties zouden idealiter niet te onderscheiden zijn van willekeurig ;
2. Maar met niet-cryptografische hashfuncties, is het wenselijk dat ze gunstig reageren op waarschijnlijke invoer .

Wat betekent dat een niet-cryptografische hashfunctie minder botsingen kan hebben dan een cryptografische voor “goede” gegevensset – gegevenssets waarvoor deze is ontworpen.

We kunnen dit feitelijk aantonen met de gegevens in het antwoord van Ian Boyd en een beetje wiskunde: de Verjaardagsprobleem . De formule voor het verwachte aantal botsende paren als je n gehele getallen willekeurig kiest uit de set [1, d] is deze (overgenomen van Wikipedia):

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

Inpluggen n = 216,553 en d = 2 ^ 32 krijgen we ongeveer 5.5 verwachte botsingen . De tests van Ian tonen meestal resultaten rond die buurt, maar met één dramatische uitzondering: de meeste functies kregen nul botsingen in de opeenvolgende getallen testen. De kans om 216.553 32-bits getallen willekeurig te kiezen en nul botsingen te krijgen, is ongeveer 0,43%. En dat is slechts voor één functie: hier hebben we vijf verschillende hash-functiefamilies met nul botsingen!

Dus wat we hier zien, is dat de hashes die Ian heeft getest gunstig samenwerken met de gegevensset met opeenvolgende nummers, dwz ze verspreiden minimaal verschillende inputs breder invoeren dan een ideale cryptografische hashfunctie zou doen. (Kanttekening: dit betekent dat Ians grafische inschatting dat FNV-1a en MurmurHash2 er volgens hem willekeurig uitzien in de gegevensset met getallen, kan worden weerlegd op basis van zijn eigen gegevens. Geen botsingen op een gegevensset van die omvang, voor > beide hash-functies, is opvallend niet willekeurig!)

Dit is geen verrassing, want dit is een wenselijk gedrag voor veel gebruik van hash-functies. Hash-tabeltoetsen lijken bijvoorbeeld vaak erg op elkaar; Het antwoord van Ian vermeldt een probleem dat MSN ooit had met hashtabellen voor postcode . Dit is een gebruik waarbij het vermijden van botsingen op waarschijnlijke inputs wint van willekeurig gedrag.

Een andere leerzame vergelijking hier is het contrast in de ontwerpdoelen tussen CRC en cryptografische hashfuncties:

• CRC is ontworpen om fouten op te vangen die het gevolg zijn van luidruchtige communicatiekanalen , die waarschijnlijk een klein aantal bitflips;
• Crypto-hashes zijn ontworpen om wijzigingen op te vangen die zijn aangebracht door kwaadwillende aanvallers , die beperkte rekenkracht krijgen maar willekeurig veel slimheid.

Dus voor CRC is het weer goed om minder botsingen te hebben dan willekeurig in minimaal verschillende invoer. Met crypto-hashes is dit een nee-nee!

De SHA-algoritmen (inclusief SHA-256) zijn ontworpen om snel te zijn .

In feite kan hun snelheid soms een probleem zijn. In het bijzonder is een veelgebruikte techniek voor het opslaan van een van een wachtwoord afgeleid token het 10.000 keer uitvoeren van een standaard snel hash-algoritme (het opslaan van de hash van de hash van de hash van de hash van het … wachtwoord).

#!/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 

Uitvoer:

Rehearsal ------------------------------------ 1.480000 0.000000 1.480000 ( 1.391229) --------------------------- total: 1.480000sec user system total real 1.400000 0.000000 1.400000 ( 1.382016) 

Reacties

• Het ‘ is relatief snel, zeker voor een cryptografisch hash-algoritme . Maar het OP wil alleen waarden opslaan in een hashtabel, en ik denk niet ‘ niet dat een cryptografische hashfunctie daar echt geschikt voor is.
• De vraag die werd gesteld (tangentieel, het lijkt nu) het onderwerp van de cryptografische hash-functies. Dat ‘ is het stukje waarop ik reageer.
• Gewoon om mensen van het idee van ” is een veelgebruikte techniek voor het opslaan van een van een wachtwoord afgeleid token het 10.000 keer uitvoeren van een standaard snel hash-algoritme ” – hoewel gebruikelijk, dat ‘ is gewoon stom. Er zijn algoritmen ontworpen voor deze scenarios, bijvoorbeeld bcrypt. Gebruik de juiste tools.
• Cryptografische hashes zijn ontworpen voor een hoge doorvoer, maar dat betekent vaak dat ze hoge installatie-, demontage-, .rodata en / of staatskosten hebben .Als je een algoritme voor een hashtabel wilt, heb je meestal zeer korte sleutels, en veel daarvan, maar heb je niet de aanvullende garanties nodig die een cryptografie heeft. Ik gebruik zelf een getweakte Jenkins een-voor-een.
• @ChrisMorgan: in plaats van een cryptografisch veilige hash te gebruiken, kan HashTable DoS veel efficiënter worden opgelost met hash-randomisatie, zodat elke run van de programmas of zelfs op elke hashtabel, zodat de gegevens niet ‘ niet elke keer in dezelfde bucket worden gegroepeerd.

Gebruik SipHash . Het heeft veel gewenste eigenschappen:

• Snel. Een geoptimaliseerde implementatie duurt ongeveer 1 cyclus per byte.

• Veilig. SipHash is een sterke PRF (pseudowillekeurige functie). Dit betekent dat het niet te onderscheiden is van een willekeurige functie (tenzij u de 128-bits geheime sleutel kent). Vandaar:

  • U hoeft zich geen zorgen te maken dat uw hashtabel-probes lineaire tijd worden als gevolg van botsingen. Met SipHash weet u dat u gemiddeld gemiddelde prestaties krijgt, ongeacht de invoer.

  • Immuniteit voor op hash gebaseerde denial of service-aanvallen.

  • Je kunt SipHash (vooral de versie met een 128-bit output) gebruiken als een MAC (Message Authentication Code). Als u een bericht en een SipHash-tag ontvangt, en de tag is dezelfde als die van het uitvoeren van SipHash met uw geheime sleutel, dan weet u dat degene die de hash heeft gemaakt ook in het bezit was van uw geheime sleutel en dat noch het bericht noch de hash is sindsdien gewijzigd.

Reacties

• Isn ‘ t SipHash overdreven tenzij je beveiliging nodig hebt? Vereist een 128-bits sleutel die slechts een veredelde hashzaad is. Om nog maar te zwijgen van MurmurHash3 heeft 128-bits uitvoer en SipHash heeft alleen een 64-bits uitvoer. Het is duidelijk dat de grotere samenvatting een lagere kans op botsingen heeft.
• @bryc Het verschil is dat SipHash zich goed zal blijven gedragen, zelfs bij kwaadwillende invoer. Een hashtabel op basis van SipHash kan worden gebruikt voor gegevens uit potentieel vijandige bronnen, en kan een algoritme gebruiken zoals lineaire sondering dat erg gevoelig is voor de details van de hashfunctie.
• Siphash (en gerelateerde nieuwere prng stijlfuncties) is mijn standaardkeuze voor beveiliging. Voor prestaties is xxhash moeilijk te verslaan. Er is heel veel slecht hashing-advies op internet, zelfs in de discussies hier. Goede prestaties op willekeurige of semi-willekeurige invoer zijn zinloos. Wat is de slechtste prestatie met input uit de echte wereld? Wat is het resultaat met kwaadaardige inputs? Uw hashtabel zal uiteindelijk een aanvalsvector worden.

Het hangt af van de gegevens die u hashing. Sommige hashing werkt beter met specifieke gegevens zoals tekst. Sommige hash-algoritmen zijn specifiek ontworpen om goed te zijn voor specifieke gegevens.

Paul Hsieh heeft ooit snelle hash gemaakt. Hij somt de broncode en uitleg op. Maar het was al verslagen. 🙂

Java gebruikt deze eenvoudige vermenigvuldiging -and-add-algoritme:

De hash-code voor een String-object wordt berekend als

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

met int arithmetic, waarbij s[i] het i ​ -de teken van de string is, n is de lengte van de string, en ^ geeft machtsverheffen aan. (De hash-waarde van de lege string is nul.)

Er zijn waarschijnlijk veel betere die er zijn, maar dit is vrij algemeen en lijkt een goede afweging tussen snelheid en uniekheid.

Reacties

• Ik zou ‘ niet exact hetzelfde gebruiken een die hier wordt gebruikt, omdat het ‘ nog steeds relatief eenvoudig is om hiermee botsingen te produceren. Het ‘ is absoluut niet verschrikkelijk, maar er zijn veel betere die er zijn. En als er ‘ s geen significante reden is om compatibel te zijn met Java, zou het niet moeten worden gekozen.
• Als je dit toch kiest Om de een of andere reden te hashen, zou je op zijn minst een betere priemgetal zoals 92821 als een multiplicator kunnen gebruiken. Dat vermindert veel botsingen. stackoverflow.com/a/2816747/21499
• Je zou net zo goed FNV1a kunnen gebruiken. Het ‘ is ook een eenvoudige hash op basis van vermenigvuldiging, maar gebruikt een grotere vermenigvuldiger, die de hash beter verspreidt.
• Je hoeft wil s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3] doen. Vermijd de power operator (^) en doe het op deze manier: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Ja, in de code is het iteratief gedaan (en zou het moeten), het was gewoon gemakkelijker te begrijpen in een gesloten formule.

Allereerst, waarom moet u uw eigen hashing implementeren? Voor de meeste taken zou je goede resultaten moeten behalen met datastructuren uit een standaardbibliotheek, ervan uitgaande dat er een implementatie beschikbaar is (tenzij je dit alleen voor je eigen opleiding doet).

Wat de werkelijke hash-algoritmen betreft, is mijn persoonlijke favoriet FNV. 1

Hier is een voorbeeldimplementatie van de 32-bits versie in 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; } 

Reacties

• De FNV-1a-variant is iets beter met willekeur. Verwissel de volgorde van de * en ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619