Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Not a good practice to put seed as the 1st argument in hash function #592

Open
bowenszhu opened this issue May 1, 2024 · 1 comment
Open

Comments

@bowenszhu
Copy link
Member

bowenszhu commented May 1, 2024

const ADD_SALT = 0xaddaddaddaddadda % UInt
const SUB_SALT = 0xaaaaaaaaaaaaaaaa % UInt
const DIV_SALT = 0x334b218e73bbba53 % UInt
const POW_SALT = 0x2b55b97a6efb080c % UInt
function Base.hash(s::BasicSymbolic, salt::UInt)::UInt
E = exprtype(s)
if E === SYM
hash(nameof(s), salt SYM_SALT)
elseif E === ADD || E === MUL
!iszero(salt) && return hash(hash(s, zero(UInt)), salt)
h = s.hash[]
!iszero(h) && return h
hashoffset = isadd(s) ? ADD_SALT : SUB_SALT
h′ = hash(hashoffset, hash(s.coeff, hash(s.dict, salt)))
s.hash[] = h′
return h′

Note line 267 in the above code. hashoffset of type UInt, serving as a seed, is the first argument of the hash function. Although it still works, it somehow violates the original design principle of 2-argument hash functions.

For hash(x::Int64, h::UInt), Julia Base focuses on the first argument and merely does a scalar multiplication and subtraction to the second argument, which is probably not what we want.
https://github.com/JuliaLang/julia/blob/57b9b591e28181aee8ff985d0ace661b408577d7/base/hashing.jl#L88
https://github.com/JuliaLang/julia/blob/57b9b591e28181aee8ff985d0ace661b408577d7/base/hashing.jl#L79
https://github.com/JuliaLang/julia/blob/57b9b591e28181aee8ff985d0ace661b408577d7/base/hashing.jl#L44

@nsajko
Copy link

nsajko commented May 26, 2024

hash(::UInt, ::UInt) just combines the arguments in a noncommutative way, with a multiplication and subtraction as you say. So it's quite cheap, but you could save a cycle or two by using for mixing hashoffset with the computed hash instead of calling hash(::UInt, ::UInt).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants