lazy incremental hashcodes for Clojure PersistentVector and PersistentMap

repl.clj

user=> (def v (vec (range 1e7)))
#'user/v
user=> (time (hash v))
"Elapsed time: 314.268 msecs"
604896065
user=> (time (hash (assoc v 0 :a (quot (count v) 2) :b (dec (count v)) :c)))
"Elapsed time: 0.097 msecs"
1523739128

user=> (def m (into {} (map (juxt str identity) (range 1e6))))
#'user/m
user=> (time (hash m))
"Elapsed time: 280.189 msecs"
-851486832
user=> (time (hash (assoc m "hello" :world "42" :answer)))
"Elapsed time: 0.129 msecs"
750303239

;; incremental hashes rely on structural sharing, it doesn't matter whether you hash the original or the updated value first
user=> (def v2 (vec (range 1e7)))
#'user/v2
user=> (def v3 (assoc v2 123456 0))
#'user/v3
user=> (time (hash v3))
"Elapsed time: 319.84 msecs"
817767809
user=> (time (hash v2))
"Elapsed time: 0.06 msecs"
604896065

@brandonbloom you mean commutative I guess. To be incremental you only need associativity. Map hashing was already commutative (its a requirement since maps are not ordered). For vectors it required to do a bit of maths to figure out how to decompose the computation in an associative manner.

Re: lazy seqs. It's lazy incremental hash computation I propose: as long as you don't hash, nothing is computed. So no eager computation to force realization of seqs.