Hash -funktion - Hash function

En hash-funktion är vilken funktion som helst som kan användas för att mappa data av godtycklig storlek till värden med fast storlek. De värden som returneras av en hash -funktion kallas hashvärden , hashkoder , smältningar eller helt enkelt hash . Värdena används vanligtvis för att indexera en tabell med fast storlek som kallas en hashtabell . Användning av en hash -funktion för att indexera en hash -tabell kallas hashning eller scatter -lagringsadressering .

Hashfunktioner och deras tillhörande hashtabeller används i datalagrings- och hämtningsprogram för att komma åt data på en liten och nästan konstant tid per hämtning. De kräver en mängd lagringsutrymme som bara är fraktionellt större än det totala utrymmet som krävs för själva data eller poster. Hashing är en beräkningsmässigt och lagringsutrymmeeffektiv form av datatillgång som undviker den olinjära åtkomsttiden för ordnade och oordnade listor och strukturerade träd, och de ofta exponentiella lagringskraven för direktåtkomst av statliga utrymmen för stora eller variabla längder.

Användning av hashfunktioner är beroende av statistiska egenskaper hos nyckel- och funktionsinteraktion: värsta fall beteende är oacceptabelt dåligt med en försvinnande liten sannolikhet och genomsnittligt beteende kan vara nästan optimalt (minimal kollision ).

Hashfunktioner är relaterade till (och ofta förvirrade med) kontrollsummor , kontrollsiffror , fingeravtryck , komprimering utan förlust , randomiseringsfunktioner , felkorrigerande koder och chiffer . Även om begreppen till viss del överlappar varandra, har alla sina egna användningsområden och krav och är utformade och optimerade på olika sätt. Hashfunktionerna skiljer sig från de begrepp som numreras främst när det gäller dataintegritet.

Översikt

En hash -funktion tar en ingång som en nyckel, som är associerad med en datum eller post och används för att identifiera den för datalagrings- och hämtningsprogrammet. Nycklarna kan ha en fast längd, som ett heltal eller variabel längd, som ett namn. I vissa fall är nyckeln själva datumet. Utdata är en hashkod som används för att indexera en hashtabell som innehåller data eller poster eller pekar till dem.

En hash -funktion kan anses utföra tre funktioner:

• Konvertera nycklar med variabel längd till fasta längder (vanligtvis maskinordslängd eller mindre) genom att vika dem med ord eller andra enheter med en paritetsbevarande operatör som ADD eller XOR.
• Kryptera bitarna i nyckeln så att de resulterande värdena fördelas enhetligt över nyckelutrymmet.
• Kartlägg nyckelvärdena till värden som är mindre än eller lika med tabellens storlek

En bra hash -funktion uppfyller två grundläggande egenskaper: 1) det ska vara mycket snabbt att beräkna; 2) det bör minimera dubblering av utgångsvärden (kollisioner). Hashfunktioner är beroende av att generera gynnsamma sannolikhetsfördelningar för deras effektivitet, vilket reducerar åtkomsttiden till nästan konstant. Höga tabellbelastningsfaktorer, patologiska nyckeluppsättningar och dåligt utformade hashfunktioner kan resultera i att åtkomsttider närmar sig linjära i antalet objekt i tabellen. Hashfunktioner kan utformas för att ge bästa prestanda i värsta fall, bra prestanda under höga tabellbelastningsfaktorer och i speciella fall perfekt (kollisionsfri) kartläggning av nycklar till hashkoder. Implementeringen är baserad på paritetsbevarande bitoperationer (XOR och ADD), multiplicera eller dela. Ett nödvändigt tillägg till hash-funktionen är en kollisionsupplösningsmetod som använder en hjälpdatastruktur som länkade listor eller systematisk undersökning av tabellen för att hitta en tom plats.

Hashbord

Hashfunktioner används tillsammans med hashtabeller för att lagra och hämta dataobjekt eller dataposter. Hashfunktionen översätter nyckeln som är associerad med varje datum eller post till en hashkod, som används för att indexera hashtabellen. När ett objekt ska läggas till i tabellen kan hashkoden indexera en tom plats (kallas även en hink), i vilket fall objektet läggs till i tabellen där. Om hashkoden indexerar en full plats krävs någon form av kollisionsupplösning: det nya objektet kan utelämnas (läggs inte till i tabellen) eller ersätta det gamla objektet, eller det kan läggas till i tabellen på någon annan plats med ett specifikt förfarande. Denna procedur beror på hashtabellens struktur: I kedjad haschning är varje plats huvudet på en länkad lista eller kedja, och objekt som kolliderar vid luckan läggs till i kedjan. Kedjor kan hållas i slumpmässig ordning och sökas linjärt, eller i serieordning, eller som en självordnande lista efter frekvens för att påskynda åtkomsten. Vid öppen adresshashning sonderas bordet från det ockuperade facket på ett specifikt sätt, vanligtvis genom linjär sondering , kvadratisk sondering eller dubbel hashning tills en öppen lucka är lokaliserad eller hela bordet sonderas (överflöde). Att söka efter objektet följer samma procedur tills objektet är hittat, en öppen plats har hittats eller hela tabellen har sökts (objektet finns inte i tabellen).

