Testasin joitain erilaisia algoritmeja, mittaamalla nopeuden ja törmäysten määrän .

Käytin kolmea erilaista avainsarjaa:

• 216 553 englanninkielisen sanan luettelo ^{🕗  arkisto} (pienillä kirjaimilla)
• Numerot "1" "216553" (ajattele postinumeroita ja kuinka huono hash otti alas msn.com ^{🕗  arkisto} )
• 216553 ” satunnainen ”(ts. tyyppi 4 uuid ) GUID: t

Jokaisen korpusen kohdalla törmäysten määrä ja keskimääräinen hajautukseen käytetty aika äänitettiin.

Testasin:

• DJB2
• DJB2a (muunnos, joka käyttää xor -tunnusta eikä +)
• FNV-1 (32-bittinen)
• FNV-1a (32-bittinen)
• SDBM
• CRC32
• Murmeli2 (32-bittinen)
• SuperFastHash

Tulokset

Jokainen tulos sisältää keskimääräisen hajautusajan ja törmäysten määrän

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 

Huomautuksia :

• LoseLose-algoritmi (jossa hash = hash + merkki) on todella kauhea . Kaikki törmää samoihin 1375 ämpäriin
• SuperFastHash on nopea, ja asiat näyttävät melko hajallaan; hyvyydestäni numero törmäykset. Toivon sen siirtäneelle kaverille jotain vikaa; se on melko huono
• CRC32 on melko hyvä . Hitaampi ja 1 000 hakutaulukko

Tapahtuuko törmäyksiä todella?

Kyllä. Aloin kirjoittaa testiohjelmaani nähdäksesi, tapahtuvatko hash-törmäykset todella – eivätkä ne ole vain teoreettisia rakenteita.Ne todellakin tapahtuvat:

FNV-1-törmäykset

• creamwove törmää quists

FNV -1a törmäykset

• costarring törmäävät liquid
• declinate törmää macallums
• altarage törmää zinke
• altarages törmää zinkes

Murm2-törmäykset

• cataract törmää periti
• roquette törmää skivie
• shawl törmää stormbound
• dowlases törmää tramontane
• cricketings törmää twanger
• longans törmää whigs

DJB2-törmäysten kanssa

• hetairas törmää mentioner
• heliotropes törmää neurospora
• depravement törmää serafins
• stylist törmää subgenera
• joyful törmää synaphea
• redescribed törmää urites
• dram törmää vivency

DJB2a-törmäykset

• haggadot törmää kohtaan loathsomenesses
• adorablenesses törmää rentability
• playwright törmää snush
• playwrighting törmää snushing
• treponematoses törmää waterbeds

CRC32-törmäysten kanssa

• codding törmää gnu
• exhibiters törmää schlager

SuperFastHash-törmäyksiin

• dahabiah törmää drapability
• encharm törmää enclave
• grahams törmää gramary
• … katkaise 79 törmäystä …
• night törmää vigil
• törmää vigils
• finks törmää vinic

Satunnaistaminen

Toinen subjektiivinen mitta on se, kuinka hajautukset ovat jakautuneet satunnaisesti. Tuloksena olevien HashTable-taulukoiden kartoitus osoittaa, kuinka tasaisesti tiedot jaetaan. Kaikilla hash-funktioilla on hyvä jakauma taulukon kartoituksessa lineaarisesti:

Tai Hilbert-kartta ( XKCD on aina relevantti ):

Paitsi kun numerosarjaa hajautetaan ("1", "2", …, "216553") (esimerkiksi postinumero) , josta kuviot alkavat esiintyä useimmissa hajautusalgoritmeissa:

SDBM :

DJB2a :

FNV-1 :

Kaikki paitsi

Jos haluat luoda hash-kartan muuttumattomasta sanakirjasta, sinun kannattaa harkita täydellistä hajautusta https://en.wikipedia.org/wiki/Perfect_hash_function – hash-funktion ja hash-taulukon rakentamisen aikana voit taata tietylle tietojoukolle, ettei törmäyksiä tapahdu.

Kommentit

