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 添加特殊案例，就像现在对 String 那样。

有关此主题在 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类型给定的clojure.lang.Util/hasheq的“调度时间”。因此，我多次对同一个持久哈希映射进行哈希，以理论上的方式测量IHashEq实例的调度时间。然后，我对PHM、字符串和长进行单独的基准测试，并使用unchecked-add将结果加在一起。希望这是一个好开始；我无疑认为还需要进行额外的基准测试。

结果让我有些惊讶：在这种情况下，我的构建中PHM上的hasheq实际比在1.6.0上要快；而在1.6.0上的“添加三个hasheq”基准测试要快。


;;; 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)))
警告：最后进行垃圾回收需要 runtime 的 1.24405836928592 %
评估计数：5549560980 在 60 个样本中，每个样本为 92492683 次。
             执行时间平均值：9.229881 纳秒
    执行时间标准差：0.156716 纳秒
   执行时间下四分位数：8.985994 纳秒 (2.5%)
   执行时间上四分位数：9.574039 纳秒 (97.5%)
                   开销使用：1.741068 纳秒

在 60 个样本中发现 2 个异常值（3.3333%）
    低严重性     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%）
    低严重性     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个样本中包含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)))
评估次数：5537698680次，60个样本，每样本92294978次调用。
             执行时间平均值：8.973200纳秒
    执行时间标准差：0.157079纳秒
   执行时间下四分位数：8.733544纳秒（2.5%）
   执行时间上四分位数：9.289350纳秒（97.5%）
                   开销使用：1.744772纳秒
评估次数：2481600次，60个样本，每样本41360次调用。
             执行时间平均值：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%
评估次数：954751500次，60个样本，每样本15912525次调用。
             执行时间平均值：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对那些在所有检查之后才到达末尾的对象的成本很感兴趣。上方评论列表是一个好起点——例如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)))
WARNING: Final GC required 1.409118084170768 % of runtime
评估计数：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)))
WARNING: Final GC required 1.3353133083866688 % of runtime
评估计数：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
`

带有新的补丁（在默认情况下没有额外的murmur步骤）的单个PHM和类/字符/变量结果

`
用户=> (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)))))
WARNING: Final GC required 1.258952964663877 % of runtime
评估计数：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)))
警告：最终垃圾收集需要运行时的1.31690036780011 %
评估次数：在60个样本中为1661453640，总共27690894次调用。

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

执行时间下四分位数：34.454839 ns（2.5%）
执行时间上四分位数：35.953584 ns（97.5%）

               Overhead used : 1.556642 ns

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

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

执行时间下四分位数：35.083030 ns（2.5%）
执行时间上四分位数：36.190015 ns（97.5%）

               Overhead used : 1.556642 ns

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

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

离群值方差：1.6389%，方差略微因离群值而膨胀
评估次数：在60个样本中为1440434700，总共24007245次调用。

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

执行时间下四分位数：40.055991 ns（2.5%）
执行时间上四分位数：41.990985 ns（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纳秒之内）和"添加三个hasheq"的基准（使用补丁为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个样本中为5183841240，总共86397354次调用。
             平均执行时间：10.076893 ns
    标准偏差：0.182592 ns
   执行时间下四分位数：9.838456 ns（2.5%）
   执行时间上四分位数：10.481086 ns（97.5%）
                   开销使用：1.565749 ns
评估次数：在60个样本中为3090420，总共51507次调用。
             平均执行时间：19.596627 µs
    标准偏差：224.380257 ns
   执行时间下四分位数：19.288347 µs（2.5%）
   执行时间上四分位数：20.085620 µs（97.5%）
                   开销使用：1.565749 ns
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)))))
警告：最终垃圾收集需要运行时的1.418253438197936 %
评估次数：在60个样本中为879210900，总共14653515次调用。
             平均执行时间：66.939309 ns
    标准偏差：0.747984 ns
   执行时间下四分位数：65.667310 ns（2.5%）
   执行时间上四分位数：68.155046 ns（97.5%）
                   开销使用：1.724002 ns
nil