Specialiserade användningsområden

Hashfunktioner används också för att bygga cacheminne för stora datamängder lagrade i långsamma medier. En cache är i allmänhet enklare än en haschad söktabell eftersom en kollision kan lösas genom att kasta eller skriva tillbaka den äldre av de två kolliderande objekten.

Hashfunktioner är en viktig ingrediens i Bloom-filtret , en rymdeffektiv probabilistisk datastruktur som används för att testa om ett element är medlem i en uppsättning .

Ett specialfall med haschning kallas geometrisk haschning eller rutnätmetoden . I dessa applikationer är uppsättningen av alla ingångar ett slags metriskt utrymme , och hashfunktionen kan tolkas som en partition av det utrymmet i ett rutnät av celler . Tabellen är ofta en matris med två eller flera index (kallas en rutfil , rutnätindex , skopnät och liknande namn), och hashfunktionen returnerar en indextupel . Denna princip används ofta i datorgrafik , beräkningsgeometri och många andra discipliner för att lösa många närhetsproblem i planet eller i tredimensionellt utrymme , till exempel att hitta närmaste par i en uppsättning punkter, liknande former i en lista med former, liknande bilder i en bilddatabas och så vidare.

Hashtabeller används också för att implementera associativa matriser och dynamiska uppsättningar .

Egenskaper

Enhetlighet

En bra hash -funktion bör kartlägga de förväntade inmatningarna så jämnt som möjligt över dess utgångsområde. Det vill säga att varje hashvärde i utmatningsområdet ska genereras med ungefär samma sannolikhet . Anledningen till detta sista krav är att kostnaden för haschbaserade metoder ökar kraftigt när antalet kollisioner- par av ingångar som kartläggs till samma hashvärde-ökar. Om det är mer troligt att vissa hashvärden förekommer än andra, måste en större bråkdel av sökningsoperationerna söka igenom en större uppsättning kolliderande tabellposter.

Observera att detta kriterium endast kräver att värdet är enhetligt fördelat , inte slumpmässigt i någon mening. En bra randomiseringsfunktion är (med undantag för problem med beräkningseffektivitet) i allmänhet ett bra val som hash -funktion, men det motsatta behöver inte vara sant.

Hashtabeller innehåller ofta bara en liten delmängd av de giltiga inmatningarna. Till exempel kan en medlemslista i klubben endast innehålla ett hundratal medlemsnamn, av den mycket stora uppsättningen alla möjliga namn. I dessa fall bör enhetlighetskriteriet gälla för nästan alla typiska delmängder av poster som kan finnas i tabellen, inte bara för den globala uppsättningen av alla möjliga poster.

Med andra ord, om en typisk uppsättning m -poster har haschats till n bordslitsar, bör sannolikheten för att en hink får många fler än m / n -poster vara försvinnande liten. I synnerhet om m är mindre än n bör väldigt få skopor ha mer än en eller två poster. Ett litet antal kollisioner är praktiskt taget oundvikligt, även om n är mycket större än m - se födelsedagsproblemet .

I speciella fall när nycklarna är kända i förväg och nyckeluppsättningen är statisk, kan en hash -funktion hittas som uppnår absolut (eller kollisionsfri) enhetlighet. En sådan hash -funktion sägs vara perfekt . Det finns inget algoritmiskt sätt att konstruera en sådan funktion - att söka efter en är en faktoriell funktion av antalet nycklar som ska mappas jämfört med antalet bordsslots som de knackas till. Att hitta en perfekt hash -funktion över mer än en mycket liten uppsättning nycklar är vanligtvis oberäkneligt; den resulterande funktionen kommer sannolikt att vara mer beräkningsmässigt komplex än en standard hash -funktion och ger endast en marginell fördel gentemot en funktion med goda statistiska egenskaper som ger ett minimalt antal kollisioner. Se universell hash -funktion .

Testning och mätning

Vid testning av en hash-funktion kan enhetligheten i distributionen av hashvärden utvärderas med chi-squared-testet . Detta test är ett mått av godhet: det är den faktiska fördelningen av föremål i hinkar jämfört med den förväntade (eller enhetliga) fördelningen av föremål. Formeln är: ${\ displaystyle {\ frac {\ sum _ {j = 0}^{m-1} (b_ {j}) (b_ {j} +1)/2} {(n/2m) (n+2m-1 )}}}}$

där: är antalet nycklar, är antalet skopor, är antalet objekt i hinken${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle b_ {j}}$${\ displaystyle j}$

