Java 集合中的不一致哈希

Question

c.c/hash 总是使用 hashCode 为 Java 集合生成哈希值，这与使用 Murmur3 的 Clojure 集合不兼容。

user=> (== (hash (java.util.ArrayList. [1 2 3])) (hash [1 2 3])) false user=> (= (java.util.ArrayList. [1 2 3]) [1 2 3]) true

修复这个问题的一种方法是在 Util/hasheq 中为 java.util.Collections 添加一个特殊案例，就像现在为 Strings 所做的。

关于这个主题的讨论链接在 Clojure 群组中： https://groups.google.com/forum/#!topic/clojure/dQhdwZsyIEw

Answer 1

stu 评论

我认为这需要更多的考虑，而且不应该阻止 1.6。

Answer 2

jafingerhut 评论

截至 2014 年 3 月 20 日，最新的 Clojure 主分支上，补丁 clj-1372.diff 和 clj-1372-2.diff 无法干净地应用。我相信在 2014 年 3 月 19 日的提交之前，它们可以干净地应用。唯一的问题是 diff 上下文的改变行。鉴于关于是否希望这种变化进行的讨论，看来在决定是否应该进行任何更改之前，需要更多的思考。

Answer 3

mikera 评论

这是一个相当严重的缺陷。它绝对需要修复。这不仅仅关乎使用Clojure和Java集合的混合是否是可能的使用场景（可能不是……），这关乎提供人们可以依赖的一致性保证。

例如，现在我真的很不确定我使用的某些使用集合或映射的库函数是否已损坏。我特别担心任何基于哈希值实现对象缓存/记忆化/内建的代码。这样的代码现在可能存在一些非常糟糕的微妙缺陷。

由于它们是库函数，我无法保证传递的对象类型，因此代码必须与所有可能的输入兼容（或者我需要编写清晰的文档字符串，并在不支持输入时抛出异常）。

Answer 4

_评论由：michalmarczyk_发表

此补丁（0001-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M.patch）使hasheq在java.util.{List,Map,Map.Entry,Set}中与等号一致。此外，它将特殊的处理方式扩展到除以下情况之外的所有类型（关于这一点，请参见以下评论）。

它也在此处可用

https://github.com/michalmarczyk/clojure/tree/alien-hasheq-2

早期版本在此处可用

https://github.com/michalmarczyk/clojure/tree/alien-hasheq

如果理解正确，需要基准测试的主要是clojure.lang.Util/hasheq给定Clojure类型时的“分发时间”。因此，我反复对相同的持久哈希映射进行哈希，按照这个理论，这将仅测量IHashEq实例上的分发时间。然后我运行了另一个基准测试，在这个测试中，哈希PHM、字符串和长整型，并使用unchecked-add将结果相加。希望这是一个好的开始；毫无疑问，更多的基准测试会有所帮助。

对于这个结果，我有些惊讶：PHM上的hasheq在这个基准测试中实际上比我构建的1.6.0快一点；“添加三个hasheq”的测试在1.6.0上稍微快一点。


;;; 1.6.0

;;; 注意：j.u.HM基准测试不相关
user=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] #_(assert (= (hash phm) (hash juhm))) (c/bench (clojure.lang.Util/hasheq phm)) (c/bench (clojure.lang.Util/hasheq juhm)))
WARNING: Final GC required 1.24405836928592 % of runtime
评估计数：5549560980次，在60个样本中，每个样本92492683次调用。
             平均执行时间：9.229881纳秒
    执行时间标准差：0.156716纳秒
   执行时间下限四分位数：8.985994纳秒（2.5%）
   执行时间上限四分位数：9.574039纳秒（97.5%）
                   使用的开销：1.741068纳秒

在60个样本中发现了2个异常值（3.3333%）
    low-severe     2 (3.3333%)
 异常值方差：6.2652%  异常值略微增加了方差
评估计数：35647680次，在60个样本中，每个样本594128次调用。
             平均执行时间：1.695145微秒
    执行时间标准差：20.186554纳秒
   执行时间下限四分位数：1.670049微秒（2.5%）
   执行时间上限四分位数：1.740329微秒（97.5%）
                   使用的开销：1.741068纳秒

在60个样本中发现了2个异常值（3.3333%）
    low-severe     2 (3.3333%)
 异常值方差：1.6389%  异常值略微增加了方差
