Editing Fowler–Noll–Vo hash function (section)

==The hash==

One of FNV's key advantages is that it is very simple to implement.<ref name="FNV_gps">
{{cite web
| first = James
| last = Smith
| work = Golang Project Structure
| title = Hash Functions in Go
| url = https://golangprojectstructure.com/hash-functions-go-code/#implementing-the-fowler%e2%80%93noll%e2%80%93vo-fnv-hash-function
| date = 2022-05-29
| access-date = 2024-10-19
}}
</ref>  Start with an initial hash value of ''FNV offset basis''.  For each byte in the input, [[multiply]] ''hash'' by the ''FNV prime'', then [[XOR]] it with the byte from the input.  The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.

===FNV-1 hash===

The FNV-1 hash algorithm is as follows:<ref name="FNV_basics">{{Cite journal|last1=Eastlake|first1=Donald|last2=Hansen|first2=Tony|last3=Fowler|first3=Glenn|last4=Vo|first4=Kiem-Phong|last5=<unknown-email-Landon-Noll>|first5=Landon Noll|date=June 4, 2020|title=The FNV Non-Cryptographic Hash Algorithm|url=https://tools.ietf.org/html/draft-eastlake-fnv-17.html|archive-url=|archive-date=|access-date=2020-06-04|website=tools.ietf.org|language=en}}</ref><ref>{{Cite web|title=FNV Hash - The core of the FNV hash|url=http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-1|access-date=2020-06-04|website=www.isthe.com}}</ref>

 '''algorithm''' fnv-1 '''is'''
     ''hash'' := '''''FNV_offset_basis'''''
 
     '''for each''' ''byte_of_data'' to be hashed '''do'''
         ''hash'' := ''hash'' × '''''FNV_prime'''''
         ''hash'' := ''hash'' [[XOR]] ''byte_of_data''
 
     '''return''' ''hash'' 

In the above [[pseudocode]], all variables are [[signedness|unsigned]] [[integers]].  All variables, except for ''byte_of_data'', have the same number of [[bit]]s as the FNV hash.  The variable, ''byte_of_data'', is an 8-[[bit]] unsigned [[integer]].

As an example, consider the 64-[[bit]] FNV-1 hash:

* All variables, except for ''byte_of_data'', are 64-[[bit]] unsigned [[integers]].
* The variable, ''byte_of_data'', is an 8-[[bit]] unsigned [[integer]].
* The ''FNV_offset_basis'' is the 64-[[bit]] value: 14695981039346656037 (in hex, 0xcbf29ce484222325).
* The ''FNV_prime'' is the 64-[[bit]] value 1099511628211 (in hex, 0x100000001b3).
* The [[multiply]] returns the lower 64 [[bit]]s of the [[Product (mathematics)|product]].
* The [[XOR]] is an 8-[[bit]] operation that modifies only the lower 8-[[bit]]s of the hash value.
* The ''hash'' value returned is a 64-[[bit]] [[Signedness|unsigned]] [[Integer (computer science)|integer]].

===FNV-1a hash===

The FNV-1a hash differs from the FNV-1 hash only by the order in which the [[multiply]] and [[XOR]] is performed:<ref name=FNV_basics /><ref>{{Cite web|url=http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-1a|title=FNV Hash - FNV-1a alternate algorithm|website=www.isthe.com}}</ref>

 '''algorithm''' fnv-1a '''is'''
     ''hash'' := '''''FNV_offset_basis'''''
 
     '''for each''' ''byte_of_data'' to be hashed '''do'''
         ''hash'' := ''hash'' [[XOR]] ''byte_of_data''
         ''hash'' := ''hash'' × '''''FNV_prime'''''
 
     '''return''' ''hash'' 
The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode.  The change in order leads to slightly better [[avalanche effect|avalanche characteristics]].<ref name=FNV_basics /><ref>{{Cite web|url=https://sites.google.com/site/murmurhash/avalanche|title=avalanche - murmurhash|website=sites.google.com}}</ref>

===FNV-0 hash (deprecated)===
The FNV-0 hash differs from the FNV-1 hash only by the initialisation value of the ''hash'' variable:<ref name= FNV_basics /><ref name=FNV0>{{Cite web|url=http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-0|title=FNV Hash - FNV-0 Historic not|website=www.isthe.com}}</ref>

 '''algorithm''' fnv-0 '''is'''
     ''hash'' := 0
 
     '''for each''' ''byte_of_data'' to be hashed '''do'''
         ''hash'' := ''hash'' × '''''FNV_prime'''''
         ''hash'' := ''hash'' [[XOR]] ''byte_of_data''
 
     '''return''' ''hash''

The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode.

A consequence of the initialisation of the hash to 0 is that empty messages and all messages consisting of only the byte 0, regardless of their length, hash to 0.<ref name=FNV0 />

Use of the FNV-0 hash is [[deprecated]] except for the computing of the FNV offset basis for use as the FNV-1 and FNV-1a hash parameters.<ref name= FNV_basics /><ref name=FNV0 />

===FNV offset basis===

There are several different FNV offset bases for various bit lengths.  These offset bases are computed by computing the FNV-0 from the following 32 [[octet (computing)|octet]]s when expressed in [[ASCII]]:
: <pre>chongo <Landon Curt Noll> /\../\</pre>
This is one of [[Landon Curt Noll]]'s [[Signature block|signature lines]].  This is the only current practical use for the [[deprecated]] FNV-0.<ref name= FNV_basics /><ref name=FNV0 />

===FNV prime===

An ''FNV prime'' is a [[prime number]] and is determined as follows:<ref name="FNV_prime"/><ref name=FNV_prime_remarks>{{Cite web|url=http://www.isthe.com/chongo/tech/comp/fnv/index.html#fnv-prime|title=FNV Hash - A few remarks on FNV primes|website=www.isthe.com}}</ref>

For a given integer {{Mvar|s}} such that {{Math|4 < ''s'' < 11}}, let {{Math|1=''n'' = 2<sup>''s''</sup>}} and {{Math|1=''t'' = {{floor|(5 + ''n'') / 12}}}}; then the {{Mvar|n}}-[[bit]] FNV prime is the smallest [[prime number]] {{Mvar|p}} that is of the form
:<math>256^t + 2^8 + \mathrm{b}\,</math>

such that:
:* {{Math|0 < ''b'' < 2<sup>8</sup>}},
:* the number of one-bits in the [[binary number|binary]] representation of {{Mvar|b}} is either 4 or 5, and
:* {{Math|''p'' mod (2<sup>40</sup> &minus; 2<sup>24</sup> &minus; 1) > 2<sup>24</sup> + 2<sup>8</sup> + 2<sup>7</sup>}}.

Experimentally, FNV primes matching the above constraints tend to have better dispersion properties. They improve the polynomial feedback characteristic when an FNV prime multiplies an intermediate hash value. As such, the hash values produced are more scattered throughout the {{Mvar|n}}-[[bit]] hash space.<ref name=FNV_prime /><ref name= FNV_prime_remarks />

===FNV hash parameters===

The above FNV prime constraints and the definition of the FNV offset basis yield the following table of FNV hash parameters:

{| border="1" class="wikitable" style="text-align: center;" align="center"
|+ FNV parameters <ref name="FNV_prime"/><ref>{{Cite web|url=http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param|title=FNV Hash - Parameters of the FNV-1/FNV-1a hash|website=www.isthe.com}}</ref>
! Size in bits
<math>n = 2^s</math>
! Representation
! '''FNV prime''' 
! '''FNV offset basis'''
|-
|-
! rowspan="3" | 32
! Expression
| 2<sup>24</sup> + 2<sup>8</sup> + 0x93
|
|-
! Decimal
|16777619
|2166136261
|-
! [[Hexadecimal]]
|0x01000193
|0x811c9dc5
|-
! rowspan="3" | 64
! Expression
|2<sup>40</sup> + 2<sup>8</sup> + 0xb3
|
|-
! Decimal
|1099511628211
|14695981039346656037
|-
! Hexadecimal
|0x00000100000001b3
|0xcbf29ce484222325
|-
! rowspan="3" | 128
! Representation
|2<sup>88</sup> + 2<sup>8</sup> + 0x3b
|
|-
! Decimal
|309485009821345068724781371
|144066263297769815596495629667062367629
|-
! Hexadecimal
|0x0000000001000000000000000000013b
|0x6c62272e07bb014262b821756295c58d
|-
! rowspan="3" | 256
! Representation
|2<sup>168</sup> + 2<sup>8</sup> + 0x63
|
|-
! Decimal
|
374144419156711147060143317<br>
175368453031918731002211
|
100029257958052580907070968620625704837<br>
092796014241193945225284501741471925557
|-
! Hexadecimal
|
0x00000000000000000000010000000000<br>
00000000000000000000000000000163
|
0xdd268dbcaac550362d98c384c4e576ccc8b153<br>
6847b6bbb31023b4c8caee0535
|-
! rowspan="3" | 512
! Representation
|2<sup>344</sup> + 2<sup>8</sup> + 0x57
|
|-
! Decimal
|
358359158748448673689190764<br>
890951084499463279557543925<br>
583998256154206699388825751<br>
26094039892345713852759
|
965930312949666949800943540071631046609<br>
041874567263789610837432943446265799458<br>
293219771643844981305189220653980578449<br>
5328239340083876191928701583869517785
|-
! Hexadecimal
|
0x0000000000000000 0000000000000000<br>
0000000001000000 0000000000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 0000000000000157
|
0xb86db0b1171f4416 dca1e50f309990ac<br>
ac87d059c9000000 0000000000000d21<br>
e948f68a34c192f6 2ea79bc942dbe7ce<br>
182036415f56e34b ac982aac4afe9fd9
|-
! rowspan="3" | 1024
! Representation
|2<sup>680</sup> + 2<sup>8</sup> + 0x8d
|
|-
! Decimal
|
501645651011311865543459881103<br>
527895503076534540479074430301<br>
752383111205510814745150915769<br>
222029538271616265187852689524<br>
938529229181652437508374669137<br>
180409427187316048473796672026<br>
0389217684476157468082573
|
14197795064947621068722070641403218320<br>
88062279544193396087847491461758272325<br>
22967323037177221508640965212023555493<br>
65628174669108571814760471015076148029<br>
75596980407732015769245856300321530495<br>
71501574036444603635505054127112859663<br>
61610267868082893823963790439336411086<br>
884584107735010676915
|-
! Hexadecimal
|
0x0000000000000000 0000000000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 0000010000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 000000000000018d
|
0x0000000000000000 005f7a76758ecc4d<br>
32e56d5a591028b7 4b29fc4223fdada1<br>
6c3bf34eda3674da 9a21d90000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 0000000000000000<br>
0000000000000000 000000000004c6d7<br>
eb6e73802734510a 555f256cc005ae55<br>
6bde8cc9c6a93b21 aff4b16c71ee90b3
|}