Non-cryptographic hash function

<h2 id="applications-and-requirements">Applications and requirements</h2>
Among the typical uses of non-cryptographic hash functions are <a href="/facts/Bloom_filter/Gq2WVE37">bloom filters</a>, <a href="/facts/Hash_table/Ht4ptDPF">hash tables</a>, and <a href="/facts/Count_sketch/aUcULP4Q">count sketches</a>. These applications require, in addition to speed, <a href="/facts/Discrete_uniform_distribution/M52SQP5n">uniform distribution</a> and <a href="/facts/Avalanche_effect/hpYX5zu5">avalanche</a> properties.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> <a href="/facts/Collision_resistance/8eBxsuHe">Collision resistance</a> is an additional feature that can be useful against <a href="/facts/Hash_flooding/6aXFAMbW">hash flooding</a> attacks; simple NCHFs, like the <a href="/facts/Cyclic_redundancy_check/u2exo4sv">cyclic redundancy check</a> (CRC), have essentially no collision resistance<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and thus cannot be used with an input open to manipulation by an attacker.
NCHFs are used in diverse systems: <a href="/facts/Lexical_analyzer/T1JYWpIf">lexical analyzers</a>, <a href="/facts/Compiler/WNfCDFJe">compilers</a>, <a href="/facts/Database/VYcpkevb">databases</a>, <a href="/facts/Communication_network/NFCX0STS">communication networks</a>, video games, <a href="/facts/DNS_server/pUgmBMNW">DNS servers</a>, <a href="/facts/Filesystem/FdPm90uc">filesystems</a>—anywhere in computing where there is a need to find the information very quickly (preferably in the <a href="/facts/O(1)/weFFjSWg">O(1)</a> time, which will also achieve perfect <a href="/facts/Scalability/jh7JomPa">scalability</a>).<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Estébanez et al. list the "most important" NCHFs:<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<ul><li>The <a href="/facts/Fowler%25E2%2580%2593Noll%25E2%2580%2593Vo_hash_function/C9VHCDmB">Fowler–Noll–Vo hash function</a> (FNV) was created by Glenn Fowler and Phong Vo in 1991 with contributions from <a href="/facts/Landon_Curt_Noll/QtmQklQ7">Landon Curt Noll</a>. FNV with its two variants, FNV-1 and FNV-1a, is very widely used in <a href="/facts/Linux/9FvCKSTq">Linux</a>, <a href="/facts/FreeBSD/RKsFTm7F">FreeBSD</a> OSes, DNS servers, <a href="/facts/Network_File_System/jWRRALVo">NFS</a>, <a href="/facts/Twitter/VWwDNGUm">Twitter</a>, <a href="/facts/PlayStation_2/gbFBT7AX">PlayStation 2</a>, and <a href="/facts/Xbox_(console)/2FuQrJeX">Xbox</a>, among others.</li>
<li><a href="/facts/Lookup3/AHcoV5hY">lookup3</a> was created by <a href="/facts/Robert_John_Jenkins_Jr./JYXeKVMH">Robert Jenkins</a>. This hash is also widely used and can be found in <a href="/facts/PostgreSQL/LHdXuHfl">PostgreSQL</a>, Linux, <a href="/facts/Perl/fx31kjlT">Perl</a>, <a href="/facts/Ruby_(programming_language)/BeYSaPSR">Ruby</a>, and <a href="/facts/Infoseek/URcvrdzN">Infoseek</a>.</li>
<li>SuperFastHash was created by Paul Hsieh using ideas from FNV and lookup3, with one of the goals being a high degree of avalanche effect. The hash is used in <a href="/facts/WebKit/YrP9vbIj">WebKit</a> (part of <a href="/facts/Safari_(browser)/9R8v7tNl">Safari</a> and <a href="/facts/Google_Chrome/4INfWq37">Google Chrome</a>).</li>
<li><a href="/facts/MurmurHash/87wWyb3F">MurmurHash</a>2 was created by Austin Appleby in 2008 and is used in <a href="/facts/Memcached/m43x4fRg">libmemcached</a>, Maatkit, and <a href="/facts/Apache_Hadoop/oUS1G2R7">Apache Hadoop</a>.</li>
<li>DJBX33A ("Daniel J. Bernstein, Times 33 with Addition"). This very simple multiplication-and-addition function was proposed by <a href="/facts/Daniel_J._Bernstein/KQLuMRTx">Daniel J. Bernstein</a>. It is fast and efficient during initialization. Many programming environments based on <a href="/facts/PHP_5/vU6YRJX0">PHP 5</a>, <a href="/facts/Python_(language)/YbuGqofa">Python</a>, and <a href="/facts/ASP.NET/xq7KM8mN">ASP.NET</a> use variants of this hash. The hash is easy to <a href="/facts/Hash_flooding/6aXFAMbW">flood</a>, exposing the servers.</li>
<li>BuzHash was created by Robert Uzgalis in 1992. It is designed around a substitution table and can tolerate extremely skewed distributions on the input.</li>
<li>DEK is an early multiplicative hash based on a proposal by <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> and is one of the oldest hashes that is still in use.</li></ul>
<h2 id="design">Design</h2>
Non-cryptographic hash functions optimized for software frequently involve the multiplication operation. Since in-hardware multiplication is resource-intensive and frequency-limiting, <a href="/facts/ASIC/YGUXpX50">ASIC</a>-friendlier designs had been proposed, including <a href="/facts/SipHash/snDLDp73">SipHash</a> (which has an additional benefit of being able to use a secret <a href="/facts/Key_(cryptography)/5W5PAmT4">key</a> for <a href="/facts/Message_authentication_code/mXxCP5Yl">message authentication</a>), NSGAhash, and XORhash. Although technically lightweight cryptography can be used for the same applications, the <a href="/facts/Latency_(engineering)/6Bjhn30H">latency</a> of its algorithms is usually too high due to a large number of <a href="/facts/Round_(cryptography)/GDSequUg">rounds</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Sateesan et al. propose using the <a href="/facts/Reduced-round/GDSequUg">reduced-round</a> versions of lightweight hashes and ciphers as non-cryptographic hash functions.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Many NCHFs have a relatively small result size (e.g., 64 bits for <a href="/facts/SipHash/snDLDp73">SipHash</a> or even less): large result size does not increase the performance of the target applications, but slows down the calculation, as more bits need to be generated.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="see-also">See also</h2>
<ul><li>A list of <a href="/facts/Non-cryptographic_hash_functions/fdTqDa9l">non-cryptographic hash functions</a></li></ul>

