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}。此外，它将字符串的特殊处理（返回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快一点；“添加三个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: 最终GC需要运行时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

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次在60个样本中，每个样本17165805次调用。
             执行时间平均值：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（范围128）（范围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设置单独的分支。这使得实现了IHashEq的对象的hasheq更快，但将“三个散列”基准测试大约减慢了两倍。

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），它不会对未处理的类型进行额外嘈杂的处理。单独的PHM情况下会较慢；下面将详细介绍。另外，GitHub上的分支如下

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

关于新的结果，性能下降相当大，我担心

`
;;; 使用补丁（平凡版本Murmur hash代码）
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: 最终GC耗费1.409118084170768 %的运行时间
评估次数：655363680次，在60个样本中，每次调用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次，在60个样本中，每次调用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次，在60个样本中，每次调用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)))
WARNING: 最终GC耗费1.3353133083866688 %的运行时间
评估次数：1829305260次，在60个样本中，每次调用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次，在60个样本中，每次调用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次，在60个样本中，每次调用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和Class/Character/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)))))
WARNING: 最终GC耗费1.258952964663877 %的运行时间
评估次数：1007768460次，在60个样本中，每次调用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次，在60个样本中，每次调用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次，在60个样本中，每次调用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次，在60个样本中，每次调用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

使用这个补丁的“直接进入”情况下，哈希性能似乎非常好

`
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次，在27690894次的60个样本中。

         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

评估次数：1630167600次，在27169460次的60个样本中。

         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 % 离群值略微提高了方差
评估次数：1440434700次，在24007245次的60个样本中。

         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纳秒内）和“添加三个hasheq”基准的基准测试（使用补丁时为66纳秒，不使用补丁时为57纳秒）


user=>（let [phm（apply hash-map（interleave（范围128）（范围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次，在86397354次的60个样本中。
             执行时间平均值：10.076893纳秒
    执行时间标准差：0.182592纳秒
   执行时间下四分位数：9.838456纳秒（2.5%）
   执行时间上四分位数：10.481086纳秒（97.5%）
                  使用的开销：1.565749纳秒
评估次数：3090420次，在51507次的60个样本中。
             执行时间平均值：19.596627微秒
    执行时间标准差：224.380257纳秒
   执行时间下四分位数：19.288347微秒（2.5%）
   执行时间上四分位数：20.085620微秒（97.5%）
                  使用的开销：1.565749纳秒
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次，在14653515次的60个样本中。
             执行时间平均值：66.939309纳秒
    执行时间标准差：0.747984纳秒
   执行时间下四分位数：65.667310纳秒（2.5%）
   执行时间上四分位数：68.155046纳秒（97.5%）
                  使用的开销：1.724002纳秒
nil


需要注意，我在测试1.6.0时，在新的JVM上获得了“三个hasheq”基准测试的无补丁结果，因此我这样应用补丁后再次进行了基准测试。不同类型的哈希改变结果非常明显——大概是因为HotSpot看到传入多个不同类型到hasheq之后放弃了某些优化？

Answer 10

评论者：michalmarczyk

这是一个新的补丁（0005-CLJ-1372-consistent-hasheq-for-java.util.-List-Map-M.patch），该补丁引入了一个名为isAlien的静态方法，用于检查是否为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”基准测试
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查找加hasheq对java.util.HashMap实例的基准测试遗漏了——这里补上（不过并没有惊喜）


user=>（let [phm（apply hash-map（interleave（范围128）（范围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%）
    严重      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后，会退回一些优化？”

是的——如果您的基准测试没有将此视为多形态，您将得到各种扭曲的结果。

Answer 15

_评论者：michalmarczyk_

好的，我有一个我认为改进的微观基准测试：对长、双精度浮点数、字符串、类、字符和PHM（单实例，所以它将是一个哈希查找）的hasheq进行异或。结果不太令人鼓舞。

一个包含要求以方便运行；还包括一个{{j.u.HashMap}}（128个条目）的hasheq基准


(do
  (require '[criterium.core :as c])
  (let [l 41235125123
              д 123.456
              с "asdf;lkjh"
              к BigInteger
              f \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 д))
                   (bit-xor (clojure.lang.Util/hasheq с))
                   (bit-xor (clojure.lang.Util/hasheq к))
                   (bit-xor (clojure.lang.Util/hasheq f))
                   (bit-xor (clojure.lang.Util/hasheq phm))))]
    (c/bench (f))
    (c/bench (hash juhm))))


由Criterium报告的平均执行时间

||版本||xor (ns)||j.u.HM (µs)||
|unpatched 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}} 测试中进行检查。-alternative 补丁和 0005 补丁在默认情况下返回 {{hashCode}}，而原始补丁将 {{Murmur3.hashInt}} 与 {{hashCode}} 组合。

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

所有补丁都更改了 {{c.l.Util.hasheq}} 并在 {{clojure.lang.Util}} 中添加一个或两个新的静态方法，作为 {{hasheq}} 的辅助。没有哪个更改了其他任何东西。MurmuringhashCode 是一项性能实验，它在某些“快速情况”中似乎产生了一点点积极影响（实际上，它仍然是上面展示的微型基准测试中当前三个补丁中性能最好的，尽管胜利的差距当然是非常微小的）。因此，我认为所有当前补丁实际上都是在更改范围内有限的，即直接与票据相关的更改；-alternative 补丁和 0005 补丁肯定是这样的。