Teszteltem néhány különböző algoritmust, mértem az ütközések sebességét és számát .

Három különböző kulcskészletet használtam:

• A 216 553 angol szó felsorolása ^{🕗  archívum} (kisbetűvel)
• A számok "1" – "216553" (gondolja meg az irányítószámokat, és hogyan szedte le egy szegény hash az msn.com ^{🕗  archívum} )
• 216 553 ” véletlenszerű “(azaz 4-es típusú uuid ) GUID-ek

Minden korpusz esetében az ütközések száma és az átlagos hasholással töltött idő felvételre került.

Teszteltem:

• DJB2
• DJB2a (a xor helyett +)
• FNV-1 (32 bites)
• FNV-1a (32 bites)
• SDBM
• CRC32
• Zúgás2 (32 bites)
• SuperFastHash

Eredmények

Minden eredmény tartalmazza az átlagos kivonatolási időt és az ütközések számát

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 

Megjegyzések :

• A A LoseLose algoritmus (ahol a hash = hash + karakter) valóban borzasztó . Minden ugyanazon 1375 vödörbe ütközik
• A SuperFastHash gyors, a dolgok elég szétszórtnak tűnnek; jóságomból a szám ütközések. Remélem, hogy az a srác, aki portált, valami hibát okozott; nagyon rosszul van
• A CRC32 nagyon jó . Lassabb, és 1 ezer keresési táblázat

Valójában ütközések történnek?

Igen. Elkezdtem írni a tesztprogramomat, hogy lássam, történnek-e hash ütközések valójában – és nem csak elméleti konstrukciónak számítanak-e.Valóban előfordulnak:

FNV-1 ütközések

• creamwove ütközik a quists

FNV-vel -1a ütközés

• costarring ütközik a liquid
• declinate ütközik a macallums
• altarage ütközik a következővel: zinke
• altarages ütközik a zinkes

Murm2 ütközés

• cataract ütközik a periti
• roquette ütközik a skivie
• shawl ütközik a stormbound
• dowlases ütközik a következővel: tramontane
• cricketings ütközik twanger
• longans ütközik whigs

DJB2 ütközésekkel

• hetairas ütközik a mentioner
• heliotropes ütközik a következővel: neurospora
• depravement ütközik a serafins
• stylist ütközik a subgenera
• joyful ütközik a következővel: synaphea
• redescribed ütközik a urites
• dram ütközik a vivency

DJB2a ütközések

• haggadot ütközik a loathsomenesses
• adorablenesses ütközik a következővel: rentability
• playwright ütközik a snush
• playwrighting ütközik a snushing
• treponematoses ütközésekkel waterbeds

CRC32 ütközésekkel

• codding ütközik a gnu
• exhibiters ütközik a schlager

SuperFastHash ütközésekkel

• dahabiah ütközik a drapability
• encharm ütközik a enclave
• grahams ütközik a gramary
• … 79 ütközést vág le …
• night ütközik a vigil
• ütközik a következővel: vigils
• finks ütközik a vinic

Véletlenszerűsítés

A másik szubjektív mérték az, hogy a hashek milyen véletlenszerűen oszlanak el. A kapott HashTables feltérképezése megmutatja, hogy az adatok hogyan oszlanak el egyenletesen. Az összes hash függvény jó eloszlást mutat a táblázat lineáris leképezésénél:

Vagy Hilbert Map ( Az XKCD mindig releváns ):

Kivéve a számláncok hasításakor ("1", "2", …, "216553") (például irányítószámok ), ahol a minták kezdődnek hogy megjelenjenek a legtöbb hash algoritmusban:

SDBM :

DJB2a :

FNV-1 :

Minden, kivéve

Ha változatlan szótárból szeretne kivonatkártyát létrehozni, érdemes megfontolni a tökéletes kivonatolást https://en.wikipedia.org/wiki/Perfect_hash_function – a hash függvény és a hash tábla összeállítása során garantálhatja, hogy egy adott adatkészletnél ne történjenek ütközések.

Megjegyzések

