Ok, I have what I think is an improved microbenchmark for this: xor of hasheqs for a long, a double, a string, a class, a character and a PHM (single instance, so it'll be a hash lookup). The results are not very encouraging.
Single form including the require to make it convenient to run; also bundled is a j.u.HashMap (128 entries) hasheq benchmark:
(require '[criterium.core :as c])
(let [l 41235125123
phm (apply hash-map (interleave (range 128) (range 128)))
juhm (java.util.HashMap. phm)
f (fn f 
(-> (clojure.lang.Util/hasheq l)
(bit-xor (clojure.lang.Util/hasheq d))
(bit-xor (clojure.lang.Util/hasheq s))
(bit-xor (clojure.lang.Util/hasheq k))
(bit-xor (clojure.lang.Util/hasheq c))
(bit-xor (clojure.lang.Util/hasheq phm))))]
(c/bench (hash juhm))))
Mean execution time as reported by Criterium:
The substring patch is broken (see below), so I skipped it. The patch I'm describing as the "original" one is attached as 0001-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M.patch.
Decisions common to all the patches:
1. One extra if statement in hasheq just above the default return with a three-way instanceof check.
2. The types tested for are j.u.Iterable, j.u.Map.Entry and j.u.Map.
3. Murmur3.hashOrdered takes Iterable, so that's why it's on the list. Map does not extend Iterable, so it's listed separately. Map.Entry is on the list, because ultimately the way to hash maps is to iterate over and hash their entries.
4. The actual hashing of the "alien" / host types is done by a separate static method – clojure.lang.Util.doalienhasheq – on the theory that this will permit hasheq to be inlined more aggressively and limit the worst of the perf hit to alien collections.
5. doalienhasheq checks for Map, Map.Entry, Set and List; entries are converted to lists for hashing, maps are hashed through entry sets and lists and sets are passed directly to Murmur3.
6. There is also a default case for other Iterable types – we must return hashCode or the result of composing some other function with hashCode for these, since we use equals to test them for equivalence.
The 0005 patch has hasheq call a separate private static method to perform the three-way type check, whereas the others put the check directly in the actual if test. The -alternative patch and the 0005 patch return hashCode in the default case, whereas the original patch composes Murmur3.hashInt with hashCode.
The substring patch only works for java.util.** classes and so doesn't solve the problem (it wouldn't correctly hash Guava collections, for example).
All of the patches change c.l.Util.hasheq and add one or two new static methods to clojure.lang.Util that act as helpers for hasheq. None of them changes anything else. Murmuring hashCode was a performance experiment that appeared to have a slight positive impact on some of the "fast cases" (in fact it's still the best performer among the current three patches in the microbenchmark presented above, although the margin of victory is of course extremely tiny). Thus I think all the current patches are in fact limited in scope to changes directly relevant to the ticket; the -alternative patch and the 0005 patch certainly are.