Testoval jsem několik různých algoritmů, měření rychlosti a počtu kolizí .

Použil jsem tři různé sady klíčů:

• Seznam 216 553 anglických slov ^{🕗  archiv} (malými písmeny)
• Čísla "1" to "216553" (přemýšlejte o PSČ a jak špatný hash srazil msn.com ^{🕗  archiv} )
• 216 553 “ random „(tj. typ 4 uuid ) GUID

U každého korpusu počet kolizí a průměrný čas strávený hašováním byl zaznamenán.

Testoval jsem:

• DJB2
• DJB2a (varianta používající xor spíše než +)
• FNV-1 (32bitový)
• FNV-1a (32bitová)
• SDBM
• CRC32
• Murmur2 (32bitový)
• SuperFastHash

Výsledky

Každý výsledek obsahuje průměrnou dobu hash a počet kolizí

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 

Poznámky :

• Algoritmus LoseLose (kde hash = hash + znak) je skutečně strašný . Všechno se srazí do stejných 1 375 segmentů
• SuperFastHash je rychlý a věci vypadají docela rozptýleny; podle mého boha počet srážek. Doufám, že ten, kdo to přenesl, něco pokazil; je to docela špatné
• CRC32 je docela dobrý . Pomalejší a 1k vyhledávací tabulka

Dochází ke kolizím?

Ano. Začal jsem psát svůj testovací program, abych zjistil, zda ke srážkám hash skutečně nedochází – a nejsou jen teoretickým konstruktem.Skutečně k nim dochází:

kolize FNV-1

• creamwove koliduje s quists

FNV Kolize -1a

• costarring se srazí s liquid
• declinate koliduje s macallums
• altarage koliduje s zinke
• altarages koliduje s zinkes

Kolize Murmur2

• cataract koliduje s periti
• roquette koliduje s skivie
• shawl koliduje s stormbound
• dowlases se srazí s tramontane
• cricketings koliduje s twanger
• longans koliduje s whigs

kolizemi DJB2

• hetairas koliduje s mentioner
• heliotropes koliduje s neurospora
• depravement koliduje s serafins
• stylist koliduje s subgenera
• joyful koliduje s synaphea
• redescribed koliduje s urites
• dram koliduje s vivency

kolize DJB2a

• haggadot kolize s loathsomenesses
• adorablenesses koliduje s rentability
• playwright koliduje s snush
• playwrighting koliduje s snushing
• treponematoses koliduje s waterbeds

srážkami CRC32

• codding srazí se s gnu
• exhibiters koliduje s schlager

srážkami SuperFastHash

• dahabiah koliduje s drapability
• encharm se srazí s enclave
• grahams se srazí s gramary
• … srážky snipu 79 …
• night koliduje s vigil
• koliduje s vigils
• finks koliduje s vinic

Náhodnost

Další subjektivní míra spočívá v tom, jak jsou hashe náhodně rozloženy. Mapování výsledných tabulek HashTables ukazuje, jak rovnoměrně jsou data distribuována. Všechny funkce hash vykazují dobrou distribuci při lineárním mapování tabulky:

Nebo jako Hilbertova mapa ( XKCD je vždy relevantní ):

S výjimkou hašování číselných řetězců ("1", "2", …, "216553") (například PSČ ), kde vzory začínají se objeví ve většině hashovacích algoritmů:

SDBM :

DJB2a :

FNV-1 :

Vše kromě

Pokud chcete vytvořit hashovací mapu z neměnného slovníku, možná budete chtít zvážit dokonalé hašování https://en.wikipedia.org/wiki/Perfect_hash_function – během vytváření funkce hash a tabulky hash můžete pro danou datovou sadu zaručit, že nedojde ke kolizím.

Komentáře

• Zde ‚ s více o (minimálním) Perfect Hashing burtleburtle.net/bob/hash/perfect.html včetně údajů o výkonu, přestože ‚ nepoužívá nejaktuálnější procesor atd.
• Je to ‚ docela zřejmé, ale stojí za zmínku, že aby byly zaručeny žádné kolize, klíče by musely mít stejnou velikost jako hodnoty, pokud Existují omezení týkající se hodnot, ze kterých může algoritmus vydělávat.
• @ devios1 Vaše prohlášení nemá smysl. Za prvé, hodnoty v hash tabulce, dokonalé nebo ne, jsou nezávislé na klíčích. Zadruhé, dokonalá hash tabulka je pouze lineární pole hodnot indexovaných podle výsledku funkce, která byla vytvořena tak, aby všechny indexy byly jedinečné.
• @MarcusJ Perfect hash se obvykle používá s méně než 100 klíče, ale podívejte se na cmph.sourceforge.net … stále ještě daleko od vašeho dosahu.
• @DavidCary Nic na dosah odkaz podporuje váš nárok. Možná jste zaměnili O (1) s “ žádnými kolizemi „, ale nejsou ‚ t totéž. Dokonalé hašování samozřejmě nezaručuje žádné kolize, ale vyžaduje to, aby byly všechny klíče známy předem a aby jich bylo relativně málo. (Ale viz výše uvedený odkaz na cmph.)

