# Hash collision with small vectors
**URL:** https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702
**Category:** General Usage
**Created:** [August 19, 2025, 9:08am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702 "2025-08-19T09:08:42Z")
**Posts on this page:** 17
**Page:** 1
### Author:  [@mxhbl](https://discourse.julialang.org/u/mxhbl)
#### Post date: [August 19, 2025, 9:08am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/1 "2025-08-19T09:08:42Z")
Hi everyone,
I recently ran into a hash collision with very small vectors (I’m on Julia 11.2):
```julia-auto
julia> a = [0x0000000000000080, 0x0000000000100000, 0x0000000000000400, 0x0000000000000100]
4-element Vector{UInt64}:
0x0000000000000080
0x0000000000100000
0x0000000000000400
0x0000000000000100
julia> b = [0x0000000000000100, 0x0000000000100000, 0x0000000000000080, 0x0000000000000400]
4-element Vector{UInt64}:
0x0000000000000100
0x0000000000100000
0x0000000000000080
0x0000000000000400
julia> hash(a) == hash(b)
true
```
Now I know that the Julia hash function is not super safe against collisions and is more designed for speed, but I was still a bit surprised to run into a collision with length four vectors. Is this to be expected? Does the fact that all elements of `a` and `b` are powers of two, and that `b` is a permutation of `a` play a role?
More generally, are there any easy ways to get a more collision resistant hash function? I tried to use the SHA stdlib in the past for this, but I found using SHA to hash Julia objects quite awkward. I’d appreciate any advice!
---
### Author:  [@technocrat](https://discourse.julialang.org/u/technocrat)
#### Post date: [August 19, 2025, 10:06am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/2 "2025-08-19T10:06:23Z")
`hash()` doesn’t take into account the ordering of its arguments. To make it you can pass them as Tuples
```julia
julia> a = [0x0000000000000080, 0x0000000000100000, 0x0000000000000400, 0x0000000000000100]
4-element Vector{UInt64}:
0x0000000000000080
0x0000000000100000
0x0000000000000400
0x0000000000000100
julia> b = [0x0000000000000100, 0x0000000000100000, 0x0000000000000080, 0x0000000000000400]
4-element Vector{UInt64}:
0x0000000000000100
0x0000000000100000
0x0000000000000080
0x0000000000000400
julia> hash(Tuple(a)) == hash(Tuple(b))
false
```
---
### Author:  [@eldee](https://discourse.julialang.org/u/eldee)
#### Post date: [August 19, 2025, 10:19am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/3 "2025-08-19T10:19:54Z")
> [@technocrat](#):
>
> `hash()` doesn’t take into account the ordering of its arguments.
This is incorrect:
```julia-repl
julia> hash(a) == hash(sort(a))
false
```
Looking into the source code, the only differences between `hash(::AbstractArray)` (for short `length`) and `hash(::Tuple)` are that
- they use different seeds (`0x7e2d6fb6448beb77` vs `0x77cfa1eef01bca90` for 64-bit Julia)
- `hash(::AbstractArray)` also takes into account the `axes`
- `hash(::Tuple)` traverses the elements in reverse order, while `hash(::AbstractArray)` uses forward order.
> **Simplified source code**
>
> ```julia
> function my_hash(a::Vector)
> h = 0x7e2d6fb6448beb77
> h = hash((1,), h)
> h = hash((length(a),), h)
> for x in a
> h = hash(x, h)
> end
> return h
> end
>
> function my_hash(t::Tuple)
> # (This is actually more lines of code than the recursive real version,
> # but it makes it easier to contrast to the Vector version)
> h = 0x77cfa1eef01bca90
> for x in reverse(t)
> h = hash(x, h)
> end
> return h
> end
>
> ```
>
> ```julia-repl
> julia> my_hash(a) == hash(a) && my_hash(Tuple(a)) == hash(Tuple(a))
> true
>
> ```
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [August 19, 2025, 10:34am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/4 "2025-08-19T10:34:08Z")
> [@eldee](#):
>
> `hash(::Tuple)` traverses the elements in reverse order, while `hash(::AbstractArray)` uses forward order.
```julia-auto
julia> hash(Tuple(reverse(a))) == hash(Tuple(reverse(b)))
true
```
> [@mxhbl](#):
>
> Does the fact that all elements of `a` and `b` are powers of two, and that `b` is a permutation of `a` play a role?
Maybe, but for this example at least, it’s the only collision among all permutations:
```julia-auto
julia> using Combinatorics
julia> length(permutations(a))
24
julia> length(unique([hash(x) for x in permutations(a)]))
23
```
Trying `rand(UInt, i)` several times over `i in 1:8` hasn’t been able to find another example.
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [August 19, 2025, 10:37am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/5 "2025-08-19T10:37:26Z")
note that this specific MWE will no longer collide in 1.13 (since hash values will change)
> Does the fact that all elements of `a` and `b` are powers of two, and that `b` is a permutation of `a` play a role?
yes, probably. although the new algorithm continues to be designed for speed and is still not collision-resistant (in the cryptographic sense)
depending on your needs, you may be able to use `objectid` as a hash function, but it won’t satisfy the same properties w.r.t. a correspondence to `==` as `hash` does
---
### Author:  [@mxhbl](https://discourse.julialang.org/u/mxhbl)
#### Post date: [August 19, 2025, 11:01am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/6 "2025-08-19T11:01:27Z")
Thanks for all your replies.
I think the collision is related to this line in Base:
```julia-auto
# hashing.jl, line 87
hash(x::UInt64, h::UInt) = hash_uint64(x) - 3h
```
Changing the shift from `3` to e.g. `5` seems to resolve the collision (but probably causes other arrays to collide):
```julia-auto
function demohash(a::Vector{<:UInt}, h::UInt=zero(UInt); n)
# Roughly corresponds what happens in Base.hash, modulo hash seeds and array axes
for x in a
h = Base.hash_uint64(x) - n*h # Base uses n == 3
end
return h
end
```
```julia-auto
julia> demohash(a; n=3) == demohash(b; n=3)
true
julia> demohash(a; n=5) == demohash(b; n=5)
false
```
---
### Author:  [@mxhbl](https://discourse.julialang.org/u/mxhbl)
#### Post date: [August 19, 2025, 11:05am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/7 "2025-08-19T11:05:29Z")
> depending on your needs, you may be able to use `objectid` as a hash function, but it won’t satisfy the same properties w.r.t. a correspondence to `==` as `hash` does
Thanks for this. I don’t think `objectid` will work for my current purpose (I am pretty sure I need the correspondence with `==`), but I will keep it in the back of my head for the future.
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [August 19, 2025, 11:22am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/8 "2025-08-19T11:22:09Z")
> [@mxhbl](#):
>
> I think the collision is related to this line in Base:
>
> ```julia-auto
> # hashing.jl, line 87
> hash(x::UInt64, h::UInt) = hash_uint64(x) - 3h
>
> ```
ah yeah. well luckily that’s also addressed in 1.13. it will become `hash(x - 3h)` so folding chains will mix better (note that the linear part moves _inside_ the `hash` call)
---
### Author:  [@eldee](https://discourse.julialang.org/u/eldee)
#### Post date: [August 19, 2025, 11:30am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/9 "2025-08-19T11:30:05Z")
> [@mxhbl](#):
>
> `# Roughly corresponds what happens in Base.hash, modulo hash seeds and array axes`
Interestingly, the hash equality of `a` and `b` is invariant to the initial hash:
```julia-repl
julia> h = rand(UInt64); hash(a, h) == hash(b, h)
true
```
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [August 19, 2025, 11:49am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/10 "2025-08-19T11:49:42Z")
> [@mxhbl](#):
>
> I tried to use the SHA stdlib in the past for this, but I found using SHA to hash Julia objects quite awkward. I’d appreciate any advice!
The cryptographic hashes all work on byte streams, so you need to serialize an object into a stream of raw bytes before you can hash it.
For example, you could use the Serialization stdlib for this:
```julia-auto
import Serialization, SHA
function myhash(x)
buf = IOBuffer()
Serialization.serialize(buf, x)
reinterpret(UInt64, SHA.sha256(take!(buf)))[1]
end
```
(Of course, this won’t be particularly fast, but it should be cryptographically strong for a 64-bit hash. You can use `UInt128` to have more bits, or even take all 256 bits. Serialization is also not guaranteed to give the same byte stream across Julia versions, so this doesn’t give a version-stable hash if you need that.)
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [August 19, 2025, 11:56am UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/11 "2025-08-19T11:56:52Z")
> [@stevengj](#):
>
> Of course, this won’t be particularly fast
For vectors of bit types you can also reinterpret it directly to avoid serialization:
```julia-auto
a = rand(Int, 4)
reinterpret(UInt64, SHA.sha256(reinterpret(UInt8, a)))[1]
```
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [August 19, 2025, 12:48pm UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/12 "2025-08-19T12:48:24Z")
> [@sgaure](#):
>
> For vectors of bit types you can also reinterpret it directly to avoid serialization:
This actually doesn’t save that much time, and it makes the function much less general.
```julia-auto
myhash2(a) = reinterpret(UInt64, SHA.sha256(reinterpret(UInt8, a)))[1]
```
gives:
```julia-auto
julia> a = rand(Int, 4); @btime hash($a); @btime myhash($a); @btime myhash2($a);
3.750 ns (0 allocations: 0 bytes)
253.157 ns (20 allocations: 1.18 KiB)
163.088 ns (7 allocations: 368 bytes)
julia> a = rand(Int, 400); @btime hash($a); @btime myhash($a); @btime myhash2($a);
270.636 ns (0 allocations: 0 bytes)
6.208 μs (21 allocations: 4.38 KiB)
6.092 μs (7 allocations: 368 bytes)
```
Using SHA-256 is ≈ 50x slower than the insecure `hash`.
---
### Author:  [@mxhbl](https://discourse.julialang.org/u/mxhbl)
#### Post date: [August 19, 2025, 1:11pm UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/13 "2025-08-19T13:11:26Z")
> [@stevengj](#):
>
> For example, you could use the Serialization stdlib for this:
>
> ```julia-auto
> import Serialization, SHA
> function myhash(x)
> buf = IOBuffer()
> Serialization.serialize(buf, x)
> reinterpret(UInt64, SHA.sha256(take!(buf)))[1]
> end
>
> ```
Thanks for this suggestion! This is basically what I also used (I think I originally got this from a similar code snippet you posted in a different thread). This worked well for me if the arrays to be hashed are large, but unfortunately I often have to hash a large number of small arrays. For context: I am working on a wrapper for the graph isomorphism tool nauty. For small graphs, the call to `myhash` can take more time than computing the isomorphism class.
> [@adienes](#):
>
> depending on your needs, you may be able to use `objectid` as a hash function, but it won’t satisfy the same properties w.r.t. a correspondence to `==` as `hash` does
Thinking about this a bit more, I also tried this for vectors of bit types:
```julia-auto
hashobj(x) = objectid(Tuple(x))
```
But this looks kind of dangerous and doesn’t really lead to a meaningful speedup compared to the SHA based `myhash` except for very small vectors:
```julia-auto
julia> a = rand(Int, 4); @btime hash($a); @btime hashobj($a); @btime myhash($a);
4.625 ns (0 allocations: 0 bytes)
106.481 ns (5 allocations: 112 bytes)
275.559 ns (20 allocations: 1.18 KiB)
julia> a = rand(Int, 40); @btime hash($a); @btime hashobj($a); @btime myhash($a);
38.268 ns (0 allocations: 0 bytes)
844.971 ns (41 allocations: 976 bytes)
960.400 ns (21 allocations: 1.49 KiB)
```
I guess the best solution for me would be to use the SHA based `myhash` for large vectors, and maybe use something similar to the 1.13 `hash` implementation for small vectors? (For my very specific graph isomorphism use case, I may also be able to use the hashing tools shipped with the new version of nauty.)
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [August 19, 2025, 1:42pm UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/14 "2025-08-19T13:42:01Z")
what about [GitHub - tecosaur/KangarooTwelve.jl: Hashing with hopping](https://github.com/tecosaur/KangarooTwelve.jl) ? it’s possibly faster than the SHA + serialization approach and only requires that you can convert your data to a `Vector{<:Unsigned}` (which it looks like it already is?)
---
### Author:  [@jling](https://discourse.julialang.org/u/jling)
#### Post date: [August 19, 2025, 3:33pm UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/15 "2025-08-19T15:33:14Z")
> **[GitHub - hros/XXhash.jl: Julia wrapper for xxHash C library](https://github.com/hros/XXhash.jl)**
>
> Julia wrapper for xxHash C library
is very fast. (for less dependency and less speed, [GitHub - Moelf/XXHashNative.jl: Pure Julia implementation of one-shot xxHash3\_64](https://github.com/Moelf/XXHashNative.jl))
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [August 19, 2025, 4:09pm UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/16 "2025-08-19T16:09:23Z")
> [@jling](#):
>
> XXhash.jl is very fast.
Quantitatively, it seems almost as fast as `hash` for a small `Int` array:
```julia-auto
julia> a = rand(Int, 4); @btime hash($a); @btime xxh64($a);
3.750 ns (0 allocations: 0 bytes)
4.291 ns (0 allocations: 0 bytes)
```
Of course, this is not a cryptographic hash, but the authors claim it has low-collision properties.
---
### Author:  [@mxhbl](https://discourse.julialang.org/u/mxhbl)
#### Post date: [August 20, 2025, 2:33pm UTC](https://discourse.julialang.org/t/hash-collision-with-small-vectors/131702/17 "2025-08-20T14:33:00Z")
This looks very promising! Thanks!