1151:– Being an iterative hash based primarily on multiplication and XOR, the algorithm is sensitive to the number zero. Specifically, if the hash value were to become zero at any point during calculation, and the next byte hashed were also all zeroes, then the hash would not change. This makes colliding messages trivial to create given a message that results in a hash value of zero at some point in its calculation. Additional operations, such as the addition of a third constant prime on each step, can mitigate this but may have detrimental effects on
1161:– The ideal secure hash function is one in which each byte of input has an equally-complex effect on every bit of the hash. In the FNV hash, the ones place (the rightmost bit) is always the XOR of the rightmost bit of every input byte. This can be mitigated by XOR-folding (computing a hash twice the desired length, and then XORing the bits in the "upper half" with the bits in the "lower half").
716:
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
1145:– As a hash designed primarily for hashtable and checksum use, FNV-1 and FNV-1a were designed to be fast to compute. However, this same speed makes finding specific hash values (collisions) by brute force faster.
672:
52:
committee by Glenn Fowler and Phong Vo in 1991. In a subsequent ballot round, Landon Curt Noll improved on their algorithm. In an email message to Landon, they named it the
72:
for the desired bit length; however, the FNV webpage discusses methods of adapting one of the above versions to a smaller length that may or may not be a power of two.
1562:
774:
506:
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.
68:. FNV currently comes in 32-, 64-, 128-, 256-, 512-, and 1024-bit variants. For pure FNV implementations, this is determined solely by the availability of
1557:
521:
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
429:
The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode. The change in order leads to slightly better
1177:
38:
1339:
Eastlake, Donald; Hansen, Tony; Fowler, Glenn; Vo, Kiem-Phong; <unknown-email-Landon-Noll>, Landon Noll (June 4, 2020).
733:
The above FNV prime constraints and the definition of the FNV offset basis yield the following table of FNV hash parameters:
1135:
87:
346:
628:
103:
121:
One of FNV's key advantages is that it is very simple to implement. Start with an initial hash value of
1358:
314:
140:
it with the byte from the input. The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.
1297:
1232:
1280:
513:
except for the computing of the FNV offset basis for use as the FNV-1 and FNV-1a hash parameters.
1490:
1472:
110:
1214:
1196:
1134:. The authors have identified the following properties as making the algorithm unsuitable as a
1541:
1408:
522:
1451:
1384:
746:
1152:
540:
430:
99:
48:
The basis of the FNV hash algorithm was taken from an idea sent as reviewer comments to the
42:
17:
1508:
Eastlake, Donald; Hansen, Tony; Fowler, Glenn; Vo, Kiem-Phong; Noll, Landon (29 May 2019).
1261:
Eastlake, Donald; Hansen, Tony; Fowler, Glenn; Vo, Kiem-Phong; Noll, Landon (29 May 2019).
1370:
544:
1509:
1340:
1262:
503:
The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode.
1535:
1551:
1426:
694:
80:
64:
The current versions are FNV-1 and FNV-1a, which supply a means of creating non-zero
1171:
1131:
616:
564:
441:
The FNV-0 hash differs from the FNV-1 hash only by the initialisation value of the
818:
76:
1123:
548:
510:
343:
216:
212:
1310:
358:
The FNV-1a hash differs from the FNV-1 hash only by the order in which the
1127:
359:
306:
262:
219:
126:
277:
239:
95:
90:
previously used a modified version of the FNV scheme for its default
735:
526:
49:
722:
612:
489:
402:
363:
340:
329:
325:
321:
310:
299:
288:
273:
258:
246:
235:
227:
197:
137:
1233:"FNV Hash - Changing the FNV hash size - non-powers of 2"
291:
value: 14695981039346656037 (in hex, 0xcbf29ce484222325).
1311:"PEP 456 -- Secure and interchangeable hash algorithm"
94:
function. From Python 3.4, FNV has been replaced with
1215:"FNV Hash - Changing the FNV hash size - xor-folding"
749:
631:
1467:
1465:
768:
666:
547:. This is the only current practical use for the
1542:Internet draft by Fowler, Noll, Vo, and Eastlake
1491:"FNV Hash - Parameters of the FNV-1/FNV-1a hash"
8:
1334:
1332:
1330:
1328:
1326:
1324:
667:{\displaystyle 256^{t}+2^{8}+\mathrm {b} \,}
302:value 1099511628211 (in hex, 0x100000001b3).
1538:(with table of base & prime parameters)
1256:
1254:
1252:
1250:
1248:
1246:
1510:"The FNV Non-Cryptographic Hash Algorithm"
1341:"The FNV Non-Cryptographic Hash Algorithm"
1263:"The FNV Non-Cryptographic Hash Algorithm"
708:mod (2 − 2 − 1) > 2 + 2 + 7
75:The FNV hash algorithms and reference FNV
760:
748:
663:
658:
649:
636:
630:
328:operation that modifies only the lower 8-
1473:"FNV Hash - A few remarks on FNV primes"
944:0xdd268dbcaac550362d98c384c4e576ccc8b153
927:092796014241193945225284501741471925557
885:144066263297769815596495629667062367629
148:The FNV-1 hash algorithm is as follows:
1563:Public-domain software with source code
1446:
1444:
1442:
1440:
1409:"FNV Hash - FNV-1a alternate algorithm"
1188:
984:293219771643844981305189220653980578449
982:041874567263789610837432943446265799458
980:965930312949666949800943540071631046609
925:100029257958052580907070968620625704837
1366:
1356:
1155:or random distribution of hash values.
1065:61610267868082893823963790439336411086
1063:71501574036444603635505054127112859663
1061:75596980407732015769245856300321530495
1059:65628174669108571814760471015076148029
1057:22967323037177221508640965212023555493
1055:88062279544193396087847491461758272325
1053:14197795064947621068722070641403218320
986:5328239340083876191928701583869517785
534:chongo <Landon Curt Noll> /\../\
1385:"FNV Hash - The core of the FNV hash"
7:
1544:(IETF Informational Internet Draft)
1122:The FNV hash was designed for fast
1096:0x0000000000000000 005f7a76758ecc4d
1077:0x0000000000000000 0000000000000000
1007:0xb86db0b1171f4416 dca1e50f309990ac
996:0x0000000000000000 0000000000000000
896:0x6c62272e07bb014262b821756295c58d
893:0x0000000001000000000000000000013b
1110:6bde8cc9c6a93b21 aff4b16c71ee90b3
1091:0000000000000000 000000000000018d
1013:182036415f56e34b ac982aac4afe9fd9
1002:0000000000000000 0000000000000157
937:0x00000000000000000000010000000000
659:
25:
1558:Hash function (non-cryptographic)
1536:Landon Curt Noll's webpage on FNV
1108:eb6e73802734510a 555f256cc005ae55
1106:0000000000000000 000000000004c6d7
1104:0000000000000000 0000000000000000
1102:0000000000000000 0000000000000000
1100:6c3bf34eda3674da 9a21d90000000000
1098:32e56d5a591028b7 4b29fc4223fdada1
1089:0000000000000000 0000000000000000
1087:0000000000000000 0000000000000000
1085:0000000000000000 0000000000000000
1083:0000000000000000 0000000000000000
1081:0000000000000000 0000010000000000
1079:0000000000000000 0000000000000000
1011:e948f68a34c192f6 2ea79bc942dbe7ce
1009:ac87d059c9000000 0000000000000d21
1000:0000000000000000 0000000000000000
998:0000000001000000 0000000000000000
939:00000000000000000000000000000163
1178:Non-cryptographic hash functions
230:as the FNV hash. The variable,
1452:"FNV Hash - FNV-0 Historic not"
245:As an example, consider the 64-
125:. For each byte in the input,
39:non-cryptographic hash function
27:Non-cryptographic hash function
1298:FNV put into the public domain
1046:180409427187316048473796672026
1044:938529229181652437508374669137
1042:222029538271616265187852689524
1040:752383111205510814745150915769
1038:527895503076534540479074430301
1036:501645651011311865543459881103
693:the number of one-bits in the
567:and is determined as follows:
1:
1197:"FNV Hash - FNV hash history"
1174:(application for fast hashes)
222:. All variables, except for
882:309485009821345068724781371
79:have been released into the
18:Fowler-Noll-Vo hash function
1136:cryptographic hash function
973:583998256154206699388825751
971:890951084499463279557543925
969:358359158748448673689190764
946:6847b6bbb31023b4c8caee0535
918:374144419156711147060143317
88:Python programming language
1579:
1048:0389217684476157468082573
615:FNV prime is the smallest
253:All variables, except for
226:, have the same number of
1018:
951:
920:175368453031918731002211
900:
865:
830:
793:
509:Use of the FNV-0 hash is
431:avalanche characteristics
104:denial-of-service attacks
41:created by Glenn Fowler,
1427:"avalanche - murmurhash"
975:26094039892345713852759
1281:"FNV Hash - FNV source"
769:{\displaystyle n=2^{s}}
437:FNV-0 hash (deprecated)
339:value returned is a 64-
1118:Non-cryptographic hash
1067:884584107735010676915
770:
668:
850:14695981039346656037
771:
701:is either 4 or 5, and
669:
309:returns the lower 64
45:, and Kiem-Phong Vo.
1143:Speed of computation
747:
629:
622:that is of the form
570:For a given integer
215:, all variables are
861:0xcbf29ce484222325
858:0x00000100000001b3
738:
729:FNV hash parameters
1369:has generic name (
766:
736:
697:representation of
664:
525:when expressed in
332:of the hash value.
111:cryptographic hash
50:IEEE POSIX P1003.2
1115:
1114:
16:(Redirected from
1570:
1524:
1523:
1521:
1520:
1505:
1499:
1498:
1487:
1481:
1480:
1469:
1460:
1459:
1448:
1435:
1434:
1431:sites.google.com
1423:
1417:
1416:
1405:
1399:
1398:
1396:
1395:
1381:
1375:
1374:
1368:
1364:
1362:
1354:
1352:
1351:
1336:
1319:
1318:
1307:
1301:
1295:
1289:
1288:
1277:
1271:
1270:
1258:
1241:
1240:
1229:
1223:
1222:
1211:
1205:
1204:
1193:
1153:avalanche effect
788:FNV offset basis
775:
773:
772:
767:
765:
764:
739:
737:FNV parameters
720:
709:
700:
689:
673:
671:
670:
665:
662:
654:
653:
641:
640:
621:
610:
606:
605:
597:
588:
581:
573:
541:Landon Curt Noll
517:FNV offset basis
382:FNV_offset_basis
285:FNV_offset_basis
164:FNV_offset_basis
123:FNV offset basis
93:
66:FNV offset basis
43:Landon Curt Noll
21:
1578:
1577:
1573:
1572:
1571:
1569:
1568:
1567:
1548:
1547:
1532:
1527:
1518:
1516:
1507:
1506:
1502:
1489:
1488:
1484:
1471:
1470:
1463:
1450:
1449:
1438:
1425:
1424:
1420:
1407:
1406:
1402:
1393:
1391:
1383:
1382:
1378:
1365:
1355:
1349:
1347:
1338:
1337:
1322:
1309:
1308:
1304:
1296:
1292:
1279:
1278:
1274:
1260:
1259:
1244:
1231:
1230:
1226:
1213:
1212:
1208:
1195:
1194:
1190:
1186:
1168:
1120:
1109:
1107:
1105:
1103:
1101:
1099:
1097:
1090:
1088:
1086:
1084:
1082:
1080:
1078:
1066:
1064:
1062:
1060:
1058:
1056:
1054:
1047:
1045:
1043:
1041:
1039:
1037:
1022:Representation
1012:
1010:
1008:
1001:
999:
997:
985:
983:
981:
974:
972:
970:
955:Representation
945:
938:
926:
919:
904:Representation
869:Representation
779:Representation
756:
745:
744:
731:
718:
704:
698:
683:
645:
632:
627:
626:
619:
608:
603:
595:
590:
583:
575:
571:
557:
545:signature lines
539:This is one of
535:
519:
501:
458: := 0
439:
427:
356:
209:
146:
119:
91:
62:
28:
23:
22:
15:
12:
11:
5:
1576:
1574:
1566:
1565:
1560:
1550:
1549:
1546:
1545:
1539:
1531:
1530:External links
1528:
1526:
1525:
1514:tools.ietf.org
1500:
1482:
1461:
1436:
1418:
1400:
1376:
1345:tools.ietf.org
1320:
1302:
1290:
1272:
1267:tools.ietf.org
1242:
1224:
1206:
1187:
1185:
1182:
1181:
1180:
1175:
1167:
1164:
1163:
1162:
1156:
1146:
1119:
1116:
1113:
1112:
1093:
1074:
1070:
1069:
1050:
1033:
1029:
1028:
1026:
1023:
1020:
1016:
1015:
1004:
993:
989:
988:
977:
966:
962:
961:
959:
956:
953:
949:
948:
941:
934:
930:
929:
922:
915:
911:
910:
908:
905:
902:
898:
897:
894:
891:
887:
886:
883:
880:
876:
875:
873:
870:
867:
863:
862:
859:
856:
852:
851:
848:
847:1099511628211
845:
841:
840:
838:
835:
832:
828:
827:
824:
821:
815:
814:
811:
808:
804:
803:
801:
798:
795:
791:
790:
785:
780:
777:
763:
759:
755:
752:
730:
727:
714:
713:
712:
711:
702:
691:
675:
674:
661:
657:
652:
648:
644:
639:
635:
556:
553:
537:
536:
533:
518:
515:
447:
438:
435:
368:
366:is performed:
355:
352:
351:
350:
333:
318:
303:
292:
281:
268:The variable,
266:
150:
145:
142:
118:
115:
61:
58:
54:Fowler/Noll/Vo
31:Fowler–Noll–Vo
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1575:
1564:
1561:
1559:
1556:
1555:
1553:
1543:
1540:
1537:
1534:
1533:
1529:
1515:
1511:
1504:
1501:
1496:
1495:www.isthe.com
1492:
1486:
1483:
1478:
1477:www.isthe.com
1474:
1468:
1466:
1462:
1457:
1456:www.isthe.com
1453:
1447:
1445:
1443:
1441:
1437:
1432:
1428:
1422:
1419:
1414:
1413:www.isthe.com
1410:
1404:
1401:
1390:
1389:www.isthe.com
1386:
1380:
1377:
1372:
1360:
1346:
1342:
1335:
1333:
1331:
1329:
1327:
1325:
1321:
1316:
1312:
1306:
1303:
1299:
1294:
1291:
1286:
1285:www.isthe.com
1282:
1276:
1273:
1268:
1264:
1257:
1255:
1253:
1251:
1249:
1247:
1243:
1238:
1237:www.isthe.com
1234:
1228:
1225:
1220:
1219:www.isthe.com
1216:
1210:
1207:
1202:
1201:www.isthe.com
1198:
1192:
1189:
1183:
1179:
1176:
1173:
1170:
1169:
1165:
1160:
1157:
1154:
1150:
1147:
1144:
1141:
1140:
1139:
1137:
1133:
1129:
1125:
1117:
1111:
1094:
1092:
1075:
1072:
1071:
1068:
1051:
1049:
1034:
1031:
1030:
1027:
1025:2 + 2 + 0x8d
1024:
1021:
1017:
1014:
1005:
1003:
994:
991:
990:
987:
978:
976:
967:
964:
963:
960:
958:2 + 2 + 0x57
957:
954:
950:
947:
942:
940:
935:
932:
931:
928:
923:
921:
916:
913:
912:
909:
907:2 + 2 + 0x63
906:
903:
899:
895:
892:
889:
888:
884:
881:
878:
877:
874:
872:2 + 2 + 0x3b
871:
868:
864:
860:
857:
854:
853:
849:
846:
843:
842:
839:
837:2 + 2 + 0xb3
836:
833:
829:
825:
822:
820:
817:
816:
812:
809:
806:
805:
802:
800:2 + 2 + 0x93
799:
796:
792:
789:
786:
784:
781:
778:
776:
761:
757:
753:
750:
742:Size in bits
741:
740:
734:
728:
726:
724:
707:
703:
696:
692:
687:
682:
681:
680:
679:
678:
655:
650:
646:
642:
637:
633:
625:
624:
623:
618:
614:
601:
593:
586:
579:
568:
566:
562:
554:
552:
550:
546:
542:
532:
531:
530:
528:
524:
516:
514:
512:
507:
504:
500:
497:
494:
491:
488:
484:
481:
480:
475:
471:
468:
465:to be hashed
464:
461:
457:
454:
450:
446:
444:
436:
434:
432:
426:
423:
420:
419:
414:
410:
407:
404:
401:
397:
394:
391:to be hashed
390:
387:
384:
383:
378:
375:
371:
367:
365:
361:
353:
348:
345:
342:
338:
334:
331:
327:
323:
319:
316:
312:
308:
304:
301:
297:
293:
290:
286:
282:
279:
275:
271:
267:
264:
260:
256:
252:
251:
250:
248:
243:
241:
237:
233:
229:
225:
221:
218:
214:
211:In the above
208:
205:
202:
199:
196:
192:
189:
188:
183:
179:
176:
173:to be hashed
172:
169:
166:
165:
160:
157:
153:
149:
143:
141:
139:
135:
131:
128:
124:
116:
114:
112:
109:FNV is not a
107:
105:
101:
100:hash flooding
97:
89:
84:
82:
81:public domain
78:
73:
71:
67:
59:
57:
56:or FNV hash.
55:
51:
46:
44:
40:
36:
32:
19:
1517:. Retrieved
1513:
1503:
1494:
1485:
1476:
1455:
1430:
1421:
1412:
1403:
1392:. Retrieved
1388:
1379:
1367:|last5=
1359:cite journal
1348:. Retrieved
1344:
1314:
1305:
1300:on isthe.com
1293:
1284:
1275:
1266:
1236:
1227:
1218:
1209:
1200:
1191:
1172:Bloom filter
1158:
1149:Sticky state
1148:
1142:
1132:cryptography
1121:
1095:
1076:
1073:Hexadecimal
1052:
1035:
1006:
995:
992:Hexadecimal
979:
968:
943:
936:
933:Hexadecimal
924:
917:
890:Hexadecimal
855:Hexadecimal
787:
782:
743:
732:
725:hash space.
715:
705:
685:
676:
617:prime number
599:
591:
584:
577:
569:
565:prime number
560:
558:
538:
520:
508:
505:
502:
498:
495:
493:byte_of_data
492:
486:
482:
478:
477:
473:
469:
466:
463:byte_of_data
462:
459:
455:
452:
448:
442:
440:
428:
424:
421:
417:
416:
412:
408:
406:byte_of_data
405:
399:
395:
392:
389:byte_of_data
388:
385:
381:
380:
376:
373:
369:
357:
336:
295:
284:
270:byte_of_data
269:
255:byte_of_data
254:
249:FNV-1 hash:
244:
232:byte_of_data
231:
224:byte_of_data
223:
210:
206:
203:
201:byte_of_data
200:
194:
190:
186:
185:
181:
177:
174:
171:byte_of_data
170:
167:
163:
162:
158:
155:
151:
147:
133:
129:
122:
120:
108:
85:
74:
69:
65:
63:
53:
47:
34:
30:
29:
834:Expression
826:0x811c9dc5
823:0x01000193
819:Hexadecimal
813:2166136261
797:Expression
677:such that:
607:; then the
354:FNV-1a hash
98:to resist "
77:source code
1552:Categories
1519:2021-01-12
1394:2020-06-04
1350:2020-06-04
1315:Python.org
1184:References
1124:hash table
574:such that
549:deprecated
511:deprecated
445:variable:
298:is the 64-
287:is the 64-
272:, is an 8-
234:, is an 8-
213:pseudocode
144:FNV-1 hash
70:FNV primes
1159:Diffusion
1130:use, not
810:16777619
783:FNV prime
561:FNV prime
555:FNV prime
485: :=
479:FNV_prime
472: :=
449:algorithm
418:FNV_prime
411: :=
398: :=
379: :=
370:algorithm
296:FNV_prime
276:unsigned
261:unsigned
257:, are 64-
238:unsigned
193: :=
187:FNV_prime
180: :=
161: :=
152:algorithm
134:FNV prime
1166:See also
1128:checksum
1032:Decimal
965:Decimal
914:Decimal
879:Decimal
844:Decimal
807:Decimal
460:for each
386:for each
360:multiply
344:unsigned
324:is an 8-
307:multiply
263:integers
220:integers
217:unsigned
168:for each
127:multiply
117:The hash
60:Overview
684:0 <
580:< 11
576:4 <
551:FNV-0.
372:fnv-1a
347:integer
315:product
313:of the
278:integer
240:integer
136:, then
132:by the
96:SipHash
37:) is a
695:binary
688:< 2
602:) / 12
582:, let
523:octets
496:return
451:fnv-0
422:return
204:return
154:fnv-1
1019:1024
598:(5 +
563:is a
527:ASCII
1371:help
1126:and
952:512
901:256
866:128
589:and
499:hash
487:hash
483:hash
474:hash
470:hash
456:hash
443:hash
425:hash
413:hash
409:hash
400:hash
396:hash
377:hash
362:and
337:hash
335:The
330:bits
320:The
311:bits
305:The
294:The
283:The
228:bits
207:hash
195:hash
191:hash
182:hash
178:hash
159:hash
130:hash
92:hash
86:The
33:(or
831:64
794:32
723:bit
634:256
613:bit
587:= 2
559:An
543:'s
490:XOR
403:XOR
364:XOR
341:bit
326:bit
322:XOR
300:bit
289:bit
274:bit
259:bit
247:bit
236:bit
198:XOR
138:XOR
35:FNV
1554::
1512:.
1493:.
1475:.
1464:^
1454:.
1439:^
1429:.
1411:.
1387:.
1363::
1361:}}
1357:{{
1343:.
1323:^
1313:.
1283:.
1265:.
1245:^
1235:.
1217:.
1199:.
1138::
594:=
529::
476:×
467:do
453:is
433:.
415:×
393:do
374:is
242:.
184:×
175:do
156:is
113:.
106:.
102:"
83:.
1522:.
1497:.
1479:.
1458:.
1433:.
1415:.
1397:.
1373:)
1353:.
1317:.
1287:.
1269:.
1239:.
1221:.
1203:.
762:s
758:2
754:=
751:n
721:-
719:n
710:.
706:p
699:b
690:,
686:b
660:b
656:+
651:8
647:2
643:+
638:t
620:p
611:-
609:n
604:⌋
600:n
596:⌊
592:t
585:n
578:s
572:s
349:.
317:.
280:.
265:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.