Funkce hash - Hash function

Hašovací funkce je nějaká funkce , které mohou být použity k mapování dat o libovolné velikosti na hodnoty pevné velikosti. Hodnoty vrácené hashovací funkcí se nazývají hashovací hodnoty , hashovací kódy , digesty nebo jednoduše hashe . Hodnoty se obvykle používají k indexování tabulky s pevnou velikostí, která se nazývá hashovací tabulka . Použití hashovací funkce k indexování hashovací tabulky se nazývá hašovací nebo bodové adresování úložiště .

Hashovací funkce a jim přidružené hashovací tabulky se používají v aplikacích pro ukládání a načítání dat k přístupu k datům v malém a téměř konstantním čase na jedno načtení. Vyžadují množství úložného prostoru jen zlomkově větší než celkový prostor požadovaný pro data nebo samotné záznamy. Hašování je výpočetně a úložně prostorově efektivní forma přístupu k datům, která se vyhýbá nelineární době přístupu k uspořádaným a neuspořádaným seznamům a strukturovaným stromům a často exponenciálním požadavkům na úložiště přímého přístupu ke stavovým prostorům klíčů s velkou nebo proměnnou délkou.

Použití hašovacích funkcí závisí na statistických vlastnostech interakce klíčů a funkcí: nejhorší chování je nesnesitelně špatné s mizivou pravděpodobností a průměrné chování může být téměř optimální (minimální kolize ).

Hašovací funkce souvisejí s kontrolními součty (a často se s nimi zaměňují) , kontrolují číslice , otisky prstů , ztrátovou kompresi , funkce randomizace , kódy opravující chyby a šifry . Ačkoli se koncepty do určité míry překrývají, každý má svá vlastní použití a požadavky a je navržen a optimalizován odlišně. Hashovací funkce se liší od konceptů očíslovaných hlavně z hlediska integrity dat.

Přehled

Hašovací funkce přebírá vstup jako klíč, který je spojen s počátkem nebo záznamem a slouží k jeho identifikaci v aplikaci pro ukládání a načítání dat. Klíče mohou mít pevnou délku, například celé číslo, nebo proměnnou délku, například jméno. V některých případech je klíčem samotný datum. Výstupem je hashovací kód používaný k indexování hashovací tabulky obsahující data nebo záznamy nebo odkazy na ně.

Za hashovací funkci lze považovat provedení tří funkcí:

• Převeďte klíče s proměnnou délkou na hodnoty s pevnou délkou (obvykle délka strojového slova nebo méně) jejich složením podle slov nebo jiných jednotek pomocí operátoru zachovávajícího paritu, jako je ADD nebo XOR.
• Zakódujte bity klíče tak, aby výsledné hodnoty byly rovnoměrně rozloženy po prostoru klíčů.
• Namapujte klíčové hodnoty na hodnoty menší nebo rovné velikosti tabulky

Dobrá hashovací funkce splňuje dvě základní vlastnosti: 1) měla by být velmi rychlá k výpočtu; 2) měl by minimalizovat zdvojování výstupních hodnot (kolize). Hash funkce spoléhají na generování příznivých rozdělení pravděpodobnosti pro jejich účinnost, což snižuje přístupovou dobu téměř konstantní. Vysoké faktory načítání tabulky, sady patologických klíčů a špatně navržené hašovací funkce mohou mít za následek, že se přístupové časy blíží lineárnímu počtu položek v tabulce. Hašovací funkce mohou být navrženy tak, aby poskytovaly nejlepší výkon v nejhorších případech, dobrý výkon při vysokých faktorech načítání tabulky a ve zvláštních případech dokonalé (bezkolizní) mapování klíčů do hash kódů. Implementace je založena na bitových operacích zachovávajících paritu (XOR a ADD), násobení nebo dělení. Nezbytným doplňkem hashovací funkce je metoda řešení kolizí, která využívá pomocnou datovou strukturu, jako jsou propojené seznamy , nebo systematické sondování tabulky k nalezení prázdného slotu.

Hashovací tabulky

Hašovací funkce se používají ve spojení s hashovacími tabulkami k ukládání a načítání datových položek nebo datových záznamů. Funkce hash převede klíč spojený s každým vztažným bodem nebo záznamem do hashovacího kódu, který se používá k indexování hashovací tabulky. Když má být položka přidána do tabulky, hashovací kód může indexovat prázdný slot (také nazývaný kbelík), v takovém případě je položka přidána do tabulky tam. Pokud kód hash indexuje celý slot, je vyžadován nějaký druh řešení kolize: nová položka může být vynechána (není přidána do tabulky), nebo může být nahrazena starou položkou, nebo může být přidána do tabulky na jiném místě stanovený postup. Tento postup závisí na struktuře hashovací tabulky: V řetězcovém hašování je každý slot hlavou propojeného seznamu nebo řetězce a položky, které se ve slotu srazí, se přidají do řetězce. Řetězy mohou být uchovávány v náhodném pořadí a prohledávány lineárně nebo v sériovém pořadí nebo jako seznam s vlastním uspořádáním podle frekvence, aby se urychlil přístup. Při hašování otevřené adresy je tabulka sondována počínaje obsazeným slotem specifikovaným způsobem, obvykle lineárním sondováním , kvadratickým snímáním nebo dvojitým hashováním, dokud není umístěn otevřený slot nebo je sondována celá tabulka (přetečení). Hledání položky probíhá stejným způsobem, dokud se položka nenalezne, nenajde se otevřený slot nebo není prohledána celá tabulka (položka není v tabulce).