需要注意的是，我在对1.6.0进行基准测试时，在新JVM上获得了"三个hasheq"基准测试的无补丁结果，所以应用补丁重做了基准测试。改变许多不同的类型会显著改变结果——大概是因为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 ns (2.5%)
执行时间上限：37.414722 ns (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 ns (2.5%)
执行时间上限：36.058667 ns (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 ns (2.5%)
执行时间上限：40.499433 ns (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 ns (2.5%)
执行时间上限：73.565908 ns (97.5%)

               Overhead used : 1.738155 ns

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

low-severe	 2 (3.3333 %)

离群值方差：1.6389%，方差略微因离群值而膨胀
nil
`

Answer 11

评论者：michalmarczyk

哦，我漏掉了上面的重复的phm 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 ns
    执行时间标准差：3.407284 ns
   执行时间下限：9.510624 ns (2.5%)
   执行时间上限：11.461485 ns (97.5%)
                   使用开销：1.566301 ns

在60个样本中发现了5个异常值（8.3333%）
    低严重性     3 (5.0000 %)
    低轻度     2 (3.3333 %)
  异常值造成的方差：96.4408 % 方差受到异常值的严重 inflation
评估次数：3078180，在60个样本中，每次调用51303次。
             平均执行时间：19.717981 微秒
    执行时间标准差：209.896848 ns
   执行时间下限：19.401811 μs (2.5%)
   执行时间上限：20.180163 μs (97.5%)
                   使用开销：1.566301 ns

在 60 个样本中发现 2 个异常值（3.3333%）
    低严重性     2 (3.3333%)
 异常值方差：1.6389 % 异常值略微发散方差
nil

Answer 12

由alexmiller发表的评论

请不要提交任何更改哈希值的补丁，除非是为了使 Java 集合与 Clojure 集合匹配——任何其他更改都不在本票据的范围之内。

一般来说，我目前更倾向于只报告平均执行时间，而不是全部——完整的标准输出使得这些注释难以阅读和比较。

Answer 13

由alexmiller发表的评论

请给我一份方法的总结，以及对于一组一致测试的 1.6.0 和每个补丁的计时，例如对 Long、PHM、juHM、Class 和“三个 hasheq”测试的哈希时间？

Answer 14

评论者：richhickey

“对不同类型的哈希进行哈希处理会导致结果明显变化——假设 HotSpot 在看到多个不同类型传递给 hasheq 后会放弃某些优化？”

是的——如果你的基准测试不将此站点视为 megamorphic，你会得到各种失真的结果。

Answer 15

评论者：michalmarczyk

好的，我想我已经为我找到了一个改进的微基准测试：一个长整型、一个双精度浮点型、一个字符串、一个类、一个字符和一个 PHM（单实例，所以它将是一个哈希查找）的 hasheq 的异或。结果并不令人鼓舞。

包含 {{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 报告的平均执行时间

||版本标志||xor (ns)||j.u.HM (µs)||
|未打补丁 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. 测试的 type 为 {{j.u.Iterable}}、{{j.u.Map.Entry}} 和 {{j.u.Map}}。

3. {{Murmur3.hashOrdered}} 接受 {{Iterable}}，因此它出现在列表上。{{Map}} 并没有继承 {{Iterable}}，因此被单独列出。{{Map.Entry}} 出现在列表上，因为实际上散列 map 的方式是迭代其条目并对其散列。

4. "alien" 或主机类型的实际散列是通过一个独立的静态方法 - {{clojure.lang.Util.doalienhasheq}} - 实现的。原理在于这可以让 {{hasheq}} 更具侵略性地内联，并将性能损失限制在 alien 集合中。

5. {{doalienhasheq}} 会检查 {{Map}}、{{Map.Entry}}、{{Set}} 和 {{List}}；条目会被转换成列表进行散列，map 会通过入口集合进行散列，而列表和集合则会直接传递给 {{Murmur3}}。

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

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

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

所有的补丁都修改了 {{c.l.Util.hasheq}} 并在 {{clojure.lang.Util}} 中添加了一个或两个新的静态方法，作为 {{hasheq}} 的辅助工具。它们都没有改变其他内容。Murmuring hashCode 是一个性能实验，似乎对一些“快速案例”略有正面影响（实际上，它仍然是上面提供的微基准测试中当前三个补丁中的最佳性能者，尽管胜利的差距当然是极其微小的）。因此我认为，所有当前的补丁实际上在范围上限制于与问题直接相关的更改；-alternative 补丁和 0005 补丁肯定如此。