<h2 id="sources">Sources</h2>
<ul><li>Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). <a href="https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf">"Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware"</a> (PDF). Microprocessors and Microsystems. 98: 104782. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.micpro.2023.104782">10.1016/j.micpro.2023.104782</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0141-9331">0141-9331</a>.</li>
<li>Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 January 2013). <a href="https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf">"Performance of the most common non-cryptographic hash functions"</a> (PDF). Software: Practice and Experience. 44 (6): 681–698. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fspe.2179">10.1002/spe.2179</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0038-0644">0038-0644</a>.</li>
<li>Stamp, Mark (8 November 2011). <a href="https://books.google.com/books?id=UW3SS9P9hdEC&pg=PT118">"Non-Cryptographic Hashes"</a>. Information Security: Principles and Practice (2 ed.). John Wiley & Sons. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-118-02796-7. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/1039294381">1039294381</a>.</li>
<li>Patgiri, Ripon; Nayak, Sabuzima; Muppalaneni, Naresh Babu (25 April 2023). <a href="https://books.google.com/books?id=BIdGEAAAQBAJ&pg=PA38">Bloom Filter: A Data Structure for Computer Networking, Big Data, Cloud Computing, Internet of Things, Bioinformatics and Beyond</a>. Academic Press. pp. 37–38. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-12-823646-8. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/1377693258">1377693258</a>.</li>
<li>Mittelbach, Arno; Fischlin, Marc (2021). "Non-cryptographic Hashing". The Theory of Hash Functions and Random Oracles. Cham: Springer International Publishing. pp. 303–334. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-030-63287-8_7">10.1007/978-3-030-63287-8_7</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-030-63286-1.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Estébanez et al. 2013. - Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 January 2013). "Performance of the most common non-cryptographic hash functions" (PDF). Software: Practice and Experience. 44 (6): 681–698. doi:10.1002/spe.2179. ISSN 0038-0644. <a href="https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf" target="_blank">https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Sateesan et al. 2023, p. 1. - Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware" (PDF). Microprocessors and Microsystems. 98: 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331. <a href="https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf" target="_blank">https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Sateesan et al. 2023, p. 2. - Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware" (PDF). Microprocessors and Microsystems. 98: 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331. <a href="https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf" target="_blank">https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Mittelbach & Fischlin 2021, p. 303. - Mittelbach, Arno; Fischlin, Marc (2021). "Non-cryptographic Hashing". The Theory of Hash Functions and Random Oracles. Cham: Springer International Publishing. pp. 303–334. doi:10.1007/978-3-030-63287-8_7. ISBN 978-3-030-63286-1. <a href="https://doi.org/10.1007%2F978-3-030-63287-8_7" target="_blank">https://doi.org/10.1007%2F978-3-030-63287-8_7</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Sateesan et al. 2023, p. 2. - Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware" (PDF). Microprocessors and Microsystems. 98: 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331. <a href="https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf" target="_blank">https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Stamp 2011. - Stamp, Mark (8 November 2011). "Non-Cryptographic Hashes". Information Security: Principles and Practice (2 ed.). John Wiley & Sons. ISBN 978-1-118-02796-7. OCLC 1039294381. <a href="https://books.google.com/books?id=UW3SS9P9hdEC&pg=PT118" target="_blank">https://books.google.com/books?id=UW3SS9P9hdEC&pg=PT118</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Estébanez et al. 2013, p. 1. - Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 January 2013). "Performance of the most common non-cryptographic hash functions" (PDF). Software: Practice and Experience. 44 (6): 681–698. doi:10.1002/spe.2179. ISSN 0038-0644. <a href="https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf" target="_blank">https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Estébanez et al. 2013, pp. 3–4. - Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 January 2013). "Performance of the most common non-cryptographic hash functions" (PDF). Software: Practice and Experience. 44 (6): 681–698. doi:10.1002/spe.2179. ISSN 0038-0644. <a href="https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf" target="_blank">https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Sateesan et al. 2023, p. 2. - Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware" (PDF). Microprocessors and Microsystems. 98: 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331. <a href="https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf" target="_blank">https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Sateesan et al. 2023, p. 1. - Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware" (PDF). Microprocessors and Microsystems. 98: 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331. <a href="https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf" target="_blank">https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Patgiri, Nayak & Muppalaneni 2023, pp. 37–38. - Patgiri, Ripon; Nayak, Sabuzima; Muppalaneni, Naresh Babu (25 April 2023). Bloom Filter: A Data Structure for Computer Networking, Big Data, Cloud Computing, Internet of Things, Bioinformatics and Beyond. Academic Press. pp. 37–38. ISBN 978-0-12-823646-8. OCLC 1377693258. <a href="https://books.google.com/books?id=BIdGEAAAQBAJ&pg=PA38" target="_blank">https://books.google.com/books?id=BIdGEAAAQBAJ&pg=PA38</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Non-cryptographic hash function open-in-new

Non-cryptographic hash function