Specializované použití

Funkce hash se také používají k vytváření mezipaměti pro velké datové sady uložené v pomalých médiích. Cache je obecně jednodušší než hašovaná vyhledávací tabulka, protože jakoukoli kolizi lze vyřešit vyřazením nebo zapsáním starší ze dvou kolidujících položek.

Hashovací funkce jsou základní složkou Bloom filtru , prostorově efektivní pravděpodobnostní datové struktury, která se používá k testování, zda je prvek členem sady .

Zvláštní případ hašování je známý jako geometrické hašování nebo metoda mřížky . V těchto aplikacích je množina všech vstupů jakýmsi metrickým prostorem a hashovací funkci lze interpretovat jako rozdělení tohoto prostoru do mřížky buněk . V tabulce je často pole se dvěma nebo více indexů (nazývané souboru mřížka , index mřížka , vědro mřížky a podobné názvy) a hash funkce vrací index n-tice . Tento princip je široce používán v počítačové grafice , výpočetní geometrii a mnoha dalších disciplínách k řešení mnoha problémů blízkosti v rovině nebo v trojrozměrném prostoru , jako je hledání nejbližších dvojic v sadě bodů, podobných tvarů v seznamu tvarů, podobné obrázky v databázi obrázků atd.

Hashovací tabulky se také používají k implementaci asociativních polí a dynamických sad .

Vlastnosti

Jednotnost

Dobrá hashovací funkce by měla ve svém výstupním rozsahu mapovat očekávané vstupy co nejrovnoměrněji. To znamená, že každá hodnota hash ve výstupním rozsahu by měla být generována se zhruba stejnou pravděpodobností . Důvodem tohoto posledního požadavku je, že náklady na metody založené na hašování prudce rostou, protože roste počet kolizí- párů vstupů, které jsou mapovány na stejnou hodnotu hash. Pokud se některé hodnoty hash vyskytují s větší pravděpodobností než jiné, bude muset větší část vyhledávacích operací prohledávat větší sadu položek s kolidující tabulkou.

Toto kritérium vyžaduje pouze rovnoměrné rozdělení hodnoty , nikoli náhodné . Dobrá randomizační funkce je (kromě problémů s výpočetní efektivitou) obecně dobrou volbou jako hashovací funkce, ale opak nemusí být pravdivý.

Hashovací tabulky často obsahují pouze malou podmnožinu platných vstupů. Například seznam členů klubu může obsahovat pouze stovku jmen členů z velmi široké sady všech možných jmen. V těchto případech by kritérium jednotnosti mělo platit pro téměř všechny typické podmnožiny položek, které lze v tabulce nalézt, nejen pro globální sadu všech možných záznamů.

Jinými slovy, pokud je typická sada m záznamů hašována do n slotů tabulky, pravděpodobnost, že kbelík přijme mnohem více než m / n záznamů, by měla být mizivě malá. Zejména pokud je m menší než n , velmi málo segmentů by mělo mít více než jeden nebo dva záznamy. Malý počet kolizí je prakticky nevyhnutelný, i když n je mnohem větší než m - viz problém narozenin .

Ve zvláštních případech, kdy jsou klíče známy předem a sada klíčů je statická, lze nalézt hashovací funkci, která dosahuje absolutní (nebo bezkolizní) uniformity. Taková hashovací funkce je prý dokonalá . Neexistuje žádný algoritmický způsob konstrukce takové funkce - hledání jednoho je faktoriální funkcí počtu klíčů, které mají být mapovány, oproti počtu tabulkových slotů, do kterých se klepnou. Nalezení dokonalé hashovací funkce na více než velmi malé sadě klíčů je obvykle výpočetně neproveditelné; výsledná funkce bude pravděpodobně výpočetně složitější než standardní hashovací funkce a poskytuje pouze okrajovou výhodu oproti funkci s dobrými statistickými vlastnostmi, která přináší minimální počet kolizí. Viz univerzální hashovací funkce .

Testování a měření

Při testování funkce hash lze jednotnost rozložení hodnot hash vyhodnotit chí-kvadrát testem . Tento test je měřítkem shody: je to skutečné rozdělení položek v kbelících oproti očekávané (nebo rovnoměrné) distribuci položek. Vzorec je: ${\ Displaystyle {\ frac {\ sum _ {j = 0}^{m-1} (b_ {j}) (b_ {j} +1)/2} {(n/2m) (n+2m-1 )}}}$

kde: je počet klíčů, je počet kbelíků, je počet položek v kbelíku${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle b_ {j}}$${\ displaystyle j}$

Poměr v rámci jednoho intervalu spolehlivosti (0,95 - 1,05) naznačuje, že vyhodnocená hashovací funkce má očekávané rovnoměrné rozdělení.