nil

用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] #_(assert (= (hash phm) (hash juhm))) (c/bench (unchecked-add (clojure.lang.Util/hasheq phm) (unchecked-add (clojure.lang.Util/hasheq "foo") (clojure.lang.Util/hasheq 123)))))
警告：最后进行GC所需1.028614538339401 %的运行时间
评估计数：在60个样本的17165805次调用中共计1029948300次。
             执行时间平均值：56.797488纳秒
    执行时间标准差：0.732221纳秒
   执行时间下四分位数：55.856731纳秒（2.5%）
   执行时间上四分位数：58.469940纳秒（97.5%）
                   开销使用：1.836671纳秒

在60个样本中发现了1个异常值（1.6667%）
    低严重性     1（1.6667%）
 异常值方差：1.6389%  异常值略微增加了方差
nil

;;; 修复已应用

用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] (assert (= (hash phm) (hash juhm))) (c/bench (clojure.lang.Util/hasheq phm)) (c/bench (clojure.lang.Util/hasheq juhm)))
评估计数：在60个样本的92294978次调用中共计5537698680次。
             执行时间平均值：8.973200纳秒
    执行时间标准差：0.157079纳秒
   执行时间下四分位数：8.733544纳秒（2.5%）
   执行时间上四分位数：9.289350纳秒（97.5%）
                   开销使用：1.744772纳秒
评估计数：在60个样本的41360次调用中共计2481600次。
             执行时间平均值：24.287800微秒
    执行时间标准差：288.124326纳秒
   执行时间下四分位数：23.856445微秒（2.5%）
   执行时间上四分位数：24.774097微秒（97.5%）
                   开销使用：1.744772纳秒
nil

用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] #_(assert (= (hash phm) (hash juhm))) (c/bench (unchecked-add (clojure.lang.Util/hasheq phm) (unchecked-add (clojure.lang.Util/hasheq "foo") (clojure.lang.Util/hasheq 123)))))
警告：最后进行GC所需1.298136122909759 %的运行时间
评估计数：在60个样本的15912525次调用中共计954751500次。
             执行时间平均值：61.681794纳秒
    执行时间标准差：0.712110纳秒
   执行时间下四分位数：60.622003纳秒（2.5%）
   执行时间上四分位数：62.904801纳秒（97.5%）
                   开销使用：1.744772纳秒

在60个样本中发现了1个异常值（1.6667%）
    低严重性     1（1.6667%）
 异常值方差：1.6389%  异常值略微增加了方差
nil


顺便说一下，其他分支中可用的此补丁的早期版本没有为String设置单独的分支。这使得对于实现IHashEq的对象的hasheq更快，但大约使“三个散列”基准测试减慢了2倍。

Answer 5

由 alexmiller 留言

为了清楚起见，请按名称引用此处附上的补丁，随着时间的推移，我们不必将附件时间与留言时间相关联。

我对实现IHashEq的东西的成本不太担心，因为它们应该不受影响，除了潜在的结果内联问题。我对hasheq对于在case末尾落地并承担所有检查成本的对象的成本感到好奇。评论中更上面的清单是一个好的起点 - 例如Class、Character和Var（这些可能可以在Var中解决）。

Answer 6

评论由：michalmarczyk 发布

很好的观点，我已经将上面的评论编辑为包含补丁名称。

感谢您提出基准测试的建议——我将在大约6分钟内发布一些新结果。

Answer 7

评论由：michalmarczyk 发布

首先，为了完整起见，这里是一个新的补丁（0001-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M-alternative.patch），它不会为未处理的其他类型执行额外的murmur操作。对于单个PHM情况，速度较慢；下面是详细情况。此外，GitHub上的分支在这

https://github.com/michalmarczyk/clojure/tree/alien-hasheq-3

至于新结果，性能下降相当大，我恐怕

`
;; 与补丁（murmur hashCode默认版本）
user=> (let [class-instance java.lang.String character-instance \(a\) var-instance \`hash\] (c/bench (clojure.lang.Util/hasheq class-instance)) (c/bench (clojure.lang.Util/hasheq character-instance)) (c/bench (clojure.lang.Util/hasheq var-instance)))
警告：最终GC需要.runtime的1.409118084170768 %
评估计数：655363680在60个样品中的10922728次调用。

         Execution time mean : 96.459888 ns
Execution time std-deviation : 1.019817 ns

执行的低位量：95.079086 ns（2.5%）
执行的时间高位量：98.684168 ns（97.5%）

               Overhead used : 1.708347 ns

评估计数：675919140在60个样品中的11265319次调用。

         Execution time mean : 88.965959 ns
Execution time std-deviation : 0.825226 ns

执行的低位量：87.817159 ns（2.5%）
执行的时间高位量：90.755688 ns（97.5%）

               Overhead used : 1.708347 ns

评估计数：574987680在60个样品中的9583128次调用。

         Execution time mean : 103.881498 ns
Execution time std-deviation : 1.103615 ns

执行的低位量：102.257474 ns（2.5%）
执行的时间高位量：106.071144 ns（97.5%）

               Overhead used : 1.708347 ns

在60个样本中发现了1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
nil

;;; 1.6.0
user=> (let [class-instance java.lang.String character-instance \(a\) var-instance \`hash\] (c/bench (clojure.lang.Util/hasheq class-instance)) (c/bench (clojure.lang.Util/hasheq character-instance)) (c/bench (clojure.lang.Util/hasheq var-instance)))
警告：最终GC需要.runtime的1.3353133083866688 %
评估计数：1829305260在60个样品中的30488421次调用。

         Execution time mean : 34.205701 ns
Execution time std-deviation : 0.379106 ns

执行的低位量：33.680636 ns（2.5%）
执行的时间高位量：34.990138 ns（97.5%）

               Overhead used : 1.718257 ns

在60个样本中发现了2个异常值（3.3333%）

low-severe	 1 (1.6667 %)
low-mild	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
评估计数：1858100340在60个样品中的30968339次调用。

         Execution time mean : 30.401309 ns
Execution time std-deviation : 0.213878 ns

执行的低位量：30.095976 ns（2.5%）
执行的时间高位量：30.871497 ns（97.5%）

               Overhead used : 1.718257 ns

评估计数：1592932200在60个样品中的26548870次调用。

         Execution time mean : 36.292934 ns
Execution time std-deviation : 0.333512 ns

执行的低位量：35.795063 ns（2.5%）
执行的时间高位量：36.918183 ns（97.5%）

               Overhead used : 1.718257 ns

在60个样本中发现了1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
nil
`

PHM以及新的补丁（默认情况无额外murmur步骤）和类/字符/变量结果

`
用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] #_(assert (= (hash phm) (hash juhm))) (c/bench (unchecked-add (clojure.lang.Util/hasheq phm) (unchecked-add (clojure.lang.Util/hasheq "foo") (clojure.lang.Util/hasheq 123)))))
警告：最终GC需要.runtime的1.258952964663877 %
评估计数：1007768460在60个样品中的16796141次调用。

         Execution time mean : 58.195608 ns
Execution time std-deviation : 0.482804 ns

执行的低位量：57.655857 ns（2.5%）
执行的时间高位量：59.154655 ns（97.5%）

               Overhead used : 1.567532 ns

在60个样本中发现了1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
nil
user=> (let [class-instance java.lang.String character-instance \(a\) var-instance \`hash\] (c/bench (clojure.lang.Util/hasheq class-instance)) (c/bench (clojure.lang.Util/hasheq character-instance)) (c/bench (clojure.lang.Util/hasheq var-instance)))
评估计数：647944080在60个样品中的10799068次调用。

         Execution time mean : 91.275863 ns
Execution time std-deviation : 0.659943 ns

执行的低位量：90.330980 ns（2.5%）
执行的时间高位量：92.711120 ns（97.5%）

               Overhead used : 1.567532 ns

评估计数：699506160在60个样品中的11658436次调用。

         Execution time mean : 84.564131 ns
Execution time std-deviation : 0.517071 ns

执行的低位量：83.765607 ns（2.5%）
执行的时间高位量：85.569206 ns（97.5%）

               Overhead used : 1.567532 ns

在60个样本中发现了1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
评估计数：594919980在60个样品中的9915333次调用。

         Execution time mean : 100.336792 ns
Execution time std-deviation : 0.811312 ns

执行的低位量：99.313490 ns（2.5%）
执行的时间高位量：102.167675 ns（97.5%）

               Overhead used : 1.567532 ns

在60个样本中发现了3个异常值（5.0000%）

low-severe	 3 (5.0000 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
nil
`

