Skip to content →

Computing java.util.List hashCode()s back-to-front

For some applications, it could be desirable to compute java.util.List hashCode()s backwards, recursively from back to front, rather than front-to-back as defined in the API [1]. For instance, in Clojure this would enable computing the hash values for all of the rests of a seq for free while computing its hash value. This requires just a tiny bit of math and understanding of modular arithmetic. Clojure code showing how this can be done follows.

[1] http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html#hashCode()

(defn forward-hash "How hashCode() is defined in java.util.List"  [s]
  (loop [s (seq s) h (int 1)]
    (if s 
        (recur (rest s) (int (unchecked-add (unchecked-multiply h 31) (hash (first s)))))
      h)))
 
 
(def int-pow 
     (memoize 
      (fn [x n]
	(let [x (int x) n (int n)]
	  (cond (zero? n) 1
		(even? n) (let [h (int-pow x (/ n 2))] (unchecked-multiply h h))
		:else     (unchecked-multiply x (int-pow x (dec n))))))))
 
(defn backward-hash "Compute the same value as forward-hash, but back-to-front."  [s]
  (let [s (seq s) p (int-pow 31 (count (rest s)))]
    (if s 
        (unchecked-add (unchecked-multiply 30 p)
		       (unchecked-add (int (backward-hash (rest s)))
				      (unchecked-multiply (int (hash (first s))) p)))
	1)))
 
 
user> (map #(% (vec (range 1000))) [forward-hash backward-hash #(.hashCode %)])
(133786869 133786869 133786869)

Update: I posted this on the Clojure issue page here. Note a small caveat there: it is not allowed by Java that (.equals [] (seq [])), so Clojure collections and seqs cannot be comparable in general. However, everything carries through for non-empty seqs and collections.

Published in Clojure Java

One Comment

  1. May befor (var i = 0; i < this.length; i++) {notfor (i = 0; i < this.length; i++) {And I think if we cash this.length it was more faster, fllaniy:String.prototype.hashCode = function(){ var hash = 0, len = this.length; if ( len === 0 ) return hash; for( var i = 0; i < len; ++i ) { char = this.charCodeAt(i); hash = ((hash<<5)-hash)+char; hash = hash & hash; // Convert to 32bit integer } return hash;}

Leave a Reply

Your email address will not be published. Required fields are marked *