Zde je seznam hashových funkcí, ale krátká verze je:

Pokud chcete mít pouze dobrou hashovací funkci , a nemůžu se dočkat, djb2 je jedna z nejlepších hašovacích funkcí řetězce, jaké znám. Má vynikající distribuci a rychlost na mnoha různých sadách klíčů a velikostí tabulek.

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

Komentáře

• Ve skutečnosti je djb2 nulový, jako většina takových jednoduchých hash funkcí, takže je můžete snadno rozbít.Má špatné zkreslení, příliš mnoho kolizí a špatnou distribuci, rozbíjí se u většiny kvalitních testů kvality: Viz github.com/rurban/smhasher/blob/master/doc/bernstein Jeho cdb databáze to používá, ale já bych ho ‚ nepoužíval s veřejným přístupem.
• DJB je z hlediska výkonu a distribuce docela špatný. Dnes bych jej ‚ nepoužíval.
• @ConradMeyer I ‚ vsadím se, že DJB může být urychlen faktor tři stejně jako v této mé otázce a poté ‚ d pravděpodobně porazil většinu použitelných algoritmů. Pokud jde o distribuci, souhlasím. Hash vytvářející kolize i pro řetězce se dvěma písmeny nemůže být ‚ opravdu dobrý.
• Chlapi, mám pochybnosti. Říkáte, že djb2 je špatný, ale výsledky testů přijaté odpovědi ukazují, že je dobrý.
• Můžete použít alespoň rozumný prime, který produkuje méně kolizí místo 33. stackoverflow.com/a/2816747/21499

CityHash by Google je algoritmus, který hledáte. To není dobré pro kryptografii, ale je to dobré pro generování jedinečných hodnot hash.

Další podrobnosti najdete v blogu a kód je k dispozici zde .

CityHash je napsán v C ++. K dispozici je také prostý port C .

O 32bitové podpoře:

Všechny funkce CityHash jsou vyladěny pro 64bitové procesory. To znamená, že poběží (s výjimkou nových, které používají SSE4.2) ve 32bitovém kódu. Nebudou však velmi rychlí. Možná budete chtít použít Murmur nebo něco jiného v 32bitovém kódu.

Komentáře

• Je CityHash vyslovován podobně jako “ City Sushi? “
• podívejte se také na SipHash, má nahradit MurmurHash / CityHash / atd.: 131002.net/siphash
• Viz také FarmHash, a nástupce CitHash. code.google.com/p/farmhash
• xxHash tvrdí, že je 5krát rychlejší než CityHash.
• plain C port odkaz je nefunkční

Při hašování souborů jsem vynese srovnání krátké rychlosti různých hashovacích algoritmů.

Jednotlivé grafy se liší jen mírně metodou čtení a lze je zde ignorovat, protože všechny soubory byly uloženy v tmpfs. Pokud tedy přemýšlíte, měřítko nebylo vázáno na IO.

• Lineární měřítko
• Logaritmické měřítko

Algoritmy zahrnují: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Závěry:

• Nekryptografické hashovací funkce jako Murmur3, Cityhash a Spooky jsou docela blízko u sebe. Je třeba si uvědomit, že Cityhash může být rychlejší na procesorech s instrukcí SSE 4.2s CRC, kterou můj procesor nemá. SpookyHash byl v mém případě vždy malý kousek před CityHash.
• MD5 se zdá být dobrým kompromisem při používání kryptografických hash funkcí, i když SHA256 může být bezpečnější pro kolizní chyby MD5 a SHA1.
• Složitost všech algoritmů je lineární – což není překvapující, protože fungují blokově. (Chtěl jsem zjistit, zda metoda čtení dělá rozdíl, takže můžete jen porovnat hodnoty zcela vpravo).
• SHA256 byl pomalejší než SHA512.
• Nezkoumal jsem náhodnost hashovací funkce. Ale zde je dobré srovnání hashových funkcí, které chybí v odpovědi Iana Boydse . To poukazuje na to, že CityHash má v rohových případech určité problémy.

Zdroj použitý pro grafy:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (omlouvám se za ošklivý kód)

Komentáře

• Lineární graf zmenší štítek osy y, který říká, jaké množství vykresluje. Myslím, že by to pravděpodobně byl “ čas v sekundách „, stejný jako logaritmická stupnice. To ‚ stojí za to opravit.