• Itt ‘ további információ a (minimális) Tökéletes hasításról burtleburtle.net/bob/hash/perfect.html , beleértve a teljesítményadatokat is, bár nem ‘ nem használja a legfrissebb processzort stb.
• ‘ meglehetősen kézenfekvő, de érdemes kiemelni, hogy az ütközések elkerülése érdekében a kulcsoknak azonos méretűeknek kell lenniük, mint az értékek, hacsak nincsenek korlátozások az algoritmus által kamatoztatható értékekre vonatkozóan.
• @ devios1 Az állításod értelmetlen. Először is, a hash tábla értékei, tökéletesek vagy sem, függetlenek a kulcsoktól. Másodszor, a tökéletes hash-tábla csak egy lineáris értéktömb, amelyet a függvény eredménye alapján indexelünk, úgy, hogy az összes index egyedi legyen.
• @MarcusJ A tökéletes hash-ot általában 100-nál kevesebbel használják. gombokat, de nézze meg a cmph.sourceforge.net oldalt … még mindig messze elmarad a hatótávolságától.
• @DavidCary link támogatja az Ön igényét. Esetleg összekeverte O (1) -et ” nincs ütközés “, de ezek nem ‘ t egyáltalán. Természetesen a tökéletes hash nem garantálja az ütközéseket, de megköveteli, hogy az összes kulcsot előre ismerjék, és hogy viszonylag kevés legyen belőlük. (De lásd a fenti cmph hivatkozást.)

Itt a hash függvények listája, de a rövid verzió:

Ha csak egy jó hash függvényt szeretne , és alig várom, a djb2 az egyik legjobb string hash függvény, amelyet ismerek. Kiváló eloszlású és sebességű a kulcsok és a táblaméretek sok különböző készleténél.

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

Megjegyzések

• Valójában a djb2 nulla érzékeny, mivel a legtöbb ilyen egyszerű hash függvény, így az ilyen hasheket könnyedén fel tudja bontani.Rossz elfogultsága, túl sok ütközése és rossz elosztása van, a legtöbb smhasher minőségi teszten megszakad: Lásd: github.com/rurban/smhasher/blob/master/doc/bernstein A cdb adatbázisa használja, de én nem használnám ‘ nyilvános hozzáféréssel.
• A DJB teljesítmény és terjesztés szempontjából elég rossz. Nem szeretném ‘ ma használni.
• @ConradMeyer I ‘ d fogadok, a DJB felpörgethető háromszoros tényező, akárcsak ebben a kérdésemben , majd ‘ d valószínűleg legyőzte a legtöbb használható algoritmust. A terjesztést illetően egyetértek. A két betűs karakterláncot is ütközést okozó hash ‘ nem lehet igazán jó.
• Srácok, kétségeim vannak. Azt mondod, hogy a djb2 rossz, de az elfogadott válasz teszt eredményei azt mutatják, hogy ez jó.
• Legalább használhatsz ésszerű prímet, amely kevesebb ütközést eredményez 33 helyett. stackoverflow.com/a/2816747/21499

A CityHash by Google a keresett algoritmus. Nem jó a rejtjelezéshez, de egyedi hashek előállításához.

További részletekért olvassa el a blogot és a kód itt érhető el .

A CityHash C ++ nyelven íródott. Van még egy sima C port .

A 32 bites támogatásról:

Az összes CityHash funkció 64 bites processzorokra van hangolva. Ennek ellenére 32 bites kódban fognak futtatni (kivéve az újakat, amelyek SSE4.2-et használnak). Bár nem lesznek nagyon gyorsak. Érdemes használni a Murmur vagy valami mást a 32 bites kódban.

Megjegyzések

• A CityHash kiejtése hasonló a ” City Sushihoz? ”
• Van egy nézd meg a SipHash-t is, ez a MurmurHash / CityHash / stb helyettesítésére szolgál: 131002.net/siphash
• Lásd még a FarmHash, egy a CitHash utódja. code.google.com/p/farmhash
• xxHash azt állítja, hogy ötször gyorsabb, mint a CityHash.
• plain C port link megszakadt

Fájlok kivonásakor rövid sebesség-összehasonlítást terveztem a különböző kivonatoló algoritmusokról.

