( odd x && odd y) ==> hash (x,y) == hash (negate x, negate y )

[jwaldmann]

( odd x && odd y) ==> hash (x,y) == hash (negate x, negate y )

[jwaldmann]

also,

ghci> hash [1,-1,1]
-4935772016787126823

ghci> hash [1,1,-1]
-4935772016787126823

[phadej]

Interesting. I guess it's not a problem with vanilla FNV1 as it hashes byte at the time, so -1 something different.

That's unfortunate. I would like to mix-in Ints efficiently.

I wonder whether there are hash function with machine integers (Word64) as native input type (instead of single bytes).

EDIT: Now as I think of it, given that internal state is 64bit, the 128 bit input will always have collisions. hashable doesn't claim to be collision resistant, but it's not great that there are such easily colliding inputs (which I can imagine can happen, lists of -1 and 1 are not that far fetched key string).

[jwaldmann]

... hash function with machine integers (Word64) as native input type (instead of single bytes).

a quick search turned up this comment "... will provide poorer mixing of the bits" and gives the example of bit flips - I guess that's similar to flipping signs, observed in the present issue
https://cs.stackexchange.com/questions/60950/hash-multiple-integers-directly-using-fnv-1a

This answers the comment in the source

-- Note: FNV-1 hash takes a byte of data at once, here we take an 'Int',
-- which is 4 or 8 bytes. Whether that's bad or not, I don't know.

because ... it is bad? The code (hashInt) is trying to reduce the number of operations (significantly) w.r.t. FNV1 without citing any justification. Presumably there is some paper that defines and proves dispersion for FNV1, but I did not find it. If we had it, then we could re-do the computations for other bit widths.

I am experimenting with

-- hashInt s x = (s * 1099511628211) `xor` x
hashByte s x = (s * 1099511628211) `xor` (x .&. 255)
hashInt s x =
  let rots x = take 8 $ iterate (flip shiftR 8) x
  in  foldl' hashByte s $ rots x

and it does look better (w.r.t. collisions. for run-time - did not measure but it should probably be unrolled)

[phadej]

Could you test the current version 0cfa4fd in #270. I added more mixing, but just 4 rounds, not 8.

[jwaldmann]

Will do (later today). I am thinking both:

1. Great,
2. Wat?

This is a change (different trade-off between no. of collisions and time for computing hash function) that might affect a lot of users of hashable/unordered-containers? So, "4 rounds not 8" should be scrutinized further? (with proofs, or experiments)

On the other hand, perhaps not so much code is hashing numbers and tuples. Else, people would have complained already? But the change also applies to every generic instance of Hashable (does it?)

Perhaps the saving grace is that instances for bytestring (and similar) were using byte-wise computation already, and remain as they are?

[phadej]

But the change also applies to every generic instance of Hashable (does it?)

It does as we hash the constructor number. Good point, that can be changed to hash as previously. (I have to see a Generic instance of type with over 65536 constructors to compile, so hashing three zeros doesn't add much).

That said, the exact values of hash are not part of the API contract, and we are free to change them. It says it in the docs

Note: the hash is not guaranteed to be stable across library versions, operating systems or architectures. For stable hashing use named hashes: SHA256, CRC32 etc.

I should add that to the package description as well. (EDIT: Done)

[jwaldmann]

I checked your 0cfa4fd . The collisions that I was complaining about, are gone.

NB: and I was thinking: for the SAT/SMT encoding folks (like me), it's a nice challenge to find a small collision (for (Int,Int), say) with 2, 4, 8 rounds.

[phadej]

it's a nice challenge to find a small collision (for (Int,Int), say) with 2, 4, 8 rounds.

What you mean by small? I guess you want to ask SMT for a counterexample of "there aren't simple bit flip collisions for hash(x,y)"

[phadej]

To add to the last, don't spend too much time. I'll investigate how much breakage switching hashable to using siphash would cause, and how much performance changes (where hashing Text or ByteString is what really matters, not tuples or lists of Ints - though they shouldn't be too slow either).

[jwaldmann]

small

e.g., hash(x1,y1)==hash(x2,y2) with $|x_1|+|y_1|+|x_2|+|y_2|$ minimal.

I did use leancheck for enumeration, but with the improved code now that takes too long (which is a good sign - there are no small collisions)

or something like http://www.isthe.com/chongo/tech/comp/fnv/#zero-hash

what really matters

that, of course, depends on the hashmap key type in the application. For me, right now, it's not (byte)strings but trees. I think I want hash-consing, really.