# Use of MurmurHash3 for hashing strings

**URL:** <https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818>\
**Category:** Internals & Design\
**Created:** [March 19, 2018, 4:39pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818 "2018-03-19T16:39:03Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 19, 2018, 4:39pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/1 "2018-03-19T16:39:03Z")

</div>

Julia uses the 128 bit MurmurHash3 algorithm for the `hash` function for `AbstractString`.

There are two serious issues with that:

1. It is not possible to build up a hash value for a string in chunks:

```julia
julia> hash("bar",hash("foo"))
0x6d0f1600f8bd5874

julia> hash("foobar")
0x54fc7dff7f029834

julia> using CRC32c

julia> crc32c("bar",crc32c("foo"))
0x0d5f5c7f

julia> crc32c("foobar")
0x0d5f5c7f

```

1. It is about twice as slow as using crc32c (at least, on my machine, but most platforms have crc accelerator instructions, such as used in crc32c).

2. CRC-32c seems to give very similar results as far as collisions as MurmurHash3 - so it seems like it would be an advantage to switch to using it, instead of MurmurHash3.

---

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [March 19, 2018, 8:04pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/2 "2018-03-19T20:04:49Z")

</div>

Good question, but AFAIK CRC32 there’s some controversy around the question of whether CRC32 is a good function for hash tables.

Have you considered Google’s CityHash? It’s relatively recent, designed for strings, and they claim it’s faster than MurmurHash while still of high quality:

> CityHash, a family of hash functions for strings. […]  
> We are most excited by the performance of CityHash64() and its variants on  
> short strings, but long strings are interesting as well.  
> CityHash is intended to be fast, under the constraint that it hash very  
> well. For CPUs with the CRC32 instruction, CRC is speedy, but CRC wasn’t  
> designed as a hash function and shouldn’t be used as one. CityHashCrc128()  
> is not a CRC, but it uses the CRC32 machinery.

> **[GitHub - google/cityhash: Automatically exported from code.google.com/p/cityhash](https://github.com/google/cityhash)**
>
> Automatically exported from code.google.com/p/cityhash - GitHub - google/cityhash: Automatically exported from code.google.com/p/cityhash

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 19, 2018, 8:19pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/3 "2018-03-19T20:19:23Z")

</div>

> [@nalimilan](#):
>
> Have you considered Google’s CityHash? It’s relatively recent, designed for strings, and they claim it’s faster

Apparently CityHash has been [superseded by FarmHash](https://www.infoq.com/news/2014/04/google_farmhash) at Google.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 19, 2018, 8:49pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/4 "2018-03-19T20:49:16Z")

</div>

> [@nalimilan](#):
>
> Good question, but AFAIK CRC32 there’s some controversy around the question of whether CRC32 is a good function for hash tables.

I’d been using CRC functions for hashing starting with CRC-16 back in the day, and compared with the alternatives _at that time_, it (and later using CRC-32) always performed quite well, compared to the alternatives generally in use back then.  
Could you point to some of the controversy about using CRC for a hash table? (I’ll try to dig some references up, if you can’t) I’d done a lot of testing with large varieties of strings (many many millions, of text and binary data), and had very few collisions, but I’m interested to learn what the criticisms are.

I’m also interested in [SipHash](https://131002.net/siphash/).

I have already ported the 64-bit implementation of the 128-bit MurmurHash3 to Julia (it seems to be identical in speed to the C version), because to improve the performance of hashing non-UTF8 encoded strings (while keeping them returning a UTF-8 compatible hash), I needed a Julia version so that I don’t have to convert the entire string first [hence the concern over being able to do the hashing in chunks]).

It will be in JuliaString/Strs.jl/src/murmurhash3.jl shortly.

---

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [March 19, 2018, 10:02pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/5 "2018-03-19T22:02:23Z")

</div>

> [@ScottPJones](#):
>
> Could you point to some of the controversy about using CRC for a hash table? (I’ll try to dig some references up, if you can’t) I’d done a lot of testing with large varieties of strings (many many millions, of text and binary data), and had very few collisions, but I’m interested to learn what the criticisms are.

Apart from what CityHash authors say above, there are (not really conclusive) discussions on StackOverflow: [this one](https://stackoverflow.com/questions/10953958/can-crc32-be-used-as-a-hash-function) and [this one](https://stackoverflow.com/questions/2694740/can-one-construct-a-good-hash-function-using-crc32c-as-a-base?rq=1) at least.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 19, 2018, 10:56pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/6 "2018-03-19T22:56:03Z")

</div>

Those discussions seemed to have as many people claiming that (for non-cryptographic uses) CRC32C did quite well, as those claiming that it didn’t.  
It may be that the only solution will be to try out CRC32C vs. FarmHash64, and see what does best overall.

---

<div class="post-metadata">

**Author:** ![Keno](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/keno/32/285_2.png) [@Keno](https://discourse.julialang.org/u/Keno)\
**Post date:** [March 19, 2018, 11:04pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/7 "2018-03-19T23:04:07Z")

</div>

If we care about hash flood attacks, CRC32 is not an appropriate choice (though FarmHash and SipHash are designed to defend against it). It seems likely that we do want a hash flood resistant hash function here.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 20, 2018, 12:28am UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/8 "2018-03-20T00:28:08Z")

</div>

Apparently MurmurHash is also susceptible to attacks, so if that’s going to be one of the criteria, then we should probably investigate both FarmHash & SipHash.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 20, 2018, 6:07pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/9 "2018-03-20T18:07:14Z")

</div>

> [@Keno](#):
>
> If we care about hash flood attacks, CRC32 is not an appropriate choice (though FarmHash and SipHash are designed to defend against it). It seems likely that we do want a hash flood resistant hash function here.

I found [this discussion](https://github.com/google/highwayhash/issues/28) to be very informative. One of the authors there argues at least somewhat persuasively that no hash function can provide real protection against flooding attacks, because hash tables use only a few bits of the hash and hence can always be brute-forced (since there are a variety of ways to get the seed). Hence you might as well use CRC32c, which has good distribution properties and is fast. To defend against hash flooding, the argument was that you need to focus instead on the hash-table implementation, and in particular on hiding/randomizing the seed and on collision resolution. (Caveat: I’m no cryptographer. But the back-and-forth on this issue was interesting.)

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 20, 2018, 6:27pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/10 "2018-03-20T18:27:23Z")

</div>

In general, it might be nice to make it a bit easier to plug in your own hash functions so that you can use something optimized for your application. This is already possible (and fast!) by just defining a wrapper type

```julia
struct HashWrap{T}
    x::T
end 
hash(h::HashWrap....) = ...

```

and then defining various `convert` methods and a specialized `keys` iterator etcetera, so that `Dict{HashWrap{T},V}` acts like `Dict{T,V}`.

But it’s a fair amount of boilerplate to write, and it seems like it would better to have done in one place, e.g. in Base or a package. Especially since a slight bit of cleverness is required to encode an arbitrary hash function in the type, ala `HashWrap{T,F<:Function}`, and to use this information efficiently.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 20, 2018, 6:32pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/11 "2018-03-20T18:32:06Z")

</div>

> [@stevengj](#):
>
> (Caveat: I’m no cryptographer. But the back-and-forth on this issue was interesting.)

I have a very well respected cryptographer buddy (worked with him for years at InterSystems), I’ll see if I can pick his brain on this issue.  
He always knows really scary stuff that hackers can do when you’re not extremely careful! 😀

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 20, 2018, 6:56pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/12 "2018-03-20T18:56:59Z")

</div>

> [@stevengj](#):
>
> provide real protection against flooding attacks

I must have missed some discussion, but why is this a concern for hash tables in Julia?

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [March 20, 2018, 7:24pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/13 "2018-03-20T19:24:18Z")

</div>

Julia is a general purpose language, so concerns about flooding attacks concern it as much as any other language.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 20, 2018, 7:35pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/14 "2018-03-20T19:35:56Z")

</div>

That was pretty much the conclusion that I’d come to, and if you want a more attack resistant (not attack proof, I don’t think that’s even possible) hash table, then that’s probably best addressed by a package with a different `AbstractDict` type.  
One technique that I use to ameliorate this sort of problem, is to store the full hash values for each element of the hash table, for hash tables where checking for equality and/or calculating the hash is expensive, such as for strings, where it’s not O(1) (on the number of characters in the string).  
Also, each hash table can use a separate value that is mixed in with the calculated `hash` value, just for that specific hash table, possibly a random value.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 20, 2018, 7:40pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/15 "2018-03-20T19:40:19Z")

</div>

> [@Tamas\_Papp](#):
>
> I must have missed some discussion, but why is this a concern for hash tables in Julia?

A lot of languages have adapted their default hash algorithms to address concerns about hash flooding. As I understand it, the argument is basically “better safe than sorry” when it comes to the default (since sometimes a library’s hash table might get used in unexpectedly sensitive places), coupled with the difficulty of using a non built-in hash in many high-level languages. Some relevant discussions from other languages:

- Python: [Python adopts SipHash [LWN.net]](https://lwn.net/Articles/574761/)
- Ruby: [switch SipHash from SipHash24 to SipHash13 variant · ruby/ruby@04c94f9 · GitHub](https://github.com/ruby/ruby/commit/04c94f95d1a1c6a12f5412228a2bcdc00f5de3b2)
- Rust: [Remove (most) cryptographic algorithms from Rust by DaGenix · Pull Request #9744 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/pull/9744), [Change SipHash implementation to an optimized assembly version · Issue #35735 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/issues/35735), [consider using a different hash than SipHash for integer keys in rustc · Issue #10586 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/issues/10586)
- Java: [Loading...](https://bugs.openjdk.java.net/browse/JDK-8046170)
- Perl: [The dangerous SipHash myth // perl11 blog](http://perl11.org/blog/seed.html)
- Go: [runtime: Extend Go's map crypto hash guarentee to all platforms in 1.5 · Issue #9365 · golang/go · GitHub](https://github.com/golang/go/issues/9365), [runtime: make aeshash more DOS-proof · golang/go@91059de · GitHub](https://github.com/golang/go/commit/91059de095703ebc4ce6b8bad7a0a40dedeef7dc)

Julia is in a somewhat different position than several of these languages, however, in that you can swap your own hash function into Julia’s `Dict` type without any performance cost. Whereas in something like CPython the hash function is embedded in the C implementation and it’s not possible to use a different hash without either sacrificing performance, writing a huge pile of C code, or recompiling Python itself.

Even so, there is still a valid argument about coding defensively when writing library/package code.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 20, 2018, 7:47pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/16 "2018-03-20T19:47:45Z")

</div>

> [@stevengj](#):
>
> Julia is in a somewhat different position than several of these languages, however, in that you can swap your own hash function into Julia’s Dict type without any performance cost.

Ain’t Julia grand? 😀

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 20, 2018, 7:54pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/17 "2018-03-20T19:54:20Z")

</div>

> [@stevengj](#):
>
> “better safe than sorry” when it comes to the default

I don’t know a lot about hash functions, but my understanding is that there is a trade-off between cryptographically relevant properties and speed. Since Julia is computationally oriented, I wonder if simply going for speed (conditional on other relevant properties for hashing) would be a reasonable choice, too.

Of course, with a modular framework, the user can make this choice on a case-by-case basis.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 20, 2018, 8:19pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/18 "2018-03-20T20:19:00Z")

</div>

> [@ScottPJones](#):
>
> Also, each hash table can use a separate value that is mixed in with the calculated hash value, just for that specific hash table, possibly a random value.

Yes, if you don’t use a secret seed then my understanding is that there is essentially no point to using a secure hash — you are vulnerable to brute-force attacks if the hash function and the seed are known, even if the hash function is cryptographically strong, because of the small number of bits used by the hash table.

The SipHash paper proposes to use a cryptographically secure hash function in part to protect against the case where an attacker can actually see the value of `hash(x) mod n` but the seed is secret. I’m not sure in what practical circumstance this would be possible without also exposing you to other attacks to get the seed value, though. Indeed, that seems to be one of the criticisms of the proposal that SipHash increases security of hash tables.

The first step towards more security in Julia’s `Dict`, before anything else, would be to at least have the option of a randomized hash seed (see also [Julia is vulnerable to HashDoS · Issue #16172 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/16172)). (Currently, you can do this with a `HashKey` wrapper object, but something built-in would be better.)

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 20, 2018, 8:24pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/19 "2018-03-20T20:24:49Z")

</div>

> [@stevengj](#):
>
> Even so, there is still a valid argument about coding defensively when writing library/package code.

One thing that is a problem with Julia’s hashing design (not just for strings), is the way that hashing and isequal are tied together, but sometimes you aren’t trying to have a table where different types are ever considered equal, or you want to calculate a hash for fingerprinting, not for a hash table.

For my Str strings and characters I’m having to go to a _lot_ of performance killing work, in order to make strings that I would expect to be considered equal end up hashing the same (which means having to convert them to UTF-8, just to perform the hash, instead of being free to hash based on the Unicode code points directly, or at least hashing based on UTF-16 code units, which would be much more performant in most all cases).  
(This issue affects any type of AbstractString or AbstractChar currently, I believe @bkamins has raised the issue on GitHub).

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 20, 2018, 8:33pm UTC](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818/20 "2018-03-20T20:33:33Z")

</div>

Just randomly thinking, maybe we need something like a hash function API, and one of the parameters would be whether you need “isequal” compatible results (default true).

[Next page](https://discourse.julialang.org/t/use-of-murmurhash3-for-hashing-strings/9818.md?page=2)