Az egyes ábrák csak kissé különböznek az olvasási módtól, és itt figyelmen kívül hagyhatók, mivel az összes fájlt egy tmpfs-ben tárolták. Ezért, ha kíváncsi, a referenciaérték nem volt IO-kötve.

• Lineáris skála
• Logaritmikus skála

Az algoritmusok a következőket tartalmazzák: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Következtetések:

• A nem kriptográfiai kivonatoló funkciók, mint például a Murmur3, a Cityhash és a Spooky, elég közel vannak egymáshoz. Meg kell jegyeznünk, hogy a Cityhash gyorsabb lehet az SSE 4.2s CRC utasítással rendelkező CPU-knál, amivel a CPU-m nincs. A SpookyHash az én esetemben mindig volt egy aprócska a CityHash előtt.
• Úgy tűnik, hogy az MD5 jó kompromisszumot jelent a kriptográfiai hash függvények használatakor, bár az SHA256 biztonságosabb lehet a ütközési sebezhetőségei .
• Az összes algoritmus összetettsége lineáris – ami valójában nem meglepő, mivel blokkosan működnek. (Azt akartam látni, hogy az olvasási módszer jelent-e különbséget, így csak a jobb szélső értékeket hasonlíthatja össze.)
• Az SHA256 lassabb volt, mint az SHA512.
• Nem vizsgáltam a a hash funkciók. De az itt jó összehasonlítás az Ian Boyds válaszban hiányzó hash függvényekkel. Ez rámutat arra, hogy a CityHash-nak vannak problémái sarok esetekben.

A cselekményekhez használt forrás:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (elnézést a csúnya kódért)

Megjegyzések

• A lineáris skála grafikon levágja az y tengely címkét, amely megmondja, hogy milyen mennyiséget ábrázol. Gondolom, valószínűleg ” lesz az idő másodpercekben “, mint a logaritmikus skála. ‘ érdemes javítani.

Tudom, hogy vannak olyan dolgok, mint az SHA-256 és ilyenek, de ezek az algoritmusok biztonságos , ami általában azt jelenti, hogy lassabbak, mint a kevésbé egyedi algoritmusok.

Az a feltételezés, miszerint a kriptográfiai hash függvények egyedibbek, téves, sőt, a gyakorlatban gyakran visszafelé mutatható ki. Valójában:

1. A kriptográfiai kivonatoknak ideális esetben legyenek megkülönböztethetetlenek a véletlenszerű ;
2. De nem kriptográfiai kivonatolási funkciókkal kívánatos, hogy kedvezően lépjenek kapcsolatba a valószínű bemenetekkel . / li>

Ami azt jelenti, hogy egy nem kriptográfiai hash függvény kevesebb ütközést okozhat, mint egy kriptográfiai a “jó” adathalmazhoz – olyan adathalmazok, amelyekhez tervezték.

Ezt igazából Ian Boyd válaszában szereplő adatokkal és egy kis matematikával is bemutathatjuk: a Születésnapi probléma . Az ütköző párok várható számának képlete, ha n egész számokat véletlenszerűen választasz ki a [1, d] halmazból, ez a következő (átvett a Wikipédiából):

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

n = 216 553 és d = 2 ^ 32 körülbelül 5,5 várható ütközést kapunk . Ian tesztjei többnyire a környék környékén mutatnak eredményeket, de egy drámai kivétellel: a legtöbb funkció nulla ütközést kapott a egymást követő számtesztek. A valószínűsége, hogy véletlenszerűen 216 553 32 bites számot választunk és nulla ütközést kapunk, körülbelül 0,43%. És ez csak egy funkcióra vonatkozik – itt van öt különálló hash függvénycsalád nulla ütközések!

Tehát azt látjuk itt, hogy az Ian által tesztelt hashek kedvezően kölcsönhatásba lépnek az egymást követő számadatkészlettel – azaz minimálisan eltérnek inputok t szélesebb körben, mint egy ideális kriptográfiai hash függvény. (Mellékjegyzet: ez azt jelenti, hogy Ian grafikus értékelése, miszerint az FNV-1a és MurmurHash2 véletlenszerűen néz ki számára a számadatkészletben, saját adataiból cáfolható. Nulla ütközés egy ekkora adathalmazon, mindkét hash függvény feltűnően nem véletlenszerű!)