Funkce hash mohou mít některé technické vlastnosti, díky nimž je pravděpodobnější, že budou mít při použití rovnoměrné rozdělení. Jedním z nich je přísné lavinové kritérium : kdykoli je doplněn jeden vstupní bit, každý z výstupních bitů se mění s 50% pravděpodobností. Důvodem této vlastnosti je, že vybrané podmnožiny prostoru klíčů mohou mít nízkou variabilitu. Aby byl výstup rovnoměrně distribuován, malá variabilita, dokonce i jeden bit, by se měla promítnout do vysoké variability (tj. Distribuce přes tabulkový prostor) na výstupu. Každý bit by se měl měnit s pravděpodobností 50%, protože pokud se některé bity zdráhají změnit, klíče se seskupí kolem těchto hodnot. Pokud se bity chtějí změnit příliš pohotově, mapování se blíží k pevné funkci XOR jediného bitu. Standardní testy pro tuto vlastnost byly popsány v literatuře. Zde je posouzena relevance kritéria pro multiplikační hashovací funkci.

Účinnost

V aplikacích pro ukládání a načítání dat je použití funkce hash kompromisem mezi časem hledání a prostorem pro ukládání dat. Pokud by doba hledání byla neomezená, velmi kompaktní neuspořádaný lineární seznam by byl nejlepším médiem; pokud by byl úložný prostor neomezený, náhodně přístupná struktura indexovatelná podle hodnoty klíče by byla velmi velká, velmi řídká, ale velmi rychlá. Hašovací funkce zabere určitý čas na mapování potenciálně velkého prostoru klíčů na proveditelné množství úložného prostoru, které lze prohledávat v omezeném čase bez ohledu na počet klíčů. Ve většině aplikací by hashovací funkce měla být vyčíslitelná s minimální latencí a sekundárně v minimálním počtu instrukcí.

Výpočetní náročnost se liší podle počtu požadovaných instrukcí a latence jednotlivých instrukcí, přičemž nejjednodušší jsou bitové metody (skládání), následované multiplikativními metodami a nejsložitější (nejpomalejší) jsou metody založené na dělení.

Protože kolize by neměly být časté a způsobovaly okrajové zpoždění, ale jinak jsou neškodné, je obvykle lepší zvolit rychlejší hashovací funkci než tu, která potřebuje více výpočtu, ale ušetří několik kolizí.

Zvláště znepokojující mohou být implementace založené na dělení, protože dělení je mikroprogramováno na téměř všech čipových architekturách. Dělení ( modulo ) konstantou lze invertovat, aby se stalo násobkem multiplikativní-inverzní konstanty velikosti slova. To může provést programátor nebo kompilátor. Rozdělení lze také zmenšit přímo na řadu odečtení posunu a přidání směny, ačkoli minimalizace počtu takovýchto požadovaných operací je skličujícím problémem; počet výsledných montážních pokynů může být více než tucet a zaplavit potrubí. Pokud má architektura funkční jednotky pro násobení hardwaru, je pravděpodobně lepší přístup k násobení podle inverzí.

Můžeme dovolit, aby velikost tabulky n nebyla mocninou 2 a stále nemusela provádět žádnou operaci zbytku nebo dělení, protože tyto výpočty jsou někdy nákladné. Například nechť n je výrazně menší než 2 ^b . Uvažujme funkci generátoru pseudonáhodných čísel P (klíč), která je v intervalu [0, 2 ^b  - 1] jednotná . Jednotná hashovací funkce v intervalu [0, n -1] je n P (klíč)/2 ^b . Dělení můžeme nahradit (možná rychlejším) posunem bitů vpravo : nP (klíč) >> b .

Pokud jsou klíče hašovány opakovaně a funkce hash je nákladná, lze výpočetní čas ušetřit předběžným výpočtem hash kódů a jejich uložením pomocí klíčů. Shoda hash kódů téměř jistě znamená, že klíče jsou identické. Tato technika se používá pro transpoziční tabulku v programech pro hraní her, která ukládá 64bitovou hašovanou reprezentaci pozice desky.

Univerzálnost

Univerzální hash schéma je randomizovaná algoritmus , který vybírá funkce hash h mezi rodiny takových funkcí, a to takovým způsobem, aby byla pravděpodobnost, že srážky jakýchkoliv dvou odlišných klíčů je 1 / m , kde m je počet různých hash hodnoty požadované - nezávisle na dvou klíčích. Univerzální hašování zajišťuje (v pravděpodobnostním smyslu), že aplikace hashovací funkce se bude chovat stejně dobře, jako kdyby používala náhodnou funkci, pro jakoukoli distribuci vstupních dat. Bude však mít více kolizí než dokonalé hašování a může vyžadovat více operací než speciální hashovací funkce.

Použitelnost

Funkce hash je použitelná v různých situacích. Hashovací funkce, která umožňuje pouze určité velikosti tabulek, řetězce pouze do určité délky, nebo nemůže přijmout seed (tj. Povolit dvojité hašování), není tak užitečná jako ta, která ano.

Deterministické

Procedura hash musí být deterministická - což znamená, že pro danou vstupní hodnotu musí vždy generovat stejnou hodnotu hash. Jinými slovy, musí to být funkce dat, která mají být hašována, v matematickém smyslu tohoto termínu. Tento požadavek vylučuje hashovací funkce, které závisí na externích parametrech proměnných, jako jsou generátory pseudonáhodných čísel nebo denní doba. Rovněž vylučuje funkce, které závisí na adrese paměti hašovaného objektu v případech, kdy se adresa může během provádění změnit (jak se může stát v systémech, které používají určité metody shromažďování odpadků ), i když někdy je možné přepracování položky.