• Tässä ’ lisää (täydellisestä) täydellisestä hajautuksesta burtleburtle.net/bob/hash/perfect.html mukaan lukien suorituskykytiedot, vaikka se ’ ei käytä uusinta prosessoria jne.
• ’ on melko ilmeinen, mutta on syytä huomauttaa, että törmäysten välttämiseksi avainten on oltava samankokoisia kuin arvot, ellei Ei ole rajoituksia arvoille, joihin algoritmi voi hyödyntää.
• @ devios1 Lauselmasi on merkityksetön. Ensinnäkin hash-taulukon arvot, täydelliset tai ei, ovat riippumattomia avaimista. Toiseksi täydellinen hash-taulukko on vain lineaarinen arvoryhmä, joka indeksoidaan funktion tuloksen avulla, joka on muotoiltu siten, että kaikki indeksit ovat yksilöllisiä.
• @MarcusJ Perfect-hajautusta käytetään yleensä alle 100: lla. avaimet, mutta katso cmph.sourceforge.net … edelleen kaukana alueestasi.
• @DavidCary Ei mitään linkki tukee vaatimustasi. Olet ehkä sekoittanut O (1): n ja ” ei törmäyksiä ”, mutta ne eivät ole ’ t lainkaan sama asia. Täydellinen hajautus ei tietenkään takaa törmäyksiä, mutta se vaatii, että kaikki avaimet tunnetaan etukäteen ja että niitä on suhteellisen vähän. (Mutta katso yllä oleva linkki cmph: ään.)

Tässä on luettelo hajautusfunktioista, mutta lyhyt versio on:

Jos haluat vain hyvän hash-toiminnon , ja en voi odottaa, djb2 on yksi parhaimmista merkkijonon tiivistefunktioista, jotka tiedän. Sillä on erinomainen jakelu ja nopeus monille erilaisille avain- ja taulukkokokoille.

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

Kommentit

• Itse asiassa djb2 on nollaherkkä, koska useimmat tällaiset yksinkertaiset hash-toiminnot, joten voit helposti rikkoa tällaiset hashit.Sillä on huono puolueellisuus, liian monta törmäystä ja huono jakauma, se hajoaa useimmissa smhasher-laatutesteissä: Katso github.com/rurban/smhasher/blob/master/doc/bernstein Hänen cdb-tietokantansa käyttää sitä, mutta en halua käyttää sitä ’ julkisen pääsyn kanssa.
• DJB on melko huono suorituskyvyn ja jakelun kannalta. En halua ’ käyttää sitä tänään.
• @ConradMeyer I ’ d vedon, DJB: tä voidaan nopeuttaa kerroin kolme aivan kuten tässä kysymyksessäni ja sitten ’ d voitti todennäköisesti kaikkein käyttökelpoisimmat algoritmit. Jakelun osalta olen samaa mieltä. Hajautus, joka tuottaa törmäyksiä jopa kahdelle kirjainmerkille, ’ ei voi olla todella hyvää.
• Kaverit, minulla on epäilyksiä. Sanot, että djb2 on huono, mutta hyväksytyn vastauksen testitulokset osoittavat sen olevan hyvä.
• Voit ainakin käyttää järkevää alkua, joka tuottaa vähemmän törmäyksiä 33: n sijasta. stackoverflow.com/a/2816747/21499

Googlen CityHash on etsimäsi algoritmi. Se ei ole hyvä salaukselle, mutta on hyvä luomaan ainutlaatuisia hajautuksia.

Lue lisätietoja -blogista ja -koodi on saatavilla täältä .

CityHash on kirjoitettu C ++: lla. Siellä on myös tavallinen C-portti .

Tietoja 32-bittisestä tuesta:

Kaikki CityHash-toiminnot on viritetty 64-bittisille prosessoreille. Se sanoi, että ne suoritetaan (lukuun ottamatta uusia, jotka käyttävät SSE4.2: ta) 32-bittisessä koodissa. He eivät kuitenkaan ole kovin nopeita. Haluat ehkä käyttää Murmuria tai jotain muuta 32-bittisessä koodissa.

Kommentit

• Onko CityHash lausuttu samanlainen kuin ” City Sushi? ”
• Onko sinulla katso myös SipHashia, se on tarkoitettu korvaamaan MurmurHash / CityHash / jne.: 131002.net/siphash
• Katso myös FarmHash, a CitHashin seuraaja. code.google.com/p/farmhash
• xxHash väittää olevansa viisi kertaa nopeampi kuin CityHash.
• plain C port linkki on rikki

Olen piirtänyt lyhyen nopeusvertailun eri hajautusalgoritmeista hajauttaessasi tiedostoja.