Answer 8

评论由：michalmarczyk 发布

这里有一个新的补丁（0001-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M-substring.patch），采用了用类名上的.startsWith("java.util.")替换Iterable/Map/Entry测试的非常规方法。（我尝试了.getClass().getPackage()方法，但性能非常糟糕。）分支在这里

https://github.com/michalmarczyk/clojure/tree/alien-hasheq-4

使用此补丁在“fall-through”情况下的哈希性能似乎非常好

`
user=> (let [class-instance java.lang.String character-instance \(a\) var-instance \`hash\] (c/bench (clojure.lang.Util/hasheq class-instance)) (c/bench (clojure.lang.Util/hasheq character-instance)) (c/bench (clojure.lang.Util/hasheq var-instance)))
警告：最终GC需要运行时的1.31690036780011 %
评估次数：在60个样本中为27690894次调用中的1661453640次。

         Execution time mean : 35.099750 ns
Execution time std-deviation : 0.422800 ns

执行时间的最小分位数：34.454839纳秒（2.5%）
执行时间的最大分位数：35.953584纳秒（97.5%）

               Overhead used : 1.556642 ns

评估次数：在60个样本的27169460次调用中为1630167600次。

         Execution time mean : 35.487409 ns
Execution time std-deviation : 0.309872 ns

执行时间的最小分位数：35.083030纳秒（2.5%）
执行时间的最大分位数：36.190015纳秒（97.5%）

               Overhead used : 1.556642 ns

在60个样本中发现了4个异常值（6.6667%）

low-severe	 3 (5.0000 %)
low-mild	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
评估次数：在60个样本的24007245次调用中为1440434700次。

         Execution time mean : 40.894457 ns
Execution time std-deviation : 0.529510 ns

执行时间的最小分位数：40.055991纳秒（2.5%）
执行时间的最大分位数：41.990985纳秒（97.5%）

               Overhead used : 1.556642 ns

nil
`

Answer 9

_评论由：michalmarczyk_发表

新补丁（...-substring.patch）返回除了List、Map、Map.Entry和Set之外的java.util.**类的hashCode，所以这里没有行为变化。

这里是重复PHM查找的基准测试（比1.6.0慢一些，但在1纳秒之内）以及“添加三个hasheqs”基准测试（有补丁时为66纳秒，无补丁时为57纳秒）


用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] (assert (= (hash phm) (hash juhm))) (c/bench (clojure.lang.Util/hasheq phm)) (c/bench (clojure.lang.Util/hasheq juhm)))
评估次数：在60个样本的86397354次调用中为5183841240次。
             执行时间平均值：10.076893纳秒
    执行时间标准偏差：0.182592纳秒
   执行时间的最小分位数：9.838456纳秒（2.5%）
   执行时间的最大分位数：10.481086纳秒（97.5%）
                   使用的开销：1.565749纳秒
评估次数：在60个样本的51507次调用中为3090420次。
             执行时间平均值：19.596627微秒
    执行时间标准偏差：224.380257纳秒
   执行时间的最小分位数：19.288347微秒（2.5%）
   执行时间的最大分位数：20.085620微秒（97.5%）
                   使用的开销：1.565749纳秒
nil

用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] #_(assert (= (hash phm) (hash juhm))) (c/bench (unchecked-add (clojure.lang.Util/hasheq phm) (unchecked-add (clojure.lang.Util/hasheq "foo") (clojure.lang.Util/hasheq 123)))))
警告：最终GC需要运行时的1.418253438197936 %
评估次数：在60个样本的14653515次调用中为879210900次。
             执行时间平均值：66.939309纳秒
    执行时间标准偏差：0.747984纳秒
   执行时间的最小分位数：65.667310纳秒（2.5%）
   执行时间的最大分位数：68.155046纳秒（97.5%）
                   使用的开销：1.724002纳秒
nil


重要的是要注意，我在基准测试1.6.0时在新的JVM上获取了“三个hasheqs”基准测试的无补丁结果，因此我也用补丁应用后重复进行了基准测试。大量不同类型更改了结果——可能是HotSpot在看到传递给hasheq的几个不同类型后减少了一些优化？

Answer 10

评论由：michalmarczyk 发布

