| PJW-32 ( hashpjw ) | |
|---|---|
| Skapad | 1980-talet |
| publiceras | 1985 |
| Hash storlek | 32 bitar |
| Sorts | hash-funktion |
PJW-32 ( hashpjw ) är en hashfunktion utvecklad av Peter J. Weinberger från AT&T Bell Laboratories .
För ett godtyckligt ingångsmeddelande genererar funktionen ett 32-bitars hashvärde som kallas meddelandehashsumman . Denna algoritm används i hashtabeller och kartesiska träd , såväl som i procedurer för att verifiera registreringsnycklar i programvaruskydd. Den här funktionen används för närvarande i Linux ELF -filformatet , den valda standarden för binära filer på Unix -liknande system.
Grundidén för den här funktionen utvecklades av Peter J. Weinberger på 1980-talet när han arbetade på AT&T Bell Laboratories som en del av sin egen C-kompilator. Eftersom funktionen främst används i hashtabeller har den många modifieringar, beroende på detaljerna i en viss tabell, operativsystem, hashad datastruktur, etc.
Det första omnämnandet av denna funktion finns i boken av Alfred Aho, Ravi Seti och Jeffrey Ullman "Compilers. Principer, teknologier, verktyg” 1985. Den talar om den här funktionens tydliga överlägsenhet jämfört med andra som används inom området för att organisera sökningar genom att skapa hashtabeller. I synnerhet ges en av ändringarna för en tabell med 211 listor, liksom jämförande egenskaper för denna modifiering.
Därefter använde många författare modifieringar av denna funktion. Till exempel innehöll författaren Allen Holubs modifiering en bugg som resulterade i ett suboptimalt hashvärde och sämre övergripande resultat. Men felet korrigerades sedan i senare arbeten.
För närvarande är en av ändringarna - ELFhash används ofta, eftersom det används i ELF-filformatet. Detta format publicerades först i versionen av operativsystemet unix System V. Strax efter antogs det av många tillverkare av unix-liknande system och valdes 1999 som den binära filformatstandarden för alla Unix- och Unix-liknande system på x86-plattformen. .
I den ursprungliga versionen var algoritmen anpassad för att fungera med hashtabeller , det vill säga i det inledande skedet fanns ett meddelande s med godtycklig längd L, från vilket det krävdes för att hitta hashvärdet h. Före beräkningen sätts värdet på h till 0. Meddelandet läses tecken för tecken. Siffran m är den förväntade storleken på tabellen.
Varje tecken som läses från meddelandet s översätts till ett tal, och sedan beaktas dess bitvärde. Att konvertera ett enstaka tecken till ett heltal stöds vanligtvis av programmeringsspråk. Till exempel tillhandahåller Pascal ord-funktionen (eller direkt cast till byte) för detta, och C konverterar automatiskt ett tecken till ett heltal när aritmetiska operationer utförs.
För det resulterande värdet c, flytta h med 4 positioner åt vänster och summera det med S .
En kontroll görs: om någon av de 4 höga bitarna i h är 1, flyttar vi dem till höger med 24 positioner. Sedan utför vi en exklusiv eller operation på värdet på h och återställer värdena för de 4 mest signifikanta bitarna till 0.
Efter att ha utfört steg 1-2 med alla symboler i meddelandet s, utförs uppdelning av h modulo m. Det resulterande numret är numret på listan i tabellen som denna rad ska läggas till.
Originaltext osignerad int PJWHash ( char * str , int m ) { osignerad int hash = 0 ; unsigned int test = 0 ; för (; * str ; str ++ ) { hash = ( hash << 4 ) + ( osignerad char )( * str ); if (( test = hash & 0xf0000000 ) != 0 ) { hash = (( hash ^ ( test >> 24 )) & ( 0xfffffff )); } } returnera hash % m ; }Den huvudsakliga användningen av hashpjw-hashfunktionen och de flesta av dess modifieringar är hashtabeller . Användningen av denna hash-funktion är fullt motiverad,[ av vem? ] trots den stora förekomsten av kollisioner. hashpjw är snabb eftersom den bara utför bitvisa operationer, vilket betyder att ingen komplex aritmetik utförs.
| Hash-funktioner | |
|---|---|
| generell mening | |
| Kryptografisk | |
| Nyckelgenereringsfunktioner | |
| Kontrollnummer ( jämförelse ) | |
| Hashes |
|