Ez nem meglepő, mert a kivonatolási funkciók sokféle használata esetén ez kívánatos viselkedés. Például a hash tábla kulcsai gyakran nagyon hasonlóak; Ian válasza megemlít egy problémát, amelyet az MSN hajdanában irányítószám-kivonat táblákkal látott el . Ez egy olyan alkalmazás, ahol a valószínű bemenetek ütközésének elkerülése nyer a véletlenszerű viselkedéshez képest.

Egy másik tanulságos összehasonlítás itt a CRC és a kriptográfiai hash függvények közötti kontraszt a tervezési célokban:

• A CRC a zajos kommunikációs csatornákból eredő hibák fogadására szolgál, amelyek valószínűleg kis számú bit átfordítás;
• A kriptográfiai hasítékokat a rosszindulatú támadók módosításainak elkapására tervezték , akiknek korlátozott számítási erőforrások vannak elosztva, de önkényesen sok okosság van.

Tehát a CRC számára ismét jó , ha kevesebb ütközés van, mint véletlenszerű, minimálisan eltérő bemenetben. A kriptográfiai kivonatokkal ez nem-nem!

Az SHA algoritmusok (beleértve az SHA-256-ot is) gyors .

Valójában a sebességük néha problémát okozhat. Különösen a jelszóból származó tokenek tárolásának általános technikája, hogy egy szabványos gyors hash algoritmust 10 000-szer futtatnak (a … jelszó hash hashjának hashját tárolják).

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

Kimenet:

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

Megjegyzések

• ‘ viszonylag gyorsan, biztosan egy kriptográfiai hash algoritmus hoz. De az OP csak egy hashtable-ben akarja tárolni az értékeket, és nem gondolom, hogy a kriptográfiai hash függvény valóban megfelel erre.
• A felvetett kérdés (érintőlegesen most jelenik meg) a kriptográfiai hash függvények tárgya. Ez ‘ az a kicsit, amire reagálok.
• Csak azért, hogy elrugaszkodjam az embereket a ” gondolattól , a jelszóból származó tokenek tárolásának elterjedt technikája, hogy egy szabványos gyors hash algoritmust 10 000-szer futtatnak ” – míg gyakori, hogy ‘ s egyszerűen hülye. Vannak algoritmusok, amelyeket ezekre a forgatókönyvekre terveztek, például bcrypt. Használja a megfelelő eszközöket.
• A kriptográfiai kivonatokat nagy áteresztőképességgel tervezték, de ez gyakran azt jelenti, hogy magas a beállításuk, a lebontásuk, .rodata és / vagy az állami költségek. .Ha egy hashtable-hez szeretne algoritmust, akkor általában nagyon rövid kulcsai vannak, és sok is van belőlük, de nincs szükségük a kriptográfiai kiegészítő garanciákra. Jómagam egyszerre módosított Jenkins-t használok.
• @ChrisMorgan: ahelyett, hogy kriptográfiailag biztonságos hash-t használnék, a HashTable DoS sokkal hatékonyabban megoldható hash véletlenszerűsítéssel, így a a programokat vagy akár minden hashtable-t, így az adatok nem ‘ nem csoportosulnak mindig ugyanabba a csoportba.

A SipHash használatával. sok kívánatos tulajdonsággal rendelkezik:

• Gyors. Az optimalizált megvalósítás byte-onként kb. 1 ciklust vesz igénybe.

• Biztonságos. A SipHash erős PRF (pszeudorandom függvény). Ez azt jelenti, hogy nem különböztethető meg egy véletlenszerű függvénytől (hacsak nem ismeri a 128 bites titkos kulcsot). Ezért:

  • Nem kell attól tartania, hogy a hash-tábla szondái lineáris idővé válnak az ütközések miatt. A SipHash használatával tudja , hogy a bemenetektől függetlenül átlagosan átlagos teljesítményt fog elérni.

  • Hash-alapú szolgáltatásmegtagadási támadásokkal szembeni immunitás.

  • A SipHash-ot (különösen a 128 bites kimenettel rendelkező verziót) használhatja MAC-ként (Üzenet-hitelesítési kód). Ha üzenetet és SipHash-címkét kap, és a címke megegyezik azzal, amelyet a titkos kulcsával futtatott SipHash, akkor tudja, hogy aki létrehozta a hash-t, annak is volt titkos kulcsa, és hogy sem az üzenet, sem a a hash azóta megváltozott.