Yksittäiset juovat eroavat vain hieman lukutavasta ja voidaan jättää tässä huomioimatta, koska kaikki tiedostot on tallennettu tmpfs-tiedostoon. Siksi vertailuarvo ei ollut IO-sidottu, jos mietit.

• Lineaarinen asteikko
• Logaritminen asteikko

Algoritmeja ovat: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Johtopäätökset:

• Muut kuin kryptografiset hash-toiminnot, kuten Murmur3, Cityhash ja Spooky, ovat melko lähellä toisiaan. On huomattava, että Cityhash voi olla nopeampi suorittimissa, joissa on SSE 4.2s CRC -käsky, jota prosessorissani ei ole. SpookyHash oli minun tapauksessani aina vähän ennen CityHashia.
• MD5 näyttää olevan hyvä kompromissi käytettäessä salauksen hash-toimintoja, vaikka SHA256 saattaa olla turvallisempi törmäyshaavoittuvuudet .
• Kaikkien algoritmien monimutkaisuus on lineaarista – mikä ei todellakaan ole yllättävää, koska ne toimivat lohkona. (Halusin nähdä, onko lukumenetelmällä merkitystä, joten voit verrata oikeanpuoleisia arvoja.)
• SHA256 oli hitaampaa kuin SHA512.
• En tutkinut hash-toiminnot. Mutta tässä on hyvä vertailu hash-funktioista, jotka puuttuvat Ian Boydsin vastauksesta . Tämä osoittaa, että CityHashilla on joitain ongelmia kulmatapauksissa.

Tontteihin käytetty lähde:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (anteeksi rumasta koodista)

kommentit

• Lineaarinen asteikkokaavio katkaisee y-akselin etiketin, joka kertoo minkä määrän se piirtää. Luultavasti se olisi ” aika sekunteina ”, sama kuin logaritminen asteikko. ’ kannattaa korjata.

Tiedän, että on olemassa asioita, kuten SHA-256 ja vastaavia, mutta nämä algoritmit on suunniteltu olla turvallinen , mikä tarkoittaa yleensä, että ne ovat hitaampia kuin vähemmän ainutlaatuiset algoritmit.

Oletus, että salauksen hash-toiminnot ovat ainutlaatuisempia, on väärä, ja itse asiassa sen voidaan osoittaa olevan käytännössä usein taaksepäin. Todellisuudessa:

1. salauksen hajautusfunktioiden tulisi ihanteellisesti olla erotettavissa satunnaisista ;
2. Mutta ei-salauksellisilla hajautusfunktioilla niiden on toivottavaa olla suotuisassa vuorovaikutuksessa todennäköisten syötteiden kanssa .

Tämä tarkoittaa, että ei-salauksellisella hajautusfunktiolla voi hyvinkin olla vähemmän törmäyksiä kuin salausteksti ”hyvää” tietojoukkoa varten – tietojoukot, joille se on suunniteltu.

Voimme todellakin osoittaa tämän Ian Boydin vastauksessa olevilla tiedoilla ja vähän matematiikalla: syntymäpäiväongelma . Kaava odotetulle törmäysparien lukumäärälle, jos valitset n kokonaislukuja satunnaisesti joukosta [1, d] on tämä (otettu Wikipediasta):

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

n = 216 553 ja d = 2 ^ 32 saamme noin 5.5 odotettavissa olevat törmäykset . Ianin testit osoittavat enimmäkseen tuloksia kyseisen naapuruston ympärillä, mutta yhtä dramaattista poikkeusta lukuun ottamatta: Suurin osa toiminnoista sai nollatörmäykset peräkkäiset numerotestit. Todennäköisyys valita 216 553 32-bittistä numeroa satunnaisesti ja saada nollatörmäykset on noin 0,43%. Ja se on vain yhtä toimintoa varten – tässä meillä on viisi erillistä hash-toimintoperhettä nolla törmäykset!

Joten mitä me täällä näemme, on se, että Ianin testaamat hashit ovat vuorovaikutuksessa suotuisasti peräkkäisten numeroiden kanssa – ts. ne hajaantuvat uudelleen minimaalisesti erilaisiksi panokset laajemmin kuin ihanteellinen kryptografinen hajautusfunktio. (Sivuhuomautus: tämä tarkoittaa, että Ianin graafinen arvio siitä, että FNV-1a ja MurmurHash2 ”näyttävät hänelle satunnaisilta” numerotietojoukossa, voidaan kumota hänen omasta datastaan. Nollatörmäykset tämän kokoisessa tietojoukossa, kun molemmat hash-toiminnot ovat silmiinpistävän satunnaisia!)

