There's still a problem with collisions among *vectors* though.
I'd say the real underlying problem is that small integers hash to
themselves. If you let N be a fairly large number satisfying GCD(N, 2^32 -
1) = 1, then multiplying 32-bit integers by N would send nearby integers to
widely separated ones, while inducing a permutation on nonzero integers --
the hash space wouldn't be any smaller. That alone won't help much with the
vector problem, since 3N + 2N = 5N just as 3 + 2 = 5, though it may help
avoid collisions with small integers in small hash maps when the hash is
being used modulo a small hash-table length. What might help with vectors,
sets, and other small data structures containing integers (but would shrink
the hash space by about half) is to additionally square the result (all
operations being 2s-complement 32-bit integer operations with wrapping --
Java "int" arithmetic). Now 1 and 4 won't give the same summed hashes as 3
and 2, and 0 and 5 will be different again. You might also want to add some
constant to avoid 0 hashing to 0.
On Wed, Oct 23, 2013 at 7:46 PM, Mark Engelberg <mark.engelb...@gmail.com>wrote:
> I'd like to point out that my proposed hash function lends itself nicely
> to incremental hashing for sets.
>
> Furthermore, maps also have very weak hashing, and would benefit from a
> similar change. Right now:
> => (hash {1 1})
> 0
> => (hash {1 1 2 2})
> 0
> => (hash {1 1 2 2 3 3})
> 0
> => (hash {1 2 2 3 3 1})
> 6
> => (hash {1 3 2 1 3 2})
> 6
>
> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