Megjegyzések

• Isn ‘ t a SipHash túlteljesít, hacsak nincs szüksége biztonságra? 128 bites kulcsra van szükség, amely csak dicsőített hash mag. A MurmurHash3 128 bites kimenettel, a SipHash pedig csak 64 bites kimenettel rendelkezik. Nyilvánvaló, hogy a nagyobb kivonatnak kisebb az ütközési esélye.
• @bryc A különbség az, hogy a SipHash továbbra is jól viselkedik, még rosszindulatú bevitel esetén is. A SipHash-alapú hash-tábla felhasználható a potenciálisan ellenséges forrásokból származó adatokhoz, és használhat olyan algoritmust, mint a lineáris szondázás, amely nagyon érzékeny a hash-funkció részleteire.
• Siphash (és a kapcsolódó újabb prng) stílusfunkciók) az alapértelmezett választásom a biztonság érdekében. A teljesítmény szempontjából az xxhash-t nehéz legyőzni. Rengeteg rossz hash tanács van az interneten, még az itt folyó beszélgetések során is. A véletlenszerű vagy félig véletlenszerű bemenetek jó teljesítménye értelmetlen. Mi a legrosszabb esetben a teljesítmény a valós világban? Mi az eredmény rosszindulatú inputokkal? A hash-táblája végül támadási vektor lesz.

Ez a tárolt adatoktól függ. Egyes kivonatok jobban működnek specifikus adatokkal, például szöveggel. Néhány kivonatoló algoritmust speciálisan úgy terveztek, hogy megfelelő legyen bizonyos adatokhoz.

Paul Hsieh egyszer gyors hash-t készített . Felsorolja a forráskódot és a magyarázatokat. De már megverték. 🙂

A Java ezt a egyszerű szorzót használja -and-add algoritmus:

A String objektum kivonatkódja a következő:

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

int számtan segítségével, ahol s[i] a karakterlánc i ​ -es karaktere, A n a karakterlánc hossza, a ^ pedig a hatványozást jelzi. (Az üres karakterlánc hash értéke nulla.)

Valószínűleg vannak sokkal jobbak is, de ez meglehetősen elterjedt és jónak tűnik. kompromisszum a sebesség és az egyediség között.

Megjegyzések

• Nem használnám ‘ pontosan ugyanazt. az egyik itt használt, mivel ‘ még mindig viszonylag könnyű ezzel ütközéseket produkálni. ‘ s határozottan nem szörnyű, de vannak ennél sokkal jobbak is. És ha ‘ nincs jelentős oka annak, hogy kompatibilis legyen a Java-val, akkor azt nem kell választani.
• Ha mégis ezt választja valamilyen okból kifolyólag a kivonatolás módja, akkor legalább egy jobb prime-ot használhat, mint például a 92821, mint szorzó. Ez jelentősen csökkenti az ütközéseket. stackoverflow.com/a/2816747/21499
• Használhatja helyette az FNV1a-t is. ‘ egy egyszerű szorzás alapú hash-t is tartalmaz, de nagyobb szorzót használ, amely jobban szétszórja a hash-t.
• Ön nem ‘ nem akarja csinálni s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Kerülje az áramszolgáltatót (^), és tegye így: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Igen, a kódban iteratív módon történik (és kell is), egyszerűen könnyebb volt megérteni zárt képletben.

Először is, miért kell megvalósítania saját hash-ját? A legtöbb feladathoz jó eredményeket kell elérnie egy szabványos könyvtár adatstruktúráival, feltételezve, hogy rendelkezésre áll egy megvalósítás (hacsak nem csak a saját oktatása érdekében teszi ezt).

Ami a tényleges hash algoritmusokat illeti, személyes kedvencem az FNV. 1

Itt van egy példa a 32 bites verzió C implementációjára:

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

Megjegyzések

• Az FNV-1a variáns véletlenszerűséggel valamivel jobb. Cserélje fel a * és ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619