使用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 master，这两个补丁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}中的=保持一致。此外，它还将String的特殊处理（返回hashCode的hasheq）扩展到所有未处理的其他类型（有关此的评论见下文）。

它也可在此处获得

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)))
WARNING：最后一次GC需要1.24405836928592 %的运行时间
评估次数：60个样本中的92492683次调用，共5549560980次。
             执行时间平均值：9.229881 ns
    执行时间标准差：0.156716 ns
   执行时间下四分位数：8.985994 ns（ 2.5%）
   执行时间上四分位数：9.574039 ns（97.5%）
                   额外开销：1.741068 ns

60个样本中发现2个异常值（3.3333%）
    low-severe     2 (3.3333%)
 从异常值中提取的方差：6.2652 % 额外的方差略微偏大
评估次数：60个样本中的594128次调用，共35647680次。
             执行时间平均值：1.695145 µs
    执行时间标准差：20.186554 ns
   执行时间下四分位数：1.670049 µs（ 2.5%）
   执行时间上四分位数：1.740329 µs（97.5%）
                   额外开销：1.741068 ns

60个样本中发现2个异常值（3.3333%）
    low-severe     2 (3.3333%)
 从异常值中提取的方差：1.6389 % 额外的方差略微偏大
nil

user=> (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：最后一次GC需要1.028614538339401 %的运行时间
评估次数：1029948300，在17165805次调用中的60个样本。
             平均执行时间：56.797488纳秒
    执行时间标准差：0.732221纳秒
   执行时间下四分位数：55.856731纳秒（2.5%）
   执行时间上四分位数：58.469940纳秒（97.5%）
                 使用的开销：1.836671纳秒

在60个样本中找到1个异常值（1.6667%）
    低严重性     1（1.6667%）
 从异常值中提取的方差：1.6389 % 额外的方差略微偏大
nil

;;; 补丁应用

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)))
评估次数：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

user=> (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设置单独的分支。这使得hasheq对于实现IHashEq的对象更快，但使得“三个散列”基准测试慢了大约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)))
警告：最终GC需要运行时1.409118084170768 %的时间
评估计数：655363680次，每个样本10922728次调用。

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

执行时间下限：95.079086纳秒（2.5%）
执行时间上限：98.684168纳秒（97.5%）

               Overhead used : 1.708347 ns

评估计数：675919140次，每个样本11265319次调用。

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

执行时间下限：87.817159纳秒（2.5%）
执行时间上限：90.755688纳秒（97.5%）

               Overhead used : 1.708347 ns

评估计数：574987680次，每个样本9583128次调用。

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

执行时间下限：102.257474纳秒（2.5%）
执行时间上限：106.071144纳秒（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需要运行时1.3353133083866688 %的时间
评估计数：1829305260次，每个样本30488421次调用。

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

执行时间下限：33.680636纳秒（2.5%）
执行时间上限：34.990138纳秒（97.5%）

               Overhead used : 1.718257 ns

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

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

异常值方差：1.6389 % 异常值略微增加了方差
评估计数：1858100340次，每个样本30968339次调用。

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

执行时间下限：30.095976纳秒（2.5%）
执行时间上限：30.871497纳秒（97.5%）

               Overhead used : 1.718257 ns

评估计数：1592932200次，每个样本26548870次调用。

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

执行时间下限：35.795063纳秒（2.5%）
执行时间上限：36.918183纳秒（97.5%）

               Overhead used : 1.718257 ns

在60个样本中找到1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

异常值方差：1.6389 % 异常值略微增加了方差
nil
`

使用新补丁（默认情况下没有额外的murmur步骤）一个PHM和类/字符/Var的结果

`
user=> (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.258952964663877 %的时间
评估计数：1007768460次，每个样本16796141次调用。

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

执行时间下限：57.655857纳秒（2.5%）
执行时间上限：59.154655纳秒（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次，每个样本10799068次调用。

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

执行时间下限：90.330980纳秒（2.5%）
执行时间上限：92.711120纳秒（97.5%）

               Overhead used : 1.567532 ns

评估计数：699506160次，每个样本11658436次调用。

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

执行时间下限：83.765607纳秒（2.5%）
执行时间上限：85.569206纳秒（97.5%）

               Overhead used : 1.567532 ns

在60个样本中找到1个异常值（1.6667%）

low-severe	 1 (1.6667 %)

异常值方差：1.6389 % 异常值略微增加了方差
评估计数：594919980次，每个样本9915333次调用。

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

执行时间下限：99.313490纳秒（2.5%）
执行时间上限：102.167675纳秒（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 %。
评估次数：1661453640次，在60个样本中的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

评估次数：1630167600次，在60个样本中的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 % 异常值略微增加了方差
评估次数：1440434700次，在60个样本中的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 ns之内）和"添加三个哈希"基准（有补丁时66 ns，无补丁时57 ns）。


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)))
评估次数：5183841240次，在60个样本中的86397354次调用。
             平均执行时间：10.076893 ns
    标准差：0.182592 ns
   执行时间下四分位数：9.838456 ns（2.5%）
   执行时间上四分位数：10.481086 ns（97.5%）
                   开销：1.565749 ns