Vím, že existují věci jako SHA-256 a podobné, ale tyto algoritmy jsou navrženy být zabezpečený , což obvykle znamená, že jsou pomalejší než méně jedinečné algoritmy.

Předpoklad, že kryptografické hashovací funkce jsou jedinečnější, je mylný a ve skutečnosti se dá v praxi ukázat, že je často zpětný. Ve skutečnosti:

1. Kryptografické hashovací funkce by v ideálním případě měly být nerozeznatelné od náhodných ;
2. Ale s ne kryptografickými hashovacími funkcemi je žádoucí, aby příznivě interagovali s pravděpodobnými vstupy .

Což znamená, že ne-kryptografická hashovací funkce může mít méně kolizí než kryptografický pro „dobrý“ datový soubor – datové soubory, pro které byl navržen.

Můžeme to ve skutečnosti demonstrovat pomocí dat v odpovědi Iana Boyda a trochu matematiky: Problém s narozeninami . Vzorec pro očekávaný počet kolidujících párů, pokud náhodně vyberete n celá čísla ze sady [1, d], je tento (převzato z Wikipedie):

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

Připojování n = 216 553 a d = 2 ^ 32 dostaneme asi 5,5 očekávaných kolizí . Ianovy testy většinou ukazují výsledky v tomto okolí, ale s jednou dramatickou výjimkou: většina funkcí dostala nulové kolize v testy po sobě jdoucích čísel. Pravděpodobnost náhodného výběru 216 553 32bitových čísel a nulových kolizí je asi 0,43%. A to je jen pro jednu funkci – zde máme pět různých rodin hash funkcí s nulou kolize!

Takže to, co zde vidíme, je to, že hashe, které Ian testoval, interagují příznivě s datovou sadou po sobě jdoucích čísel – tj. dispergují minimálně odlišné vstupy ve větší míře, než by to činila ideální kryptografická hashovací funkce. (Boční poznámka: to znamená, že Ianovo grafické posouzení, že FNV-1a a MurmurHash2 na něj v množině datových souborů „vypadají náhodně“, lze vyvrátit z jeho vlastních dat. Nulové kolize na datové sadě této velikosti, pro obě hash funkce, je nápadně nenáhodné!)

To není překvapení, protože je to žádoucí chování pro mnoho použití hash funkcí. Například klíče hash tabulky jsou často velmi podobné; Odpověď Iana zmiňuje problém, který MSN kdysi měl s hash tabulkami PSČ . Toto je použití, kde vyhnutí se kolizi na pravděpodobných vstupech zvítězí nad náhodným chováním.

Dalším poučným srovnáním je kontrast v cílech návrhu mezi CRC a kryptografickými hashovacími funkcemi: / p>

• CRC je navržen tak, aby zachytil chyby vyplývající z hlučných komunikačních kanálů , které pravděpodobně budou malé množství bitů kterým jsou přiděleny omezené výpočetní zdroje, ale libovolně velká chytrost.

Takže pro CRC je opět dobré mít v minimálně odlišných vstupech méně kolizí než náhodných. S kryptovacími hashe je to ne-ne!

Algoritmy SHA (včetně SHA-256) jsou navržen být rychlý .

Ve skutečnosti může být jejich rychlost někdy problémem. Běžnou technikou pro ukládání tokenu odvozeného od hesla je zejména spuštění standardního rychlého algoritmu hash 10 000krát (uložení hash hash hash hash … hesla).

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

Výstup:

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

Komentáře

• Je to ‚ relativně rychlé, jistě, pro kryptografický hashovací algoritmus . Ale OP chce jen uložit hodnoty do hashtable a já si nemyslím, že by kryptografická hashovací funkce byla k tomu opravdu vhodná.
• Vyvstala otázka (tangenciálně se to nyní objevuje) předmět kryptografických hashovacích funkcí. To je ‚ bit, na který reaguji.
• Jen proto, abych lidi odradil od myšlenky “ Zejména , běžnou technikou pro uložení tokenu odvozeného od hesla je spuštění standardního rychlého hashovacího algoritmu 10 000krát “ – zatímco běžné je, že ‚ je prostě hloupý. Pro tyto scénáře jsou navrženy algoritmy, např. bcrypt. Používejte správné nástroje.
• Kryptografické hashe jsou navrženy tak, aby měly vysokou propustnost, ale to často znamená, že mají vysoké nastavení, demontáž, .rodata a / nebo státní náklady .Pokud chcete algoritmus pro hashtable, obvykle máte velmi krátké klíče a spoustu z nich, ale nepotřebujete další záruky kryptografického klíče. Sám používám vylepšený Jenkinsův one-at-a-time sám.
• @ChrisMorgan: namísto použití kryptograficky zabezpečeného hash lze HashTable DoS vyřešit mnohem efektivněji pomocí hash randomizace, takže každý běh programy nebo dokonce na každém hashtable, takže data se ‚ nedostanou pokaždé do stejného segmentu.

