# Why do hash functions use xor to combine multiple values?
**URL:** https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967
**Category:** General Usage
**Tags:** hash
**Created:** [February 9, 2024, 7:42am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967 "2024-02-09T07:42:45Z")
**Posts on this page:** 13
**Page:** 1
### Author:  [@abraemer](https://discourse.julialang.org/u/abraemer)
#### Post date: [February 9, 2024, 7:42am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/1 "2024-02-09T07:42:45Z")
Continuing the discussion from [Dictionary lookup errors when the struct contains empty vectors](https://discourse.julialang.org/t/dictionary-lookup-errors-when-the-struct-contains-empty-vectors/109965/2):
> [@Dictionary lookup errors when the struct contains empty vectors](https://discourse.julialang.org/t/dictionary-lookup-errors-when-the-struct-contains-empty-vectors/109965/2):
>
> ```julia
> Base.hash(n::Node, h::UInt) = sum(hash, children(n); init=h)
>
> ```
>
> (I am a little dubious of using `sum` in hash and would consider `reduce(xor`, but that is another discussion)
Usually in these hash function one sees `xor` being used to combine the results of multiple values. I myself usually also use `xor` but out of cargo cult essentially. So I wanted to ask: Why exactly is it `xor` and not `+`? At the surface level (and with wrapping arithmetic) they seem very similar. After all a single bit add is just a `xor` that sets a carry/overflow flag. So is the origin of `xor` in systems where integer overflow is bad or just mathematical convenience or is there something inherently “safer” in `xor`?
---
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [February 9, 2024, 8:02am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/2 "2024-02-09T08:02:40Z")
Because xor-ing a random value with something else yields another random value. Xor-ing multiple pseudorandom random values together can make it appear even more random.
---
### Author:  [@abraemer](https://discourse.julialang.org/u/abraemer)
#### Post date: [February 9, 2024, 8:04am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/3 "2024-02-09T08:04:50Z")
And summing them would cause a “regression to the mean” kind of thing due to central limit theorem, so make it less random? Is that a valid point of view?
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [February 9, 2024, 8:05am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/4 "2024-02-09T08:05:04Z")
I have also seen the following nested pattern somewhere, can anyone comment on the difference with `xor`?
```julia
struct MyStruct
a
b
end
Base.hash(x::MyStruct, h::UInt) = hash(x.a, hash(x.b, h))
```
---
### Author:  [@oxinabox](https://discourse.julialang.org/u/oxinabox)
#### Post date: [February 9, 2024, 9:47am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/5 "2024-02-09T09:47:56Z")
I would say in julia with its 2 arg hash that that yes, using the second arg is indeed preferable over `xor` (or `+`).
You can see the history of julia’s 2 arg hash in [RFC: new approach to efficiently hashing 1, 1.0, big(1), the same. by StefanKarpinski · Pull Request #6624 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/6624)
when i suggested xor I ironically forgot the whole point of julia’s 2 arg hash system, to make combinging them well defined.
The general property you want from a hashing function is for things that are similar or that go together in some sense should hash far apart, unless they are equal.
This is a property that `xor` gives cos it is combining them in a way that doesn’t preserve any meaning of the bits relative to each other.
In contrast + preserves some meaning in that you get a carry if both bits at a lower position are 1.
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [February 9, 2024, 9:58am UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/6 "2024-02-09T09:58:13Z")
> [@oxinabox](#):
>
> In contrast + preserves some meaning in that you get a carry if both bits at a lower position are 1.
But avoiding collisions is not necessarily bad for hashes, right?
In any case, both `+` (with modulo arithmetic, ie the overflow behavior we have in Julia) and `xor` form groups over `UInt`s.
I think that using `xor` is a historical tradition because in the olden days it was faster than `+` (you can do it bitwise, which is relevant when the CPU can’t fit the whole hash into a register). Dunno if that is the case still.
To do hashing “properly”, one would have to think about the properties of the hash function and experiment with it, but in practice is rarely done for user-defined types unless there is a problem that needs to be addressed.
---
### Author:  [@Sukera](https://discourse.julialang.org/u/Sukera)
#### Post date: [February 9, 2024, 3:24pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/7 "2024-02-09T15:24:06Z")
> [@oxinabox](#):
>
> This is a property that `xor` gives cos it is combining them in a way that doesn’t preserve any meaning of the bits relative to each other.
It’s generally good to avoid collisions with hashes - e.g. if you’d just use `reduce(xor, transcode(UInt8, "foo"))` you’d get the same as `reduce(xor, transcode(UInt8, "oof"))`:
```julia
julia> reduce(xor, transcode(UInt8, "foo"))
0x66
julia> reduce(xor, transcode(UInt8, "oof"))
0x66
```
This is because `xor` is symmetric. The same is of course true with `+`, so the usual fix is to make this non-symmetric, e.g. with `hash(a)*3 + hash(b)`. See [this StackOverflow](https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes/27952689#27952689) answer for more information.
---
### Author:  [@mnemnion](https://discourse.julialang.org/u/mnemnion)
#### Post date: [February 9, 2024, 4:09pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/8 "2024-02-09T16:09:50Z")
> [@gdalle](#):
>
> I have also seen the following nested pattern somewhere, can anyone comment on the difference with `xor`?
>
> ```julia
> struct MyStruct
> a
> b
> end
>
> Base.hash(x::MyStruct, h::UInt) = hash(x.a, hash(x.b, h))
>
> ```
Is this really good practice? Wouldn’t it yield identical hash identities for any struct with the same bit values for `a` and `b`?
I would think the way to hash a struct should be like this:
```julia
struct MyStruct
a::T
b::U
end
function Base.hash(x::MyStruct, h::UInt)
seed = hash((:MyStruct, a:, b:), 0) # compile-time constant
hash(x.a, hash(x.b, hash(seed, h)))
end
```
But perhaps some sort of hashing of the type is already taking place in the one-argument form.
---
### Author:  [@Sukera](https://discourse.julialang.org/u/Sukera)
#### Post date: [February 9, 2024, 4:23pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/9 "2024-02-09T16:23:34Z")
> [@mnemnion](#):
>
> But perhaps some sort of hashing of the type is already taking place in the one-argument form.
The one-arg form falls back to `hash(x, zero(UInt))`, which in turn falls back to `hash(x, h::UInt) = hash_uint(3h - objectid(x))`. `objectid` in turn does take the type into account:
```julia
julia> struct Foo end
julia> struct Bar end
julia> hash(Foo())
0x9e2c647635155a8c
julia> hash(Bar())
0x5669dd55187f2041
```
Note that there are some specializations for e.g. integers in `hash`, such that `hash(1) === hash(0x1)`.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [February 9, 2024, 4:33pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/10 "2024-02-09T16:33:27Z")
The common idiom I see and like here is to also hash the type itself. E.g.,
>
---
### Author:  [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)
#### Post date: [February 9, 2024, 4:57pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/11 "2024-02-09T16:57:36Z")
`xor` is useful when you want to exploit its symmetry. I used `xor` [(see here)](https://github.com/CameronBieganek/GraphTypes.jl/blob/850b59ba4ce9de0ed664764d647368acd4317661/src/graph.jl#L13) when writing the `hash` function for a type that represents an undirected graph edge:
```julia-repl
julia> using GraphTypes
julia> hash(Edge(1, 2)) == hash(Edge(2, 1))
true
```
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [February 9, 2024, 5:15pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/12 "2024-02-09T17:15:24Z")
Another reason:
xor is more easily implemented in hardware (much fewer transistors or ‘area’) and sometimes has smaller latency (because no carry calculation circuitry needed). Therefore it was used often in older designs and very high throughput designs and… inertia does the rest.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [February 9, 2024, 5:58pm UTC](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/13 "2024-02-09T17:58:09Z")
6 posts were split to a new topic: [Internals of types and how they hash](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998)