Ett förhållande inom ett konfidensintervall (0,95 - 1,05) indikerar att den utvärderade hashfunktionen har en förväntad enhetlig fördelning.

Hashfunktioner kan ha vissa tekniska egenskaper som gör det mer troligt att de får en enhetlig fördelning när de tillämpas. Ett är det strikta lavinskriteriet : när en enda ingångsbit kompletteras ändras var och en av utmatningsbitarna med 50% sannolikhet. Anledningen till den här egenskapen är att utvalda delmängder av nyckelutrymmet kan ha låg variation. För att utmatningen ska vara enhetligt fördelad bör en låg mängd variabilitet, till och med en bit, leda till en stor mängd variabilitet (dvs. distribution över tabellutrymmet) i utdata. Varje bit bör ändras med en sannolikhet på 50%, för om vissa bitar är ovilliga att ändra, blir nycklarna grupperade kring dessa värden. Om bitarna vill förändras för lätt närmar sig mappningen en fast XOR -funktion för en enda bit. Standardtester för denna egenskap har beskrivits i litteraturen. Kriteriets relevans för en multiplikativ hash -funktion bedöms här.

Effektivitet

I datalagrings- och hämtningsprogram är användningen av en hash-funktion en avvägning mellan söktid och datalagringsutrymme. Om söktiden var obegränsad skulle en mycket kompakt oordnad linjär lista vara det bästa mediet. om lagringsutrymmet var obegränsat skulle en slumpmässigt tillgänglig struktur som kan indexeras med nyckelvärdet vara mycket stor, mycket gles, men mycket snabb. En hash -funktion tar en begränsad tid att mappa ett potentiellt stort nyckelutrymme till en möjlig mängd lagringsutrymme som kan sökas inom en begränsad tid oavsett antalet nycklar. I de flesta applikationer bör hash -funktionen kunna beräknas med minimal latens och i andra hand i ett minimalt antal instruktioner.

Computational complexity varies with the number of instructions required and latency of individual instructions, with the simplest being the bitwise methods (folding), followed by the multiplicative methods, and the most complex (slowest) are the division-based methods.

Eftersom kollisioner bör vara sällsynta och orsaka marginalfördröjning men i övrigt är ofarliga, är det vanligtvis att föredra att välja en snabbare hash -funktion framför en som behöver mer beräkning men sparar några kollisioner.

Divisionsbaserade implementeringar kan vara särskilt oroande eftersom divisionen är mikroprogrammerad på nästan alla chiparkitekturer. Dividera ( modulo ) med en konstant kan inverteras för att bli en multiplicera med ordstorleken multiplikativ-invers av konstanten. Detta kan göras av programmeraren eller av kompilatorn. Delningen kan också reduceras direkt till en serie skift-subtraheringar och skift-tillägg, men att minimera antalet sådana operationer som krävs är ett skrämmande problem; antalet monteringsanvisningar som resulterar kan vara mer än ett dussin, och överbelasta rörledningen. Om arkitekturen har hårdvara multiplicera funktionella enheter är multiplicera-för-invers sannolikt ett bättre tillvägagångssätt.

Vi kan tillåta tabellstorleken n att inte vara en effekt på 2 och fortfarande inte behöva utföra någon återstående eller divisionsoperation, eftersom dessa beräkningar ibland är dyra. Låt till exempel n vara betydligt mindre än 2 ^b . Överväga en pseudoslumptalsgenerator funktionen P (nyckel) som är enhetlig på intervallet [0, 2 ^b  - 1] . En hashfunktionsuniform på intervallet [0, n -1] är n P (nyckel)/2 ^b . Vi kan ersätta divisionen med ett (möjligen snabbare) höger bitskift : nP (nyckel) >> b .

Om nycklar hascheras upprepade gånger och hashfunktionen är dyr kan datortiden sparas genom att förkalkylera hashkoderna och lagra dem med nycklarna. Matchande hashkoder betyder nästan säkert att nycklarna är identiska. Denna teknik används för transponeringstabellen i spelprogram, som lagrar en 64-bitars hash-representation av styrelsens position.

Universalitet

Ett universellt hashschema är en randomiserad algoritm som väljer en hash -funktion h bland en familj av sådana funktioner, på ett sådant sätt att sannolikheten för en kollision mellan två olika nycklar är 1/ m , där m är antalet distinkta hashvärden önskad - oberoende av de två tangenterna. Universal hashing säkerställer (i en sannolikhet) att hashfunktionsprogrammet kommer att uppträda lika bra som om det skulle använda en slumpmässig funktion för varje distribution av ingångsdata. Det kommer dock att ha fler kollisioner än perfekt hasch och kan kräva fler operationer än en hash-funktion för speciella ändamål.

Tillämplighet

En hash -funktion är tillämplig i en mängd olika situationer. En hash -funktion som endast tillåter vissa bordstorlekar, strängar endast upp till en viss längd, eller som inte kan acceptera ett frö (dvs. tillåta dubbel hashning) är inte lika användbart som en som gör det.

