Continuing the discussion from Dictionary lookup errors when the struct contains empty vectors : [image] Dictionary lookup errors when the struct contains empty vectors 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 re…

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.

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?

I have also seen the following nested pattern somewhere, can anyone comment on the difference with xor? struct MyStruct a b end Base.hash(x::MyStruct, h::UInt) = hash(x.a, hash(x.b, h))

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 …

[image] 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…

[image] 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 r…

[image] gdalle: I have also seen the following nested pattern somewhere, can anyone comment on the difference with xor? 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…

[image] 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: j…

The common idiom I see and like here is to also hash the type itself. E.g., JuliaLang/julia/blob/95233619745ef84c96af82299b162aa008a7debd/base/docs/utils.jl#L96-L96 hash(t::T, h::UInt) where {T<:Union{HTML,Text}} = hash(T, hash(t.content, h)) …

xor is useful when you want to exploit its symmetry. I used xor (see here) when writing the hash function for a type that represents an undirected graph edge: julia> using GraphTypes julia> hash(Edge(1, 2)) == hash(Edge(2, 1)) true

Why do hash functions use xor to combine multiple values?

General Usage

Topic		Replies	Views
Why must the second argument of `hash` come from another hash function? General Usage question , hash	5	264	January 15, 2025
Why does my hash function return a different value to the built in hash function? General Usage	7	742	March 16, 2022
About the low quality of Base.hash() General Usage question , hash	8	452	April 4, 2025
Use of hash code in integer hashing Internals & Design	3	763	June 2, 2022
Structural hash collisions Internals & Design	5	208	February 6, 2025

Why do hash functions use xor to combine multiple values?

Related topics