Tämä ei ole yllätys, koska tämä on toivottavaa käyttäytymistä monille hash-toimintojen käytöille. Esimerkiksi hash-taulukon avaimet ovat usein hyvin samanlaisia; Ianin vastauksessa mainitaan ongelma, joka MSN: llä oli kerran postinumeron hash-taulukoiden kanssa. Tämä on käyttö, jossa törmäyksen välttäminen todennäköisillä syötteillä voittaa satunnaiskäyttäytymisen.

Toinen opettava vertailu on CRC: n ja kryptografisten hajautusfunktioiden välinen kontrasti suunnittelutavoitteissa:

• CRC on suunniteltu tarttumaan virheisiin, jotka johtuvat meluisista viestintäkanavista , jotka todennäköisesti pieni määrä bittikäännöksiä;
• salaushajautukset on suunniteltu tarttumaan haitallisten hyökkääjien tekemiin muokkauksiin , joille on varattu rajalliset laskennalliset resurssit, mutta mielivaltaisesti paljon älykkyyttä.

Joten CRC: lle on jälleen hyvä , että törmäyksiä on vähemmän kuin satunnaisia minimaalisesti erilaisissa syötteissä. Salaushajautuksissa tämä on ei-ei!

SHA-algoritmit (mukaan lukien SHA-256) ovat suunniteltu nopeasti .

Itse asiassa niiden nopeus voi joskus olla ongelma. Erityisesti yleinen tekniikka salasanasta johdetun tunnuksen tallentamiseksi on tavallisen nopean hash-algoritmin suorittaminen 10000 kertaa (… salasanan hash-tiivisteen hash-muistin tallentaminen).

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

Tulos:

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

Kommentit

• ’ on suhteellisen nopea, varma, salauksen hajautusalgoritmille . Mutta OP haluaa vain tallentaa arvot hashtableen, enkä ’ usko, että salauksen hash-toiminto on todella sopiva siihen.
• Esitetty kysymys (tangentiaalisesti se näyttää nyt) salauksen hajautusfunktioiden kohde. Se ’ on se bitti, johon vastaan.
• Pelkästään ihmisten syrjäyttämiseksi ajatuksesta ” , yleinen tekniikka salasanasta johdetun tunnuksen tallentamiseksi on suorittaa vakioinen nopea hajautusalgoritmi 10000 kertaa ” – vaikka se on yleistä, ’ S vain tyhmä. Näitä tilanteita varten on suunniteltu algoritmeja, esim. bcrypt. Käytä oikeita työkaluja.
• Salaushajautukset on suunniteltu siten, että niiden suorituskyky on suuri, mutta se tarkoittaa usein, että niillä on korkeat määritykset, repeytymiset, .rodata ja / tai valtion kustannukset .Kun haluat algoritmin hashtabelle, sinulla on yleensä hyvin lyhyet avaimet, ja paljon niitä, mutta et tarvitse salaustodistuksen lisävakuuksia. Käytän itse muokattua Jenkinsin yksi kerrallaan.
• @ChrisMorgan: Sen sijaan, että käyttäisin kryptografisesti suojattua hashia, HashTable DoS voidaan ratkaista paljon tehokkaammin käyttämällä hash-satunnaistamista, jotta jokainen ohjelmissa tai edes jokaisella hashtabella, joten tietoja ei ’ ei ryhmitellä samaan ryhmään joka kerta.

Käytä SipHashia . Sillä on monia toivottavia ominaisuuksia:

• Nopea. Optimoitu toteutus vie noin yhden jakson tavua kohti.

• Suojattu. SipHash on vahva PRF (näennäissatunnaisfunktio). Tämä tarkoittaa, että sitä ei voida erottaa satunnaisfunktiosta (ellet tiedä 128-bittistä salaista avainta). Siksi:

  • Ei tarvitse huolehtia siitä, että hash-taulukon anturit muuttuvat lineaarisiksi törmäysten vuoksi. SipHashin avulla tiedät , että saat keskimääräisen suorituskyvyn keskimäärin syötteistä riippumatta.

  • Immuniteetti hash-pohjaisiin palvelunestohyökkäyksiin.

  • Voit käyttää SipHashia (etenkin versiota, jossa on 128-bittinen lähtö) MAC-tiedostona (Viestien todennuskoodi). Jos saat viestin ja SipHash-tunnisteen, ja tunniste on sama kuin SipHashin suorittamisessa salaisella avaimellasi, tiedät, että kuka tahansa hajautusasiakirjan luoja oli myös salaisen avaimesi hallussa ja ettei viesti eikä hashia on muutettu siitä lähtien.