Deterministisk

En hashprocedur måste vara deterministisk - vilket betyder att den för ett givet ingångsvärde alltid måste generera samma hashvärde. Med andra ord måste det vara en funktion av de data som ska hashas i termens matematiska mening. Detta krav utesluter hashfunktioner som är beroende av externa variabelparametrar, till exempel pseudo-slumpmässiga talgeneratorer eller tid på dagen. Det utesluter också funktioner som är beroende av minnesadressen för objektet som haschats i fall som adressen kan ändras under körningen (som kan hända på system som använder vissa metoder för insamling av sopor ), även om det ibland är möjligt att repetera objektet.

Determinismen är i samband med återanvändning av funktionen. Till exempel lägger Python till funktionen att hashfunktioner använder sig av ett randomiserat frö som genereras en gång när Python -processen startas utöver den ingång som ska hashas. Python -hash ( SipHash ) är fortfarande en giltig hash -funktion när den används inom en enda körning. Men om värdena kvarstår (till exempel skrivs till disk) kan de inte längre behandlas som giltiga hashvärden, eftersom det slumpmässiga värdet kan variera i nästa körning.

Definierat intervall

Det är ofta önskvärt att utsignalen från en hash -funktion har fast storlek (men se nedan). Om till exempel utmatningen är begränsad till 32-bitars heltalsvärden kan hashvärdena användas för att indexera till en array. Sådan hash används vanligtvis för att påskynda datasökningar. Att producera fast längdutmatning från ingång med variabel längd kan åstadkommas genom att bryta inmatningsdata i bitar av specifik storlek. Hashfunktioner som används för datasökningar använder något aritmetiskt uttryck som iterativt bearbetar bitar av ingången (t.ex. tecknen i en sträng) för att producera hashvärdet.

Variabelt intervall

I många applikationer kan intervallet för hashvärden vara olika för varje körning av programmet eller kan ändras längs samma körning (till exempel när en hashtabell måste utökas). I dessa situationer behöver man en hash -funktion som tar två parametrar - inmatningsdata z och antalet n tillåtna hashvärden.

En vanlig lösning är att beräkna en fast hash -funktion med ett mycket stort intervall (säg 0 till 2 ³²  - 1 ), dela resultatet med n och använda divisionens resterande . Om n i sig är en effekt på 2 kan detta göras genom bitmaskering och bitförskjutning . När detta tillvägagångssätt används måste hash -funktionen väljas så att resultatet har en ganska likformig fördelning mellan 0 och n  - 1 för varje värde av n som kan förekomma i applikationen. Beroende på funktionen kan resten vara enhetlig endast för vissa värden på n , t.ex. udda eller primtal .

Variabelt intervall med minimal rörelse (dynamisk hash -funktion)

När hashfunktionen används för att lagra värden i en hashtabell som överlever programmets körning och hashtabellen måste utökas eller krympa, kallas hashtabellen som en dynamisk hashtabell.

En hash -funktion som flyttar det minsta antalet poster när tabellen ändras är önskvärd. Det som behövs är en hash -funktion H ( z , n )  - där z är nyckeln som hashas och n är antalet tillåtna hashvärden - så att H ( z , n  + 1) = H ( z , n ) med sannolikhet nära n /( n  + 1) .

Linjär haschning och spirallagring är exempel på dynamiska hashfunktioner som utförs i konstant tid men slappnar av egenskapen till enhetlighet för att uppnå egenskapen med minimal rörelse. Utökningsbar hash använder en dynamisk hash -funktion som kräver utrymme proportionellt mot n för att beräkna hash -funktionen, och den blir en funktion av de tidigare nycklarna som har infogats. Flera algoritmer som bevarar enhetlighetsegenskapen men kräver tid som är proportionell mot n för att beräkna värdet av H ( z , n ) har uppfunnits.

En hash -funktion med minimal rörelse är särskilt användbar i distribuerade hashtabeller .

Data normalisering

I vissa applikationer kan ingångsdata innehålla funktioner som är irrelevanta för jämförelseändamål. När du till exempel letar upp ett personnamn kan det vara önskvärt att ignorera skillnaden mellan stora och små bokstäver. För sådana uppgifter, måste man använda en hash-funktion som är kompatibel med data likvärdighet kriteriet som används: det är, måste alla två ingångar som anses ekvivalenta ger samma hashvärde. Detta kan åstadkommas genom att normalisera ingången innan du hasherar den, som genom att alla bokstäver skrivs med stora bokstäver.

Hashing heltal datatyper

Det finns flera vanliga algoritmer för haschning av heltal. Metoden som ger den bästa distributionen är databeroende. En av de enklaste och vanligaste metoderna i praktiken är modulodelningsmetoden.

Identitetshash -funktion