评估次数：3090420次，在60个样本中的51507次调用。
             平均执行时间：19.596627 µs
    标准差：224.380257 ns
   执行时间下四分位数：19.288347 µs（2.5%）
   执行时间上四分位数：20.085620 µs（97.5%）
                   开销：1.565749 ns
nil

user=> (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 %。
评估次数：879210900次，在60个样本中的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上获得了"三个哈希"基准的无补丁结果，因此我也这样应用了补丁来重复基准测试。更改许多不同类型会明显改变结果——HotSpot在看到传给hasheq的几个不同类型后可能会放弃一些优化吗？

Answer 10

评论者：michalmarczyk

此段代码（0005-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M.patch）引入了一个新的静态方法isAlien，用于检查Map/Map.Entry/Iterable的instanceof，并使用该方法检查“外国集合”。

初期基准测试结果令人鼓舞

`
;;; "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.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" 基准
user=> (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查找以及java.util.HashMap实例对基准测试，现在提供这些以供完整性（不过没有惊喜）


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)))
警告：最终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和“三个hasheq”测试的hash时间？

Answer 14

_由 richhickey 发布的评论_

“对许多不同类型进行hash会明显改变结果——大概是HotSpot在看到传递给hasheq的多个不同类型后会避免一些优化？”

是的——如果您的基准测试不将此视为megamorphic，您将得到各种扭曲的结果。

Answer 15

_评论由：michalmarczyk_

好的，我认为这是一个改进的微观基准：一个长整型、一个双浮点数、一个字符串、一个类、一个字符和一个PHM（单个实例，所以它将是一个hash查找）的hasheq的异或。结果并不令人鼓舞。

包括{{require}}的单个形式，以便方便执行；此外还包括{{j.u.HashMap}}（128项）hasheq基准


（执行
   （require '[criterium.core :as c]）
   （let [l  41235125123）
   （let [d  123.456）
   （let [s  "asdf;lkjh"）
   （let [k  BigInteger）
   （let [c  \S）
   （let [phm  (apply hash-map (interleave (range 128) (range 128)））
   （let [juhm (java.util.HashMap. phm)）
   （let [f  (fn f []）
   （let [(-> (clojure.lang.Util/hasheq l)）
   （let [(-> (bit-xor (clojure.lang.Util/hasheq d))）
   （let [(-> (bit-xor (clojure.lang.Util/hasheq s))）
   （let [(-> (bit-xor (clojure.lang.Util/hasheq k))）
   （let [(-> (bit-xor (clojure.lang.Util/hasheq c))）
   （let [(-> (bit-xor (clojure.lang.Util/hasheq phm))))]）
   （c/bench (f)）
   （c/bench (hash juhm)）


由Criterium报告的平均执行时间

||版本||xor (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. "alien" / 主类型实际的散列是通过一个单独的静态方法 -- {{clojure.lang.Util.doalienhasheq}} -- 完成的。基于这种理论，这将允许 {{hasheq}} 更积极地进行内联，并将最坏的性能损失限制在 alien 集合中。

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

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

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

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

所有补丁都改变了 {{c.l.Util.hasheq}} 并在 {{clojure.lang.Util}} 中添加了一个或两个新的静态方法，这些方法作为 {{hasheq}} 的辅助工具。它们都没有改变其他任何内容。Murmuring hashCode 是一个性能实验，似乎对一些 "快速情况" 有轻微的正面影响（实际上它仍然是上面呈现的微基准测试中当前三个补丁中表现最好的一个，尽管获胜的差距当然非常小）。因此，我认为所有当前的补丁实际上在范围上仅限于与票据直接相关的更改； -alternative 补丁和 0005 补丁肯定如此。