Determinismus je v kontextu opětovného použití funkce. Například Python přidává funkci, která hashovací funkce využívají náhodného semene, které je generováno jednou, když se kromě vstupu, který má být hašován, spustí proces Pythonu. Při použití v rámci jednoho běhu je hash Pythonu ( SipHash ) stále platnou hashovací funkcí. Pokud jsou však hodnoty trvalé (například zapsané na disk), nelze je již považovat za platné hodnoty hash, protože v příštím spuštění se náhodná hodnota může lišit.

Definovaný rozsah

Často je žádoucí, aby výstup hashovací funkce měl pevnou velikost (ale viz níže). Pokud je například výstup omezen na 32bitové celočíselné hodnoty, lze hodnoty hash použít k indexování do pole. Takové hašování se běžně používá k urychlení vyhledávání dat. Produkci výstupu s pevnou délkou ze vstupu s proměnnou délkou lze dosáhnout rozdělením vstupních dat na bloky konkrétní velikosti. Hashovací funkce používané pro vyhledávání dat používají nějaký aritmetický výraz, který iterativně zpracovává bloky vstupu (například znaky v řetězci) k vytvoření hodnoty hash.

Variabilní rozsah

V mnoha aplikacích se rozsah hodnot hash může lišit pro každé spuštění programu nebo se může měnit během stejného běhu (například když je třeba rozšířit tabulku hash). V takových situacích potřebuje hashovací funkci, která přebírá dva parametry - vstupní data z a počet n povolených hodnot hash.

Běžným řešením je vypočítat fixní hashovací funkci s velmi velkým rozsahem (řekněme 0 až 2 ³²  - 1 ), výsledek vydělit n a použít zbytek dělení . Pokud n je samo o sobě mocninou 2 , lze to provést bitovým maskováním a bitovým posunem . Když je použit tento přístup, hashovací funkce musí být zvolena tak, aby výsledek měl poměrně rovnoměrné rozdělení mezi 0 a n  - 1 , pro jakoukoli hodnotu n, která se může v aplikaci vyskytnout. V závislosti na funkci může být zbytek jednotný pouze pro určité hodnoty n , např. Lichá nebo prvočísla .

Variabilní rozsah s minimálním pohybem (funkce dynamického hashování)

Když se hashovací funkce používá k ukládání hodnot do hashovací tabulky, která přežije běh programu, a hash tabulku je třeba rozšířit nebo zmenšit, hashovací tabulka se označuje jako dynamická hashovací tabulka.

Je žádoucí hashovací funkce, která při změně velikosti tabulky přemístí minimální počet záznamů. Co je potřeba, je hashovací funkce H ( z , n )  - kde z je hašovaný klíč a n je počet povolených hodnot hash - takový, že H ( z , n  + 1) = H ( z , n ) s pravděpodobností blízko k n /( n  + 1) .

Lineární hašování a spirálové ukládání jsou příklady dynamických hashovacích funkcí, které se provádějí ve stálém čase, ale uvolňují vlastnost uniformity, aby dosáhly vlastnosti minimálního pohybu. Rozšiřitelné hašování používá pro výpočet hashovací funkce dynamickou hashovací funkci, která vyžaduje prostor úměrný n , a stává se funkcí předchozích kláves, které byly vloženy. Bylo vynalezeno několik algoritmů, které zachovávají vlastnost uniformity, ale vyžadují čas úměrný n pro výpočet hodnoty H ( z , n ) .

Funkce hash s minimálním pohybem je obzvláště užitečná v distribuovaných tabulkách hash .

Normalizace dat

V některých aplikacích mohou vstupní data obsahovat funkce, které jsou pro účely srovnání irelevantní. Například při vyhledávání osobního jména může být žádoucí ignorovat rozdíl mezi velkými a malými písmeny. Pro taková data je třeba použít hashovací funkci, která je kompatibilní s použitým kritériem ekvivalence dat : to znamená, že jakékoli dva vstupy, které jsou považovány za ekvivalentní, musí poskytovat stejnou hashovací hodnotu. Toho lze dosáhnout normalizací vstupu před jeho hašováním, jako pomocí psaní velkých písmen na všechna písmena.

Hašování celočíselných datových typů

Existuje několik běžných algoritmů pro hašování celých čísel. Metoda poskytující nejlepší distribuci je závislá na datech. Jednou z nejjednodušších a nejběžnějších metod v praxi je metoda modulo divize.

Funkce hash identity

Pokud jsou data, která mají být hašována, dostatečně malá, lze jako hašovanou hodnotu použít samotná data (reinterpretovaná jako celé číslo). Náklady na výpočet této funkce hash identity jsou ve skutečnosti nulové. Tato funkce hash je perfektní , protože mapuje každý vstup na odlišnou hodnotu hash.

Význam „dostatečně malý“ závisí na velikosti typu, který je použit jako hašovaná hodnota. Například v Javě je hashovací kód 32bitové celé číslo. 32bitové celočíselné Integera 32bitové Floatobjekty s plovoucí desetinnou čárkou tedy mohou jednoduše použít hodnotu přímo; vzhledem k tomu, že 64bitové celé číslo Longa 64bitové číslo s plovoucí desetinnou čárkou Doubletuto metodu použít nemohou.

