| PJW-32 ( hashpjw ) | |
|---|---|
| Oprettet | 1980'erne |
| offentliggjort | 1985 |
| Hash størrelse | 32 bit |
| Type | hash funktion |
PJW-32 ( hashpjw ) er en hashfunktion udviklet af Peter J. Weinberger fra AT&T Bell Laboratories .
For en vilkårlig input-meddelelse genererer funktionen en 32-bit hash-værdi kaldet message hash sum . Denne algoritme bruges i hashtabeller og kartesiske træer såvel som i procedurer til verificering af registreringsnøgler i softwarebeskyttelse. Denne funktion bruges i øjeblikket i Linux ELF -filformatet , den valgte standard for binære filer på Unix -lignende systemer.
Grundidéen til denne funktion blev udviklet af Peter J. Weinberger i 1980'erne, mens han arbejdede hos AT&T Bell Laboratories som en del af sin egen C-compiler. Da funktionen primært bruges i hash-tabeller , har den mange modifikationer, afhængigt af detaljerne i en bestemt tabel, operativsystem, hashed datastruktur osv.
Den første omtale af denne funktion findes i bogen af Alfred Aho, Ravi Seti og Jeffrey Ullman "Compilers. Principper, teknologier, værktøjer” i 1985. Den taler om den klare overlegenhed af denne funktion i forhold til andre, der bruges inden for organisering af søgninger ved at oprette hash-tabeller. Især gives en af modifikationerne til en tabel med 211 lister, samt sammenlignende karakteristika for denne modifikation.
Efterfølgende brugte mange forfattere ændringer af denne funktion. For eksempel indeholdt forfatteren Allen Holubs modifikation en fejl, der resulterede i en suboptimal hashværdi og dårligere samlede resultater. Men fejlen blev efterfølgende rettet i senere værker.
I øjeblikket er en af modifikationerne - ELFhash er meget udbredt, da den bruges i ELF-filformatet. Dette format blev først udgivet i versionen af unix System V-operativsystemet. Kort efter blev det taget i brug af mange producenter af unix-lignende systemer, og i 1999 blev det valgt som den binære filformatstandard for alle Unix- og Unix-lignende systemer på x86 platformen. .
I den originale version var algoritmen tilpasset til at arbejde med hash-tabeller , det vil sige i det indledende stadium var der en besked s af vilkårlig længde L, hvorfra det var nødvendigt at finde hash-værdien h. Inden udregning sættes værdien af h til 0. Beskeden læses tegn for tegn. Tallet m er den forventede størrelse af bordet.
Hvert tegn, der læses fra meddelelsen s, oversættes til et tal, og derefter overvejes dets bitværdi. Konvertering af et enkelt tegn til et heltal understøttes normalt af programmeringssprog. For eksempel giver Pascal ord-funktionen (eller direkte cast til byte) til dette, og C konverterer automatisk et tegn til et heltal, når der udføres aritmetiske operationer.
For den resulterende værdi c skal du flytte h med 4 positioner til venstre og summere den med S .
Der foretages en kontrol: hvis nogen af de 4 høje bits af h er 1, så flytter vi dem til højre med 24 positioner. Derefter udfører vi en eksklusiv eller operation på værdien af h og nulstiller værdierne af de 4 mest signifikante bits til 0.
Efter at have udført trin 1-2 med alle symboler i meddelelsen s, udføres division af h modulo m. Det resulterende tal er nummeret på listen i tabellen, som denne række skal føjes til.
Originaltekst usigneret int PJWHash ( char * str , int m ) { usigneret int hash = 0 ; unsigned int test = 0 ; for (; * str ; str ++ ) { hash = ( hash << 4 ) + ( usigned char )( * str ); if (( test = hash & 0xf0000000 ) != 0 ) { hash = (( hash ^ ( test >> 24 )) & ( 0xfffffff )); } } returner hash % m ; }Hovedanvendelsen af hashpjw-hash-funktionen og de fleste af dens modifikationer er hash-tabeller . Brugen af denne hash-funktion er fuldt ud berettiget,[ af hvem? ] trods den store tilstedeværelse af kollisioner. hashpjw er hurtig, fordi den kun udfører bitvise operationer, hvilket betyder, at der ikke udføres kompleks aritmetik.
| Hash funktioner | |
|---|---|
| generelle formål | |
| Kryptografisk | |
| Nøglegenereringsfunktioner | |
| Tjek nummer ( sammenligning ) | |
| Hashes |
|