Content deleted Content added
Updating broken link |
→Variants: logical order |
||
(34 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Computer function}}
{{Use dmy dates|date=January 2021}}
'''MurmurHash''' is a [[non-
</ref><ref>
[http://materias.fi.uba.ar/7500/chouza-tesisingenieriainformatica.pdf Chouza et al].
</ref><ref>
{{cite web|url=http://www.inesc-id.pt/ficheiros/publicacoes/5453.pdf |title=Couceiro et al.
|page= 14
}}
Line 14 ⟶ 16:
==Variants==
===
The original MurmurHash was created as an attempt to make a faster function than [[Jenkins hash function#lookup3|Lookup3]].<ref>{{cite web |title=MurmurHash1 |url=https://github.com/aappleby/smhasher/wiki/MurmurHash1 |accessdate=12 January 2019}}</ref> Although successful, it hadn't been tested thoroughly and wasn't capable of providing 64-bit hashes as in Lookup3. It had a rather elegant design, that would be later built upon in MurmurHash2, combining a multiplicative hash (similar to [[Fowler–Noll–Vo hash function]]) with a [[Xorshift]].▼
The current version is MurmurHash3,<ref>{{cite web|title=MurmurHash3 on Github|url=https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp}}</ref><ref name="Horvath">{{cite web | first = Adam | last = Horvath | url = http://blog.teamleadnet.com/2012/08/murmurhash3-ultra-fast-hash-algorithm.html | title = MurMurHash3, an ultra fast hash algorithm for C# / .NET | date = 10 August 2012 }}</ref> which yields a 32-bit or 128-bit hash value. When using 128-bits, the x86 and x64 versions do not produce the same values, as the algorithms are optimized for their respective platforms. MurmurHash3 was released alongside SMHasher—a hash function test suite.▼
===MurmurHash2===
Line 28 ⟶ 30:
* MurmurHash64B (64-bit, x86) - A 64-bit version optimized for 32-bit platforms. It is not a true 64-bit hash due to insufficient mixing of the stripes.<ref>{{cite web |title=MurmurHash3 (see note on MurmurHash2_x86_64) |url=https://github.com/aappleby/smhasher/wiki/MurmurHash3#bulk-speed-test-hashing-an-8-byte-aligned-256k-block |accessdate=15 January 2019}}</ref>
The person who originally found the flaw{{what|date=July 2021}} in MurmurHash2 created an unofficial 160-bit version of MurmurHash2 called MurmurHash2_160.<ref>{{cite web |title=MurmurHash2_160 |url=https://simonhf.wordpress.com/2010/09/25/murmurhash160/ |accessdate=12 January 2019}}</ref>
===
▲The current version is MurmurHash3,<ref>{{cite web|title=MurmurHash3 on Github|url=https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp}}</ref><ref name="Horvath">{{cite web | first = Adam | last = Horvath | url = http://blog.teamleadnet.com/2012/08/murmurhash3-ultra-fast-hash-algorithm.html | title = MurMurHash3, an ultra fast hash algorithm for C# / .NET | date = 10 August 2012 }}</ref> which yields a 32-bit or 128-bit hash value. When using 128-bits, the x86 and x64 versions do not produce the same values, as the algorithms are optimized for their respective platforms. MurmurHash3 was released alongside SMHasher—a hash function test suite.
▲The original MurmurHash was created as an attempt to make a faster function than [[Jenkins hash function#lookup3|Lookup3]].<ref>{{cite web |title=MurmurHash1 |url=https://github.com/aappleby/smhasher/wiki/MurmurHash1 |accessdate=12 January 2019}}</ref> Although successful, it hadn't been tested thoroughly and wasn't capable of providing 64-bit hashes as in Lookup3. It had a rather elegant design, that would be later built upon in MurmurHash2, combining a multiplicative hash (similar to [[Fowler–Noll–Vo hash function]]) with a [[Xorshift]].
==Implementations==
The canonical implementation is in [[C++]], but there are efficient ports for a variety of popular languages, including [[Python (programming language)|Python]],<ref>{{cite web|url=https://code.google.com/p/pyfasthash/ |title=pyfasthash in Python
It has been adopted into a number of open-source projects, most notably [[libstdc++]] (ver 4.6), [[nginx]] (ver 1.0.1),<ref>{{cite web|url=http://nginx.org/en/CHANGES |title=nginx |accessdate=13 January 2012}}</ref> [[Rubinius]],<ref>{{cite web|url=https://github.com/rubinius/rubinius/commit/1d69526c484cc9435a7198e41b8995db6c3acf1a |title=Rubinius |accessdate=29 February 2012}}</ref> libmemcached (the [[C (programming language)|C]] driver for [[Memcached]]),<ref>{{cite web|url=http://libmemcached.org/libMemcached.html|title=libMemcached|work=libmemcached.org|accessdate=21 October 2015}}</ref> [[Npm (software)|npm]] (nodejs package manager),<ref>{{cite web|url=https://github.com/npm/write-file-atomic/commit/22dd8759076fc8d0327d50693283060e479afafc |title=switch from MD5 to murmur}}</ref> [[maatkit]],<ref>{{cite web|url=https://code.google.com/p/maatkit/source/detail?r=3273 |title=maatkit
==Vulnerabilities==
Hash functions can be vulnerable to [[collision attack]]s,
==Algorithm==
Line 46 ⟶ 48:
''// In the case of overflow, the result is reduced modulo {{math|2<sup>32</sup>}}.''
'''input:''' ''key'', ''len'', ''seed''
c1 ← 0xcc9e2d51
c2 ← 0x1b873593
Line 53 ⟶ 55:
m ← 5
n ← 0xe6546b64
hash ← ''seed''
Line 76 ⟶ 78:
''// multiplication, and notably, that such high digits are likely to be discarded''
''// by the modulo arithmetic under overflow. We don't want that.''
remainingBytes ← remainingBytes × c1
remainingBytes ← remainingBytes ROL r1
Line 82 ⟶ 84:
hash ← hash XOR remainingBytes
hash ← hash XOR ''len''
Line 134 ⟶ 136:
}
</syntaxhighlight>
{| class="wikitable"
|+Tests
!Test string
!Seed value
!Hash value (hexadecimal)
!Hash value (decimal)
|-
|
|<code>0x00000000</code>
|<code>0x00000000</code>
|<code>0</code>
|-
|
|<code>0x00000001</code>
|<code>0x514E28B7</code>
|<code>1,364,076,727</code>
|-
|
|<code>0xffffffff</code>
|<code>0x81F16F39</code>
|<code>2,180,083,513</code>
|-
|test
|<code>0x00000000</code>
|<code>0xba6bd213</code>
|<code>3,127,628,307</code>
|-
|test
|<code>0x9747b28c</code>
|<code>0x704b81dc</code>
|<code>1,883,996,636</code>
|-
|Hello, world!
|<code>0x00000000</code>
|<code>0xc0363e43</code>
|<code>3,224,780,355</code>
|-
|Hello, world!
|<code>0x9747b28c</code>
|<code>0x24884CBA</code>
|<code>612,912,314</code>
|-
|The quick brown fox jumps over the lazy dog
|<code>0x00000000</code>
|<code>0x2e4ff723</code>
|<code>776,992,547</code>
|-
|The quick brown fox jumps over the lazy dog
|<code>0x9747b28c</code>
|<code>0x2FA826CD</code>
|<code>799,549,133</code>
|}
== See also ==
* [[Non-cryptographic hash functions]]
|