Om data som ska hashas är tillräckligt liten kan man använda själva datan (omtolkad som ett heltal) som det hashade värdet. Kostnaden för att beräkna denna identitetshash -funktion är faktiskt noll. Denna hash -funktion är perfekt , eftersom den mappar varje ingång till ett distinkt hashvärde.

Betydelsen av "tillräckligt liten" beror på storleken på den typ som används som hashvärdet. Till exempel, i Java , är hashkoden ett 32-bitars heltal. Således kan 32-bitars heltal Integeroch 32-bitars floating-point- Floatobjekt helt enkelt använda värdet direkt; medan 64-bitars heltal Longoch 64-bitars flytande punkt Doubleinte kan använda denna metod.

Andra typer av data kan också använda detta haschingschema. Till exempel, vid mappning av teckensträngar mellan versaler och gemener , kan man använda den binära kodningen för varje tecken, tolkat som ett heltal, för att indexera en tabell som ger den alternativa formen för det tecknet ("A" för "a", " 8 "för" 8 ", etc.). Om varje tecken är lagrat i 8 bitar (som i utökad ASCII eller ISO Latin 1 ) har tabellen endast 2 ⁸ = 256 poster; i fallet med Unicode -tecken skulle tabellen ha 17 × 2 ¹⁶ =1 114 112 poster.

Samma teknik kan användas för att mappa landskoder med två bokstäver som "oss" eller "za" till landnamn (26 ² = 676 tabellposter), 5-siffriga postnummer som 13083 till stadsnamn (100 000 poster) etc. Ogiltiga datavärden (t.ex. landskoden "xx" eller postnummer 00000) kan lämnas odefinierade i tabellen eller mappas till ett lämpligt "null" -värde.

Trivial hash -funktion

Om nycklarna är enhetligt eller tillräckligt enhetligt fördelade över nyckelutrymmet, så att nyckelvärdena i huvudsak är slumpmässiga, kan de anses vara redan "hashade". I detta fall kan valfritt antal bitar i nyckeln ringas ut och sorteras som ett index i hashtabellen. En enkel hash -funktion skulle vara att maskera bort de nedre m -bitarna som ska användas som index till en tabell med storlek 2 ^m .

Hopfällbar

En vikande hashkod produceras genom att dela ingången i n sektioner av m bitar, där 2^m är tabellstorleken, och använda en paritetsbevarande bitvis operation som ADD eller XOR, för att kombinera sektionerna. Den sista operationen är en mask eller skift för att trimma bort överflödiga bitar i den höga eller låga änden. Till exempel, för en tabellstorlek på 15 bitar och nyckelvärdet för 0x0123456789ABCDEF, finns det fem sektioner 0x4DEF, 0x1357, 0x159E, 0x091A och 0x8. Om vi ​​lägger till får vi 0x7AA4, ett 15-bitars värde.

Mellanrutor

En hashkod för mitten av kvadraten produceras genom att kvadrera ingången och extrahera ett lämpligt antal mellansiffror eller bitar. Till exempel, om ingången är 123 456 789 och hashtabellstorleken 10 000, ger kvadrering av nyckeln 15 241 578 750 150 90 521, så hashkoden tas som de mellersta 4 siffrorna i det 17-siffriga numret (ignorerar den höga siffran) 8750. De mellersta rutorna metoden producerar en rimlig hashkod om det inte finns många inledande eller bakre nollor i nyckeln. Detta är en variant av multiplikativ hash, men inte lika bra eftersom en godtycklig nyckel inte är en bra multiplikator.

Division hashing

En standardteknik är att använda en modulofunktion på tangenten, genom att välja en divisor som är ett primtal nära tabellstorleken, så . Bordstorleken är vanligtvis en effekt på 2. Detta ger en fördelning från . Detta ger bra resultat över ett stort antal nyckeluppsättningar. En betydande nackdel med division hashing är att division är mikroprogrammerad på de flesta moderna arkitekturer inklusive x86 och kan vara 10 gånger långsammare än multiplicera. En andra nackdel är att det inte kommer att bryta upp grupperade nycklar. Till exempel mappar tangenterna 123000, 456000, 789000, etc. modulo 1000 alla till samma adress. Denna teknik fungerar bra i praktiken eftersom många nyckeluppsättningar redan är tillräckligt slumpmässiga och sannolikheten att en nyckelsats kommer att vara cyklisk med ett stort primtal är liten. ${\ displaystyle M}$${\ displaystyle h (K) = K \ mod M}$${\ displaystyle \ {0, M-1 \}}$

Algebraisk kodning