Jiné typy dat mohou také použít toto schéma hašování. Například při mapování řetězců znaků mezi velkými a malými písmeny lze použít binární kódování každého znaku, interpretovaného jako celé číslo, k indexování tabulky, která udává alternativní formu daného znaku („A“ pro „a“, „ 8 "pro" 8 "atd.). Pokud je každý znak uložen v 8 bitech (jako v rozšířeném ASCII nebo ISO Latin 1 ), má tabulka pouze 2 ⁸ = 256 položek; v případě znaků Unicode by tabulka měla 17 × 2 ¹⁶ =1 114 112 záznamů.

Stejnou technikou lze namapovat dvoupísmenné kódy zemí jako „nás“ nebo „za“ na názvy zemí (26 ² = 676 záznamů v tabulkách), 5místná poštovní směrovací čísla jako 13083 na názvy měst (100 000 záznamů) atd. Neplatné hodnoty dat (například kód země „xx“ nebo PSČ 00000) mohou být v tabulce ponechány nedefinovány nebo namapovány na vhodnou hodnotu „null“.

Triviální hashovací funkce

Pokud jsou klíče rovnoměrně nebo dostatečně rovnoměrně rozloženy v prostoru klíčů, takže hodnoty klíčů jsou v podstatě náhodné, mohou být považovány za již „hašované“. V tomto případě lze vytočit libovolný počet libovolných bitů v klíči a porovnat je jako index do hashovací tabulky. Jednoduchá hashovací funkce by byla maskování spodních bitů m, které by se použily jako index do tabulky o velikosti 2 ^m .

Skládací

Skládací hashovací kód se vytvoří rozdělením vstupu do n sekcí m bitů, kde 2^m je velikost tabulky, a pomocí paritní operace zachovávající bitové operace, jako je ADD nebo XOR, pro kombinování sekcí. Poslední operací je maska ​​nebo posuny, aby se odstranily přebytečné bity na horním nebo dolním konci. Například pro velikost tabulky 15 bitů a klíčovou hodnotu 0x0123456789ABCDEF existuje 5 sekcí 0x4DEF, 0x1357, 0x159E, 0x091A a 0x8. Přidáním získáme 0x7AA4, 15bitovou hodnotu.

Střední čtverce

Hašovací kód středních čtverců se vytvoří tak, že se vstup do něj vydělí a extrahuje se příslušný počet středních číslic nebo bitů. Pokud je například vstup 123 456 789 a velikost hashovací tabulky 10 000, kvadratura klíče vytvoří 15 241 578 750 150 9021, takže hashovací kód je brán jako prostřední 4 číslice 17místného čísla (ignorování vysoké číslice) 8750. Střední čtverce metoda vytváří rozumný hashovací kód, pokud v klíči není mnoho úvodních nebo koncových nul. Toto je varianta multiplikativního hašování, ale ne tak dobrá, protože libovolný klíč není dobrý multiplikátor.

Hašování divize

Standardní technikou je použití modulo funkce na klíči výběrem dělitele, který je prvočíslem blízkým velikosti tabulky, takže . Velikost tabulky je obvykle mocninou 2. To dává rozdělení od . To poskytuje dobré výsledky u velkého počtu klíčových sad. Významnou nevýhodou hašování divizí je, že dělení je mikroprogramováno na většině moderních architektur včetně x86 a může být 10krát pomalejší než násobení. Druhou nevýhodou je, že nerozbíjí seskupené klíče. Například klíče 123000, 456000, 789000 atd. Modulo 1000 mapují všechny na stejnou adresu. Tato technika funguje v praxi dobře, protože mnoho klíčových sad je již dostatečně náhodných a pravděpodobnost, že klíčová sada bude cyklická s velkým prvočíslem, je malá. ${\ displaystyle M}$${\ Displaystyle h (K) = K \ mod M}$${\ displaystyle \ {0, M-1 \}}$

Algebraické kódování

Algebraické kódování je variantou metody dělení hashování, která k dělení n bitů na m bitů používá místo celého čísla dělení polynomickým modulem 2. V tomto přístupu postulujeme polynom thého stupně . Klíč lze považovat za polynom . Zbývající část pomocí polynomického aritmetického modulu 2 je . Potom . Pokud je konstruován tak, aby měl t nebo méně nenulových koeficientů, pak klíče, které sdílejí méně než t bitů, zaručeně nekolidují. ${\ displaystyle M = 2^{m}}$${\ displaystyle m}$${\ Displaystyle \ mathrm {Z} (x) = x^{m}+\ zeta _ {m-1} x^{m-1}+...+\ zeta _ {0}}$${\ Displaystyle K = (k_ {n-1} ... k_ {1} k_ {0}) _ {2}}$${\ Displaystyle K (x) = k_ {n-1} x^{n-1}+...+k_ {1} x+k_ {0}}$${\ Displaystyle K (x) \ mod {Z (x)} = h_ {m-1} x^{m-1}+...+h_ {1} x+h_ {0}}$${\ Displaystyle h (K) = (h_ {m-1} ... h_ {1} h_ {0}) _ {2}}$${\ displaystyle Z (x)}$

Z funkce k, t a n, dělitel 2 ^k -1, je sestrojena z pole GF (2 ^k ). Knuth dává příklad: pro n = 15, m = 10 a t = 7, . Odvození je následující: ${\ Displaystyle Z (x) = x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$

Nechť je nejmenší sada celých čísel${\ displaystyle S}$${\ Displaystyle \ ni \ {1,2, ..., t \} \ subseteq S \ land (2j) \ mod n \ in S \ forall j \ in S}$

Definujte, kde a kde se počítají koeficienty v tomto poli. Pak stupeň . Vzhledem k tomu, je kořen , kdykoliv je kořen, to znamená, že se koeficienty v splňují tak, že jsou všechny 0 nebo 1. Pokud je jakákoliv nenulová polynomu modulo 2 s nejvýše t nenulových koeficientů, pak není násobkem modulo 2. Z toho vyplývá, že odpovídající hashovací funkce bude mapovat klíče s méně než t bity společnými pro jedinečné indexy. ${\ Displaystyle P (x) = \ prod _ {j \ in S} (x- \ alpha ^{j})}$${\ Displaystyle \ alpha \ in ^{n} GF (2 ^{k})}$${\ displaystyle P (x)}$${\ displaystyle P (x) = | S |}$${\ displaystyle \ alpha ^{2j}}$${\ displaystyle P (x)}$${\ displaystyle \ alpha ^{j}}$${\ displaystyle p^{i}}$${\ displaystyle P (x)}$${\ displaystyle p_ {i}^{2} = p_ {i}}$${\ Displaystyle R (x) = r _ {(n-1)} x^{n-1}+...+r_ {1} x+r_ {0}}$${\ displaystyle R (x)}$${\ displaystyle P (x)}$

Obvyklý výsledek je, že buď n bude velké, nebo kepr velké, nebo obojí, aby bylo schéma výpočetně proveditelné. Proto je vhodnější pro implementaci hardwaru nebo mikrokódu.

Unikátní hashování permutace

Viz také jedinečné hašování permutací, které má zaručenou nejlepší dobu vložení v nejhorším případě.

Multiplikativní hašování

Standardní multiplikativní hašování používá vzorec, který vytváří hodnotu hash v . Hodnota je vhodně zvolena hodnota, která by měla být relativně primární , aby ; měl by být velký a jeho binární reprezentace náhodná kombinace 1 a 0. Důležitý praktický speciální případ nastane, když a jsou mocniny 2 a je to velikost strojového slova . V tomto případě se tento vzorec stává . To je zvláštní, protože aritmetický modul se standardně provádí v nízkoúrovňových programovacích jazycích a celočíselné dělení mocninou 2 je jednoduše posun vpravo, takže například v C se tato funkce stává ${\ Displaystyle h_ {a} (K) = \ lfloor (aK {\ bmod {W}})/(W/M) \ rfloor}$${\ displaystyle \ {0, \ ldots, M-1 \}}$${\ displaystyle a}$${\ displaystyle W}$${\ displaystyle W = 2^{w}}$${\ displaystyle M = 2^{m}}$${\ displaystyle w}$${\ Displaystyle h_ {a} (K) = \ lfloor (aK {\ bmod {2}}^{w})/2^{wm} \ rfloor}$${\ displaystyle 2^{w}}$

unsigned hash(unsigned K)
{ 
   return (a*K) >> (w-m);
}

a pro pevné a to se promítá do jednoho celočíselného násobení a posunu doprava, což z něj činí jednu z nejrychlejších hashovacích funkcí pro výpočet. ${\ displaystyle m}$${\ displaystyle w}$

Multiplikativní hašování je náchylné k „běžné chybě“, která vede ke špatné difúzi-vstupní bity s vyšší hodnotou neovlivňují výstupní bity s nižší hodnotou. Transmutace na vstupu, která posouvá rozsah ponechaných horních bitů dolů a XOR nebo je přidá ke klíči, než to krok multiplikace napraví. Výsledná funkce tedy vypadá takto:

unsigned hash(unsigned K)
{
   K ^= K >> (w-m); 
   return (a*K) >> (w-m);
}

Fibonacciho hašování

Fibonacciho hašování je forma multiplikačního hašování, ve které je multiplikátor , kde je délka strojového slova a (phi) je zlatý řez . je iracionální číslo s přibližnou hodnotou 5/3 a desetinnou expanzí 1,618033 ... Vlastností tohoto multiplikátoru je, že rovnoměrně rozděluje po tabulkovém prostoru bloky po sobě následujících klíčů vzhledem k jakémukoli bloku bitů v klíči. Po sobě jdoucí klíče v rámci vysokých nebo nízkých bitů klíče (nebo jiného pole) jsou relativně běžné. Multiplikátory pro různé délky slov jsou: ${\ Displaystyle 2^{w}/\ phi}$${\ displaystyle w}$${\ displaystyle \ phi}$${\ displaystyle \ phi}$${\ displaystyle ^{w}}$

• 16: a = 40503 ₁₀
• 32: a = 2654435769 ₁₀
• 48: a = 173961102589771 ₁₀
• 64: a = 11400714819323198485 ₁₀

Zobrist hash

Tabulační hašování, obecněji známé jako hashování Zobristů po americkém počítačovém vědci Albertu Zobristovi , je metoda pro konstrukci univerzálních rodin hashovacích funkcí kombinací vyhledávání tabulek s operacemi XOR. Tento algoritmus se ukázal být velmi rychlý a vysoce kvalitní pro účely hašování (zejména hašování celých číselných klíčů).

Zobrist hash byl původně představen jako prostředek kompaktního znázornění šachových pozic v programech pro hraní počítačových her. Bylo přiděleno jedinečné náhodné číslo, které bude reprezentovat každý typ figurky (po šesti pro černé a bílé) na každém místě desky. Proto je tabulka 64x12 takových čísel inicializována na začátku programu. Náhodná čísla mohla mít libovolnou délku, ale 64 bitů bylo přirozené kvůli 64 čtvercům na desce. Pozice byla přepsána cyklováním mezi kousky v pozici, indexováním odpovídajících náhodných čísel (prázdná místa nebyla zahrnuta do výpočtu) a jejich XORingem dohromady (počáteční hodnota mohla být 0, hodnota identity pro XOR nebo náhodná semínko). Výsledná hodnota byla snížena modulo, skládáním nebo nějakou jinou operací k vytvoření indexu tabulky hash. Původní Zobristův hash byl uložen v tabulce jako reprezentace pozice.

Později byla metoda rozšířena na hashování celých čísel reprezentováním každého bajtu v každé ze 4 možných pozic ve slově unikátním 32bitovým náhodným číslem. Je tedy sestavena tabulka 2 ⁸ x 4 takových náhodných čísel. 32bitové hašované celé číslo je přepsáno postupným indexováním tabulky s hodnotou každého bajtu celého textu prostého textu a XORingem načtených hodnot dohromady (opět počáteční hodnotou může být hodnota identity nebo náhodné semeno). Přirozené rozšíření na 64bitová celá čísla je pomocí tabulky 2 ⁸ x8 64bitových náhodných čísel.

Tento druh funkce má několik pěkných teoretických vlastností, z nichž jedna se nazývá nezávislost na 3-tice, což znamená, že každé 3-tice klíčů je stejně pravděpodobné, že budou mapovány na 3-tice hodnot hash.

Přizpůsobená hashovací funkce

Funkci hash lze navrhnout tak, aby využívala stávající entropii v klíčích. Pokud mají klíče úvodní nebo koncové nuly nebo konkrétní pole, která jsou nepoužitá, vždy nulová nebo jiná konstanta, nebo se obecně málo liší, pak maskování pouze těkavých bitů a jejich hašování poskytne lepší a možná rychlejší hashovací funkci. Vybraní dělitelé nebo multiplikátory v dělení a multiplikačních schématech mohou zajišťovat jednotnější hashovací funkce, pokud jsou klíče cyklické nebo mají jiné nadbytečnost.

Hašování dat s proměnnou délkou

Pokud jsou datové hodnoty dlouhé (nebo proměnné) znakové řetězce- například osobní jména, adresy webových stránek nebo poštovní zprávy-je jejich distribuce obvykle velmi nerovnoměrná a komplikované závislosti. Například text v jakémkoli přirozeném jazyce má velmi nejednotné rozdělení znaků a dvojic znaků, charakteristické pro daný jazyk. Pro taková data je rozumné použít hashovací funkci, která závisí na všech znacích řetězce - a závisí na každém znaku jiným způsobem.

Uprostřed a končí

Zjednodušené hashovací funkce mohou přidat první a poslední n znaků řetězce spolu s délkou, nebo mohou ze středních 4 znaků řetězce vytvořit hash velikosti slova. To ušetří iteraci nad (potenciálně dlouhým) řetězcem, ale hashovací funkce, které nehašují všechny znaky řetězce, se mohou snadno stát lineárními kvůli nadbytečnosti, shlukování nebo jiným patologiím v sadě klíčů. Takové strategie mohou být účinné jako vlastní hashovací funkce, pokud je struktura klíčů taková, že buď střed, konce nebo jiná pole jsou nulová nebo nějaká jiná neměnná konstanta, která klíče nerozlišuje; pak lze invariantní části klíčů ignorovat.

Skládání postav

Paradigmatickým příkladem skládání podle znaků je sečtení celočíselných hodnot všech znaků v řetězci. Lepší nápad je vynásobit součet hash konstantou, obvykle značným prvočíslem, před přidáním dalšího znaku, ignorování přetečení. Věrohodnou alternativou je také použití exkluzivního „nebo“ namísto přidání. Poslední operací by byla modulo, maska ​​nebo jiná funkce pro snížení hodnoty slova na index velikosti tabulky. Slabinou tohoto postupu je, že informace se mohou shlukovat v horních nebo dolních bitech bajtů, přičemž shlukování zůstane v hašovaném výsledku a způsobí více kolizí než správný randomizační hash. Bajtové kódy ASCII mají například horní bit 0 a tisknutelné řetězce nepoužívají prvních 32 bajtových kódů, takže informace (95bajtové kódy) jsou ve zbývajících bitech seskupeny nejasným způsobem.

Klasický přístup nazvaný hash PJW na základě práce Petera. J. Weinberger ve společnosti ATT Bell Labs v 70. letech minulého století byl původně navržen pro hašování identifikátorů do tabulek symbolů kompilátoru, jak je uvedeno v „Dračí knize“ . Tato hashovací funkce odsadí bajty o 4 bity, než je spojíte dohromady. Když se množství zalomí, vysoké 4 bity se posunou ven a pokud jsou nenulové, XOR se vrátí zpět do dolního bajtu kumulativního množství. Výsledkem je hashovací kód velikosti slova, na který lze použít modulo nebo jinou redukční operaci k vytvoření konečného hashovacího indexu.

Dnes, zejména s příchodem 64bitových velikostí slov, je k dispozici mnohem efektivnější hašování řetězců s proměnnou délkou podle slovních bloků.

Skládání na délku slova

Moderní mikroprocesory umožní mnohem rychlejší zpracování, pokud 8bitové znakové řetězce nejsou hašovány zpracováním jednoho znaku najednou, ale interpretací řetězce jako pole 32bitových nebo 64bitových celých čísel a hašováním/akumulací těchto „širokých slov“ celočíselné hodnoty pomocí aritmetických operací (např. násobení konstantou a přesouvání bitů). Konečné slovo, které může mít neobsazené bajtové pozice, je před složením do hash vyplněno nulami nebo zadanou hodnotou „náhodného výběru“. Nahromaděný hashovací kód je redukován finální modulo nebo jinou operací, aby se získal index do tabulky.

Hašování konverze Radix

Analogicky ke způsobu, jakým je řetězec znaků ASCII nebo EBCDIC představující desítkové číslo převeden na číselnou veličinu pro výpočet, lze řetězec proměnné délky převést jako ( x ₀ a ^{k −1} + x ₁ a ^{k −2} + ... + x _{k −2} a + x _{k −1} ) . Toto je jednoduše polynom v nenulovém radixu a ! = 1, který bere komponenty ( x ₀ , x ₁ , ..., x _{k −1} ) jako znaky vstupního řetězce délky k . Lze jej použít přímo jako hashovací kód nebo na něj aplikovanou hashovací funkci pro mapování potenciálně velké hodnoty na velikost hashovací tabulky. Hodnota a je obvykle prvočíslo alespoň dostatečně velké, aby pojalo počet různých znaků ve znakové sadě potenciálních klíčů. Radixová konverze řetězců minimalizuje počet kolizí. Dostupné velikosti dat mohou omezit maximální délku řetězce, který lze hašovat touto metodou. Například 128bitové dvojitě dlouhé slovo bude hašovat pouze 26znakový abecední řetězec (ignorující velká a malá písmena) s radixem 29; tisknutelný řetězec ASCII je omezen na 9 znaků pomocí radix 97 a 64bitového dlouhého slova. Abecední klíče však mají obvykle skromnou délku, protože klíče musí být uloženy v tabulce hash. Řetězce číselných znaků obvykle nejsou problém; 64 bitů může počítat až 10 ¹⁹ nebo 19 desetinných míst s radixem 10.

Válcování hash

V některých aplikacích, jako je vyhledávání podřetězců , lze vypočítat hashovací funkci h pro každý podřetězec k -znaků daného řetězce n -znaků posunutím okna o šířce k znaků podél řetězce; kde k je pevné celé číslo an je větší než k . Přímé řešení, kterým je extrahovat takový podřetězec na každé pozici znaku v textu a počítat h samostatně, vyžaduje řadu operací úměrných k · n . Při správné volbě h je však možné použít techniku ​​válcování haše k výpočtu všech těchto hashů se snahou úměrnou mk  +  n, kde m je počet výskytů podřetězce.

Nejznámějším algoritmem tohoto typu je Rabin-Karp s nejlepším a průměrným výkonem případu O ( n + mk ) a nejhorším případem O ( n · k ) (ve vší slušnosti, nejhorší případ je vážně patologický: textový řetězec i podřetězce se skládají z opakovaného jediného znaku, například t = "AAAAAAAAAAA" a s = "AAA"). Hašovací funkcí používanou pro algoritmus je obvykle Rabinův otisk prstu , navržený tak, aby se zabránilo kolizím v řetězcích 8bitových znaků, ale používají se také jiné vhodné hashovací funkce.

Analýza

Výsledek nejhoršího případu pro hašovací funkci lze hodnotit dvěma způsoby: teoretickým a praktickým. Teoreticky nejhorším případem je pravděpodobnost, že se všechny klíče namapují na jeden slot. Očekává se praktický nejhorší případ nejdelší sekvence sondy (hashovací funkce + metoda řešení kolizí). Tato analýza uvažuje o jednotném hašování, to znamená, že jakýkoli klíč bude mapován na jakýkoli konkrétní slot s pravděpodobností 1/ m , charakteristickou pro univerzální hashovací funkce.

Zatímco se Knuth obává kontroverzního útoku na systémy v reálném čase, Gonnet ukázal, že pravděpodobnost takového případu je „směšně malá“. Jeho zastoupení bylo, že pravděpodobnost, že k o n mapování klíče do jedné štěrbiny , kde α je faktor zatížení, N / m . ${\ Displaystyle {\ frac {e ^{-\ alpha} \ alpha ^{k}} {k!}}}$

Dějiny

Termín „hash“ nabízí přirozenou analogii s jeho netechnickým významem („sekat“ nebo „dělat z něčeho nepořádek“), vzhledem k tomu, jak funkce hash kódují svá vstupní data, aby odvodily svůj výstup. Ve svém výzkumu přesného původu výrazu Donald Knuth poznamenává, že zatímco Hans Peter Luhn ze společnosti IBM se zdá být prvním, kdo v poznámce z ledna 1953 použil koncept hashovací funkce, samotný termín by se objevil pouze v publikovanou literaturu na konci šedesátých let minulého století o zásadách digitálního počítačového systému Herberta Hellermana , přestože v té době už to byl rozšířený žargon.

Viz také

Poznámky

Reference

externí odkazy

• Vypočítejte hash dané hodnoty Timo Denkem
• Funkce Goulburn Hashing ( PDF ) od Mayura Patela
• Konstrukce hashovací funkce pro vyhledávání textových a geometrických dat ( PDF ), nejnovější trendy na počítačích, sv. 2, s. 483–489, konference CSCC, Korfu, 2010