Kommentit

• Ei ’ t SipHash ylittää, ellet tarvitse suojausta? Vaatii 128-bittisen avaimen, joka on vain ylistetty hash-siemen. MurmurHash3: lla on 128-bittinen lähtö ja SipHashilla vain 64-bittinen lähtö. Suuremmalla katteella on tietysti pienempi törmäysmahdollisuus.
• @bryc Ero on siinä, että SipHash käyttäytyy edelleen hyvin myös haitallisilla syötteillä. SipHashiin perustuvaa hajautustaulukkoa voidaan käyttää potentiaalisesti vihamielisistä lähteistä saatavaan dataan, ja siinä voidaan käyttää algoritmia, kuten lineaarista koetusta, joka on erittäin herkkä hajautusfunktion yksityiskohdille.
• Siphash (ja siihen liittyvät uudemmat prng: t) tyylitoiminnot) on oletusvalintani turvallisuudelle. Suorituskyvyn kannalta xxhashia on vaikea voittaa. Internetissä on paljon pahoja hajautusneuvoja, jopa täällä käytävissä keskusteluissa. Hyvä suorituskyky satunnaisilla tai puoli satunnaisilla syötteillä on merkityksetöntä. Mikä on pahimmassa tapauksessa suorituskyky reaalimaailman panoksilla? Mikä on tulos haitallisilla syötteillä? Hajautustaulukostasi tulee lopulta hyökkäysvektori.

Se riippuu hajauttamistasi tiedoista. Jotkut hajautus toimii paremmin tiettyjen tietojen, kuten tekstin, kanssa. Jotkut hajautusalgoritmit on suunniteltu siten, että ne sopivat hyvin tiettyihin tietoihin.

Paul Hsieh teki kerran nopean hajautusmerkin . Hän listaa lähdekoodin ja selitykset. Mutta se oli jo lyöty. 🙂

Java käyttää tätä yksinkertaista kertoa -ja-lisää algoritmi:

String-objektin hajautuskoodi lasketaan nimellä

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

int-aritmeettinen, jossa s[i] on merkkijonon i ​ -merkki, n on merkkijonon pituus ja ^ osoittaa eksponentin. (Tyhjän merkkijonon hash-arvo on nolla.)

Siellä on todennäköisesti paljon parempia, mutta tämä on melko yleistä ja näyttää olevan hyvä kompromissi nopeuden ja ainutlaatuisuuden välillä.

Kommentit

• En käytä ’ en käytä täsmälleen samaa yhtä käytettiin täällä, koska ’ on edelleen suhteellisen helppo tuottaa törmäyksiä tämän kanssa. ’ s ehdottomasti ole kauhea, mutta siellä on paljon parempia. Ja jos ’ ei ole merkittävää syytä olla yhteensopiva Javan kanssa, sitä ei pitäisi ei valita.
• Jos valitset edelleen tämän jostain syystä voit käyttää ainakin parempaa alkua, kuten 92821, kertojana. Se vähentää törmäyksiä paljon. stackoverflow.com/a/2816747/21499
• Voit myös käyttää FNV1a: ta. Se ’ on myös yksinkertainen kertointipohjainen hajautus, mutta käyttää suurempaa kerrointa, joka hajauttaa hajautuksen paremmin.
• Et ’ ei halua tehdä s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Vältä verkko-operaattoria (^) ja tee se näin: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Kyllä, koodissa se tehdään (ja pitäisi tehdä) iteratiivisesti, se oli vain helpompi ymmärtää suljetussa kaavassa.

Ensinnäkin, miksi sinun on ensin toteutettava oma hajautus? Useimmissa tehtävissä sinun pitäisi saada hyviä tuloksia tietorakenteilla tavallisesta kirjastosta olettaen, että toteutus on käytettävissä (ellet tee sitä vain oman koulusi vuoksi).

Mitä tulee todellisiin hajautusalgoritmeihin, oma suosikkini on FNV. 1

Tässä on esimerkki 32-bittisen version toteutuksesta C: ssä:

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

Kommentit

• FNV-1a-muunnos on hieman parempi satunnaisuudella. Vaihda * ja ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619