这里有一个新的补丁（0005-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M.patch），它引入了一个新的 isAlien 静态方法，用来检查 instanceof Map/Map.Entry/Iterable，并使用此方法来测试“外来集合”。

最初的基准测试结果很有希望

`
;;; “掉落”基准
user=> (let [class-instance java.lang.String character-instance \(a\) var-instance \`hash\] (c/bench (clojure.lang.Util/hasheq class-instance)) (c/bench (clojure.lang.Util/hasheq character-instance)) (c/bench (clojure.lang.Util/hasheq var-instance)))
警告：最终 GC 需要 1.258979068087473 % 的运行时间
评估次数：1598432100 次在 60 个样本中，每个样本 26640535 次调用。

         Execution time mean : 36.358882 ns
Execution time std-deviation : 0.566925 ns

执行时间下四分位数：35.718889 纳秒（2.5%）
执行时间上四分位数：37.414722 纳秒（97.5%）

               Overhead used : 1.823120 ns

在60个样本中发现了1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
评估次数：1626362460 次在 60 个样本中，每个样本 27106041 次调用。

         Execution time mean : 35.426993 ns
Execution time std-deviation : 0.294517 ns

执行时间下四分位数：35.047064 纳秒（2.5%）
执行时间上四分位数：36.058667 纳秒（97.5%）

               Overhead used : 1.823120 ns

在60个样本中发现了1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
评估次数：1461423180 次在 60 个样本中，每个样本 24357053 次调用。

         Execution time mean : 39.541873 ns
Execution time std-deviation : 0.423707 ns

执行时间下四分位数：38.943560 纳秒（2.5%）
执行时间上四分位数：40.499433 纳秒（97.5%）

               Overhead used : 1.823120 ns

在60个样本中发现了2个异常值（3.3333%）

low-severe	 2 (3.3333 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
nil

;;; “三个 hasheq” 基准
用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] #_(assert (= (hash phm) (hash juhm))) (c/bench (unchecked-add (clojure.lang.Util/hasheq phm) (unchecked-add (clojure.lang.Util/hasheq "foo") (clojure.lang.Util/hasheq 123)))))
警告：最终 GC 需要 1.5536755331464491 % 的运行时间
评估次数：820376460 次在 60 个样本中，每个样本 13672941 次调用。

         Execution time mean : 71.999365 ns
Execution time std-deviation : 0.746588 ns

执行时间下四分位数：70.869739 纳秒（2.5%）
执行时间上四分位数：73.565908 纳秒（97.5%）

               Overhead used : 1.738155 ns

在60个样本中发现了2个异常值（3.3333%）

low-severe	 2 (3.3333 %)

从离群值中分发的方差：1.6389 % 方差略微受到离群值的影响
nil
`

Answer 11

_评论由：michalmarczyk_发表

啊，我漏掉了上述中的重复的 phm hasheq 查找 + hasheq 的 java.util.HashMap 实例对基准——下面就是为了完整性（没有惊喜）


用户=> (let [phm (apply hash-map (interleave (range 128) (range 128))) juhm (java.util.HashMap. phm)] (assert (= (hash phm) (hash juhm))) (c/bench (clojure.lang.Util/hasheq phm)) (c/bench (clojure.lang.Util/hasheq juhm)))
警告：最终 GC 需要 1.260853406580491 % 的运行时间
评估次数：5369135760 次在 60 个样本中，每个样本 89485596 次调用。
             执行时间平均值：10.380464 纳秒
    执行时间标准差：3.407284 纳秒
   执行时间下四分位数：9.510624 纳秒（2.5%）
   执行时间上四分位数：11.461485 纳秒（97.5%）
                   使用的开销：1.566301 纳秒

在 60 个样本中发现了 5 个异常值（8.3333%）
   低严重程度     3（5.0000%）
   低轻微程度     2（3.3333%）
 异常值的方差：96.4408% 异常值严重拉大了方差
评估次数：3078180 次在 60 个样本中，每个样本 51303 次调用。
             执行时间平均值：19.717981 微秒
    执行时间标准差：209.896848 纳秒
   执行时间下四分位数：19.401811 微秒（2.5%）
   执行时间上四分位数：20.180163 微秒（97.5%）
                   使用的开销：1.566301 纳秒

