It is true that it must be commutative, but not true that it must be
non-associative. Here is a sample implementation of a hash function for
sets that is commutative and associative but doesn't collide for these
sorts of common rearrangements. The idea of this proof of concept is that
the hash value of a set is the sum of (expt 3 (abs (hash item))) for each
item in the set.
Implementation:
;; First a wrap-around implementation of expt
(defn- expt [base pow]
(if (zero? pow) 1
(loop [n (int pow), y (int 1), z (int base)]
(let [t (even? n), n (quot n 2)]
(cond
t (recur n y (unchecked-multiply-int z z))
(zero? n) (unchecked-multiply-int z y)
:else (recur n (unchecked-multiply-int z y)
(unchecked-multiply-int z z)))))))
(declare my-hash)
(defn set-hash [coll]
(reduce + (for [item (seq coll)] (expt 3 (my-hash item)))))
(defn my-hash [i]
(if (set? i) (set-hash i) (hash i)))
=> (my-hash #{#{1 2} 3})
531468
=> (my-hash #{#{1 3} 2})
-1010140990
=> (my-hash #{#{1 3} #{2 4}})
-2065039966
=> (my-hash #{#{1 2} #{3 4}})
-868484254
=> (my-hash #{[1 2] [2 1]})
-3497906806
=> (my-hash #{[1 1] [2 2]})
-443882362
So this is certainly a solvable problem, the real question is how to go
about designing such a hash function around a smaller number of simple
arithmetic operations. Also, the above implementation is kind of lame
because that expt function treats the hash value of the item as a positive
number, effectively cutting the possible hash values in half. So this
implementation isn't practical, but should serve as an illustration of what
could be done.
--
--
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.