Algebraisk kodning är en variant av uppdelningsmetoden för haschning som använder division med ett polynom modulo 2 istället för ett heltal för att kartlägga n bitar till m bitar. I detta tillvägagångssätt, och vi postulerar en th grad polynom . En nyckel kan betraktas som polynomen . Återstoden med polynom aritmetisk modulo 2 är . Sedan . Om är konstruerad för att ha t eller färre koefficienter som inte är noll, kommer nycklar som delar mindre än t-bitar garanterat inte att kollidera. ${\ 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 en funktion av k, t och n, en divisor på 2 ^k -1, är konstruerad från GF (2 ^k ) -fältet. Knuth ger ett exempel: för n = 15, m = 10 och t = 7, . Avledningen är följande: ${\ displaystyle Z (x) = x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$

Låt vara den minsta uppsättningen heltal${\ displaystyle S}$${\ displaystyle \ ni \ {1,2, ..., t \} \ subseteq S \ land (2j) \ mod n \ i S \ förall j \ i S}$

Definiera var och var koefficienterna beräknas i detta fält. Sedan graden av . Eftersom är en rot till när som helst är en rot, följer det att koefficienterna för tillfredsställer så att de alla är 0 eller 1. Om är någon icke -noll polynom modul 2 med högst t icke -noll koefficienter, då är det inte en multipel av modul 2. Om följer att motsvarande hash -funktion kommer att kartlägga nycklar med färre än t -bitar gemensamt för unika index. ${\ displaystyle P (x) = \ prod _ {j \ i 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)}$

Det vanliga resultatet är att antingen n kommer att bli stort, eller så blir twill stort, eller båda, för att schemat ska vara beräknat. Därför är den mer lämpad för implementering av hårdvara eller mikrokod.

Unik permutation hashing

Se också unika permutation hashing, som har en garanterad bästa insättningstid i värsta fall.

Multiplikativ hashing

Standard multiplikativ hashing använder formeln som producerar ett hashvärde i . Värdet är ett lämpligt valt värde som bör vara relativt primärt till ; den ska vara stor och dess binära representation en slumpmässig blandning av 1: or och 0: or. En viktig praktisk specialfall uppstår när och är befogenheter 2 och är maskinen ordet storlek . I detta fall blir denna formel . Detta är speciellt eftersom aritmetisk modulo görs som standard på lågnivå programmeringsspråk och heltal division med en effekt på 2 är helt enkelt en högerskiftning, så i C, till exempel, blir denna funktion ${\ 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);
}

och för fast och detta översätts till en enda heltalsmultiplikation och högerskift vilket gör det till en av de snabbaste hashfunktionerna att beräkna. ${\ displaystyle m}$${\ displaystyle w}$

Multiplikativ hashning är mottaglig för ett "vanligt misstag" som leder till dålig diffusion-inmatningsbitar med högre värde påverkar inte utmatningsbitar med lägre värde. En transmutation på ingången som förskjuter spannet av kvarvarande toppbitar ner och XOR eller ADDar dem till nyckeln innan multiplikationssteget korrigerar för detta. Så den resulterande funktionen ser ut så här:

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

Fibonacci hashing

Fibonacci -hashning är en form av multiplikativ hashning där multiplikatorn är , var är maskinordets längd och (phi) det gyllene snittet . är ett irrationellt tal med ungefärligt värde 5/3 och decimalutvidgning på 1.618033 ... En egenskap hos denna multiplikator är att den enhetligt fördelar block av på varandra följande tangenter med avseende på block av bitar i nyckeln. På varandra följande nycklar inom nycklarnas höga eller låga bitar (eller något annat fält) är relativt vanliga. Multiplikatorerna för olika ordlängder är: ${\ 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 hashing

Tabuleringshashing, mer allmänt känt som Zobrist -hashning efter Albert Zobrist , en amerikansk datavetare, är en metod för att konstruera universella familjer av hashfunktioner genom att kombinera tabelluppslagning med XOR -operationer. Denna algoritm har visat sig vara mycket snabb och av hög kvalitet för hash-ändamål (särskilt hashning av heltalstangenter).

Zobrist hashing introducerades ursprungligen som ett sätt att kompakt representera schackpositioner i datorspelprogram. Ett unikt slumptal tilldelades för att representera varje typ av bit (sex vardera för svartvitt) på varje utrymme på brädet. Således initieras en tabell med 64x12 sådana nummer i början av programmet. Slumpmässiga tal kan vara vilken längd som helst, men 64 bitar var naturliga på grund av de 64 rutorna på brädet. En position transkriberades genom att cykla genom bitarna i en position, indexera motsvarande slumptal (lediga mellanslag inkluderades inte i beräkningen) och XORa dem tillsammans (startvärdet kan vara 0, identitetsvärdet för XOR eller en slumpmässig utsäde). Det resulterande värdet reducerades med modulo, vikning eller någon annan operation för att producera ett hashtabellindex. Den ursprungliga Zobrist -hashen lagrades i tabellen som representation av positionen.

Senare utvidgades metoden till haschning av heltal genom att representera varje byte i var och en av fyra möjliga positioner i ordet med ett unikt 32-bitars slumpmässigt tal. Således konstrueras en tabell med 2 ⁸ x4 med sådana slumpmässiga tal. Ett 32-bitars hasht heltal transkriberas genom att successivt indexera tabellen med värdet för varje byte i heltalet i vanlig text och XORa de laddade värdena tillsammans (igen kan startvärdet vara identitetsvärdet eller ett slumpmässigt utsäde). Den naturliga förlängningen till 64-bitars heltal är med hjälp av en tabell med 2 ⁸ x8 64-bitars slumptal.

Denna typ av funktion har några fina teoretiska egenskaper, varav en kallas 3-tuple-oberoende, vilket innebär att varje 3-tupel nycklar är lika sannolikt att mappas till alla 3-tupel hashvärden.

Anpassad hash -funktion

En hash -funktion kan utformas för att utnyttja befintlig entropi i nycklarna. Om nycklarna har inledande eller efterföljande nollor eller särskilda fält som är oanvända, alltid noll eller någon annan konstant, eller i allmänhet varierar lite, så kommer bara maskering av de flyktiga bitarna och haschning på dem att ge en bättre och möjligen snabbare hash -funktion. Utvalda delare eller multiplikatorer i divisions- och multiplikationsscheman kan göra mer enhetliga hashfunktioner om nycklarna är cykliska eller har andra redundans.

Hashning med variabel längd

När datavärdena är långa (eller variabel längd) teckensträngar- till exempel personnamn, webbsideadresser eller e-postmeddelanden-är deras fördelning vanligtvis mycket ojämn, med komplicerade beroenden. Till exempel har text på alla naturliga språk mycket ojämna fördelningar av tecken och teckenpar som är karakteristiska för språket. För sådana data är det klokt att använda en hash -funktion som är beroende av alla tecken i strängen - och beror på varje tecken på ett annat sätt.

Mitt och ändar

Enkla hashfunktioner kan lägga till de första och sista n- tecknen i en sträng tillsammans med längden, eller bilda en hash-storlek i ordstorlek från de fyra mellersta tecknen i en sträng. Detta sparar iterering över (potentiellt långa) strängen, men hashfunktioner som inte hashar på alla tecken i en sträng kan lätt bli linjära på grund av uppsägningar, kluster eller andra patologier i nyckelsatsen. Sådana strategier kan vara effektiva som en anpassad hash -funktion om nycklarnas struktur är sådan att antingen mitten, ändarna eller andra fält är noll eller någon annan invariant konstant som inte skiljer nycklarna; då kan de olika delarna av nycklarna ignoreras.

Karaktärsvikning

Det paradigmatiska exemplet på vikning efter tecken är att lägga till heltalsvärdena för alla tecken i strängen. En bättre idé är att multiplicera hash -totalen med en konstant, vanligtvis ett stort primtal, innan du lägger till nästa tecken, och ignorerar överflöd. Att använda exklusiv 'eller' istället för att lägga till är också ett troligt alternativ. Den sista operationen skulle vara en modulo, mask eller annan funktion för att reducera ordvärdet till ett index som är storleken på tabellen. Svagheten i detta förfarande är att information kan samlas i de övre eller nedre bitarna i byte, vilket kluster kommer att förbli i det hashade resultatet och orsaka fler kollisioner än en riktig randomiserande hash. ASCII-bytekoder har till exempel en övre bit på 0 och utskrivbara strängar använder inte de första 32 bytekoderna, så informationen (95-byte-koder) samlas i de återstående bitarna på ett otydligt sätt.

Det klassiska tillvägagångssättet kallade PJW -hash baserat på Peters arbete. J. Weinberger på ATT Bell Labs på 1970 -talet, var ursprungligen utformad för att hasha identifierare till kompilatorsymboltabeller som anges i "Dragon Book" . Denna hash -funktion kompenserar byte 4 bitar innan de läggs ihop. När kvantiteten lindas flyttas de höga 4 bitarna ut och om de inte är noll, XORed tillbaka till den låga byten för den kumulativa mängden. Resultatet är en hashkod av ordstorlek till vilken en modulo eller annan reducerande operation kan tillämpas för att producera det slutliga hashindexet.

Idag, särskilt med tillkomsten av 64-bitars ordstorlekar, finns mycket mer effektiv stränghashning med variabel längd med ordbitar tillgänglig.

Ordlängd vikning

Moderna mikroprocessorer kommer att möjliggöra mycket snabbare bearbetning om 8-bitars teckensträngar inte hascheras genom att bearbeta ett tecken i taget, utan genom att tolka strängen som en array med 32-bitars eller 64-bitars heltal och hascha/ackumulera dessa "breda ord" heltalsvärden med hjälp av aritmetiska operationer (t.ex. multiplikation med konstant och bitskiftning). Det sista ordet, som kan ha obebodda bytepositioner, fylls med nollor eller ett specifikt "randomiserande" värde innan det viks in i hash. Den ackumulerade hashkoden reduceras med en slutmodul eller annan operation för att ge ett index i tabellen.

Radix -konvertering hashing

Analogt med hur en ASCII- eller EBCDIC -teckensträng som representerar ett decimaltal konverteras till en numerisk kvantitet för beräkning, kan en sträng med variabel längd konverteras som ( x ₀ a ^{k −1} + x ₁ a ^{k −2} + ... + x _{k −2} a + x _{k −1} ) . Detta är helt enkelt en polynom i en radix utan noll a ! = 1 som tar komponenterna ( x ₀ , x ₁ , ..., x _{k −1} ) som tecknen i inmatningssträngen med längden k . Den kan användas direkt som hashkoden eller en hash -funktion som används för att mappa det potentiellt stora värdet till hashtabellstorleken. Värdet på a är vanligtvis ett primtal som är minst tillräckligt stort för att rymma antalet olika tecken i teckenuppsättningen med potentiella nycklar. Radix -omvandlingshashning av strängar minimerar antalet kollisioner. Tillgängliga datastorlekar kan begränsa den maximala längden på sträng som kan hashas med denna metod. Till exempel hashar ett 128-bitars dubbel långt ord endast en alfabetisk sträng med 26 tecken (ignorerar fall) med en radix på 29; en utskrivbar ASCII-sträng är begränsad till 9 tecken med radix 97 och ett 64-bitars långt ord. Emellertid är alfabetiska nycklar vanligtvis av blygsam längd, eftersom nycklar måste lagras i hashtabellen. Numeriska teckensträngar är vanligtvis inte ett problem; 64 bitar kan räkna upp till 10 ¹⁹ eller 19 decimaler med radix 10.

Rullande hash

I vissa applikationer, till exempel sökning efter delsträng , kan man beräkna en hash -funktion h för varje k -tecken delsträng i en given n -teckensträng genom att avancera ett fönster med k -tecken längs strängen; där k är ett fast heltal och n är större än k . Den enkla lösningen, som är att extrahera en sådan delsträng vid varje teckenposition i texten och beräkna h separat, kräver ett antal operationer proportionella mot k · n . Men med rätt val av h kan man använda tekniken för att rulla hash för att beräkna alla hashar med en ansträngning proportionell mot mk  +  n där m är antalet förekomster av delsträngen.

Den mest välkända algoritmen av denna typ är Rabin-Karp med bästa och genomsnittliga fallprestanda O ( n + mk ) och värsta fallet O ( n · k ) (i all rättvisa är det värsta fallet här allvarligt patologiskt: både textsträngen och delsträng består av ett upprepat enda tecken, såsom t = "AAAAAAAAAAA" och s = "AAA"). Hashfunktionen som används för algoritmen är vanligtvis Rabin-fingeravtrycket , utformat för att undvika kollisioner i 8-bitars teckensträngar, men andra lämpliga hash-funktioner används också.

Analys

Värsta fallet för en hash -funktion kan bedömas på två sätt: teoretiskt och praktiskt. Teoretiskt värsta fallet är sannolikheten att alla nycklar mappar till en enda plats. Praktiskt värsta fallet förväntas längsta probsekvens (hash -funktion + kollisionsupplösningsmetod). Denna analys betraktar enhetlig hash, det vill säga vilken nyckel som helst kommer att kartläggas till en viss plats med sannolikhet 1/ m , karakteristisk för universella hashfunktioner.

Medan Knuth oroar sig för kontradiktoriska attacker mot realtidssystem, har Gonnet visat att sannolikheten för ett sådant fall är "löjligt liten". Hans representation var att sannolikheten för att k av n -nycklar mappas till en enda plats är där α är lastfaktorn, n / m . ${\ displaystyle {\ frac {e ^{-\ alpha} \ alpha ^{k}} {k!}}}$

Historia

Termen "hash" erbjuder en naturlig analogi med dess icke-tekniska betydelse (att "hugga" eller "göra en röra" ur något), med tanke på hur hashfunktioner krypterar sina ingångsdata för att härleda sin produktion. I sin forskning om termens exakta ursprung noterar Donald Knuth att medan Hans Peter Luhn från IBM verkar ha varit den första som använde begreppet hash -funktion i ett memo daterat januari 1953, skulle själva termen bara visas i publicerade litteratur i slutet av 1960 -talet, om Herbert Hellermans principer för digitala datorsystem , även om det redan var utbredd jargong då.

Se även

Anteckningar

Referenser

externa länkar

• Beräkna hash av ett givet värde av Timo Denk
• Goulburn Hashing -funktionen ( PDF ) av Mayur Patel
• Hashfunktionskonstruktion för textuell och geometrisk datahämtning ( PDF ) Senaste trender på datorer, Vol.2, s. 483–489, CSCC Conference, Korfu, 2010