在60个样本中发现了2个异常值（3.3333%）
    low-severe     2 (3.3333%)
 异常值方差：1.6389%  异常值略微增加了方差
nil

Answer 12

由 alexmiller 留言

请不要提交任何除了使 Java 集合匹配 Clojure 集合之外更改任何对象的 hashCode 的补丁——任何其他更改都不在该票证的范围之内。

一般来说，我目前更愿意只看执行时间的平均值报告，而不是所有信息——完整的准则输出使得这些评论难以阅读和比较。

Answer 13

由 alexmiller 留言

能否给我一个方法的总结，以及对于一组固定测试用例，1.6.0及每个补丁的计时比较——比如Long、PHM、juHM、Class和“三个两个散列”测试的散列时间？

Answer 14

_由 richhickey 发表的评论_

“对许多不同类型进行散列会明显改变结果——HotSpot看到对hasheq传递几种不同类型后可能会退回一些优化？”

是的——如果你的基准测试没有将这一点视为megamorphic，你将得到各种扭曲的结果。

Answer 15

_评论由：michalmarczyk_发表

好的，这是我认为的一个改进的微基准：对一个long、一个double、一个字符串、一个类、一个char和一个PHM（单例，所以它将是一个hash查找）的hasheqs的异或。结果并不令人鼓舞。

包含{{require}}以便方便运行的单一种形式；还包括一个{{j.u.HashMap}}（128项）的hasheq基准


(do
  (require '[criterium.core :as c]))
  (let [l    41235125123)
        d    123.456)
        s    "asdf;lkjh")
        k    BigInteger)
        c    \S)
        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 (f))
    (c/bench (hash juhm)))


Criterium报告的平均执行时间

||版本||异或 (ns)||j.u.HM (微秒)||
|未修补 1.6.0|148.128748|1.701640|
|0005补丁|272.039667|21.201178|
|原始补丁|268.670316|21.169436|
|-备用补丁|271.747043|20.755397|

子字符串补丁已损坏（见下文），因此我跳过了它。我所说的“原始”补丁已附加为0001-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M.patch。

所有补丁的共同决策

1. 在默认返回上方的hasheq中添加一个额外的{{if}}语句，上面有一个三路{{instanceof}}检查。

2. 测试的类型是{{j.u.Iterable}}、{{j.u.Map.Entry}}和{{j.u.Map}}。

3. {{Murmur3.hashOrdered}}接受{{Iterable}}，这就是它为什么在列表上的原因。"{{Map}}"不扩展{{Iterable}}，所以它单独列出来。"{{Map.Entry}}"在列表上，因为最终散列映射的方法是迭代并对其条目进行散列。

4. "外部" / 主类型的确切散列由另一个单独的静态方法完成--{{clojure.lang.Util.doalienhasheq}}--理论是这将允许hasheq更积极地内联，并将性能损失最坏的情况限制在外部集合上。

5. {{doalienhasheq}}检查{{Map}}、{{Map.Entry}}、{{Set}}和{{List}}；条目被转换为列表以进行散列，映射通过条目标集进行散列，而列表和散列表直接传递给{{Murmur3}}。

6. 对于其他{{Iterable}}类型也存在一个默认情况--我们必须返回{{hashCode}}或这些的与其他函数组成的函数的结果，因为这些我们使用{{equals}}来测试它们以进行等价性。

0005补丁使{{hasheq}}调用一个单独的私有静态方法来执行三种类型检查，而其他方法将检查直接放入实际的{{if}}测试中。替代补丁和0005补丁在默认情况下返回{{hashCode}}，而原始补丁将{{Murmur3.hashInt}}与{{hashCode}}组合。

子字符串补丁只适用于{{java.util.**}}类，因此无法解决这个问题（例如，它不会正确散列Guava集合）。

所有这些补丁都更改{{c.l.Util.hasheq}}并在{{clojure.lang.Util}}中添加一个或两个新的静态方法作为hasheq的辅助工具。它们没有更改其他任何东西。murmuring hashCode是一种性能实验，在上述微基准测试中似乎对一些"快用例"产生轻微的积极影响（实际上它是目前三个补丁中表现最好的，尽管当然胜利的幅度极其微小）。因此，我认为所有当前的补丁实际上范围有限，仅限于与ticket直接相关的更改；替代补丁和0005补丁肯定如此。