Použijte SipHash . Má mnoho žádoucích vlastností:

• Rychle. Optimalizovaná implementace trvá přibližně 1 cyklus na bajt.

• Zabezpečené. SipHash je silný PRF (pseudonáhodná funkce). To znamená, že je k nerozeznání od náhodné funkce (pokud neznáte 128bitový tajný klíč). Proto:

  • Není třeba se obávat, že se vaše sondy hash tabulky stanou lineárním časem kvůli kolizím. Se SipHash víte , že průměrně získáte průměrný výkon bez ohledu na vstupy.

  • Imunita vůči odepření útoků na základě hash.

  • Jako MAC můžete použít SipHash (zejména verzi se 128bitovým výstupem) (Ověřovací kód zprávy). Pokud obdržíte zprávu a značku SipHash a značka je stejná jako značka ze spuštění SipHash s vaším tajným klíčem, pak víte, že ten, kdo vytvořil hash, také vlastnil váš tajný klíč a že ani zpráva, ani hash byly od té doby změněny.

Komentáře

• Není ‚ t SipHash je přehnaný, pokud nepotřebujete zabezpečení? Vyžaduje 128bitový klíč, který je jen oslavovaným hashovým semenem. Nemluvě o MurmurHash3 má 128bitový výstup a SipHash má pouze 64bitový výstup. Je zřejmé, že větší výtah má nižší šanci na kolizi.
• @bryc Rozdíl je v tom, že SipHash bude i nadále dobře vychovaný, a to i při škodlivém vstupu. Hašovací tabulku založenou na SipHash lze použít pro data z potenciálně nepřátelských zdrojů a lze použít algoritmus, jako je lineární sondování, který je velmi citlivý na podrobnosti hashovací funkce.
• Siphash (a související novější prng funkce stylu) je moje výchozí volba pro zabezpečení. Z hlediska výkonu je xxhash těžké porazit. Na internetu je spousta špatných hashovacích rad, dokonce i v diskusích zde. Dobrý výkon na náhodných nebo částečně náhodných vstupech nemá smysl. Jaký je nejhorší výkon se vstupy ze skutečného světa? Jaký je výsledek škodlivých vstupů? Vaše hash tabulka se nakonec stane vektorem útoku.

Závisí to na datech, která hašujete. Některé hashování funguje lépe s konkrétními daty, jako je text. Některé hashovací algoritmy byly speciálně navrženy tak, aby byly vhodné pro konkrétní data.

Paul Hsieh jednou vytvořil rychlý hash . Uvádí zdrojový kód a vysvětlení. Ale už to bylo poraženo. 🙂

Java používá toto jednoduché násobení – a přidejte algoritmus:

Hašovací kód pro objekt String se vypočítá jako

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

pomocí int aritmetiky, kde s[i] je i ​ -tý znak řetězce, n je délka řetězce a ^ označuje umocňování. (Hodnota hash prázdného řetězce je nula.)

Tam jsou pravděpodobně mnohem lepší, ale je poměrně rozšířený a zdá se být dobrý kompromis mezi rychlostí a jedinečností.

Komentáře

• Nepoužívám ‚ úplně stejné jeden zde použitý, protože ‚ je stále relativně snadno způsobovat kolize. ‚ s rozhodně to není hrozné, ale existují mnohem lepší. A pokud ‚ není žádný významný důvod ke kompatibilitě s Javou, neměl by být vybrán .
• Pokud si přesto vyberete toto způsob hašování z nějakého důvodu můžete jako multiplikátor použít alespoň lepší prime jako 92821. To výrazně snižuje kolize. stackoverflow.com/a/2816747/21499
• Místo toho můžete také použít FNV1a. Je to ‚ s také jednoduchý hash založený na násobení, ale používá větší multiplikátor, který hash lépe rozptýlí.

Za prvé, proč musíte implementovat vlastní hashování? U většiny úkolů byste měli dosáhnout dobrých výsledků s datovými strukturami ze standardní knihovny, za předpokladu, že je k dispozici implementace (pokud to neděláte jen pro své vlastní vzdělávání).

Pokud jde o skutečné hashovací algoritmy, mým osobním favoritem je FNV. 1

Zde je příklad implementace 32bitové verze v jazyce 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; } 

Komentáře

• Varianta FNV-1a je o něco lepší s náhodností. Zaměňte pořadí * a ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619