Java 集合的哈希不一致问题

Question

c.c/hash 始终使用 java 集合的 hashCode，当与使用 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

评论者：wagjo

对于映射（map）也存在相同的问题，因此 hasheq 应该针对 java.util.Map 也有一个特殊案例。

Answer 2

评论者：wagjo

添加了修复 j.u. Map、Set 和 List 的补丁。

Answer 3

评论者：jafingerhut

添加补丁 clj-1372-2.diff，该补丁与 Jozef Wagner 的 clj-1372.diff 相同，但它还添加了一些在未应用他的更改时失败、在应用更改时通过的测试。

Answer 4

评论者：alexmiller

我认为equiv/hasheq合同的范围更窄，仅适用于这两个集合都是IPersistentCollection的情况。换句话说，我认为这并不需要也不必需。

请注意，这里的Java .equals/.hashCode合同是维护的 - 这些集合将作为.equals()进行比较，并且确实具有相同的.hashCode()。

Answer 5

评论者：wagjo

没有补丁的情况下，以下声明无效："如果两个对象使用c.c/=相等，那么由c.c/hash返回的散列值是相同的"。我们可以说，只有在两个对象都是'clojure'对象的情况下，这才是有效的，但这与clojures的互操作原则相冲突（互操作简单、快速，无惊喜）。

Answer 6

评论者：wagjo

这个错误的体现

user=> (assoc (hash-map [1 2 3] :foo) (java.util.ArrayList. [1 2 3]) :bar) {[1 2 3] :bar, [1 2 3] :foo} user=> (get (hash-map [1 2 3] :foo) (java.util.ArrayList. [1 2 3])) nil

Answer 7

评论者：alexmiller

我同意，不加任何修饰地这样说会是一个很好的事情。

在hasheq中添加更多分支确实有一定的代价 - 添加这些集合检查会影响每个hasheq。运行完整的Clojure构建，我看到以下这组类，其中出现了>100次这种情况（注意，这其中的Java集合实际上并不存在，Clojure构建本身并没有这种情况）

clojure.lang.Var 107001502 java.lang.Class 2651389 java.lang.Character 2076322 java.util.UUID 435235 java.util.Date 430956 clojure.lang.Compiler$LocalBinding 116830 java.lang.Boolean 112361 java.util.regex.Pattern 325

我们将在每个hasheq的路径中添加4个额外的instanceof检查。这也可能破坏任何JVM内联。

Rich说"hasheq/equiv对于非值的比较没有任何保证"，其中Java集合显然属于"非值"类别。

Answer 8

评论者：jafingerhut

是否可以接受一个文档补丁？比如修改clojure.core/hash的文档，加入显示其只保证对于不可变值的clojure.core/=保持一致性的语句？甚至可以提及Floats也如此：参见CLJ-1036

Answer 9

评论者：alexmiller

我认为在https://clojure.org/data_structures上编写有关哈希的详细文档更好，而不是在文档字符串中。尽管哈希的文档字符串可能需要更新，并在最新更改后添加指向网站的链接。

Answer 10

评论者：wagjo

尽管这是一个从1.5开始的重大变更，但在变更日志中应该提到。仍然让我困扰的是，在这种情况下支持c.c/=，但c.c/hash则不行。如果支持c.c/hash代价高昂，那么放弃c.c/=的支持不是更好吗？这将消除像下面这样的意外

user=> (apply distinct? (hash-set [1 2 3] (java.util.Collections/unmodifiableList [1 2 3]))) false

Answer 11

评论者：alexmiller

我不确定如果没有被认为是保证会发生变化的，这算不算是一个“重大的”变更。 :) 但我理解你的观点。

我不认为放弃Clojure和Java集合的等号支持是可行的，这看起来很重要且有用。如果这样做的代价不高，我很乐意不加限制地宣称，如果equiv=true，则hasheq相同。

对我来说，这次票证上列举的例子并不是人们可能会遇到的实际问题。hasheq的主要用户是哈希表和哈希集。所以为了体现出来，你需要将Clojure和Java集合的混合体放入其中之一中，特别是比较相等的集合体。

仍在思考这个问题。

Answer 12

评论者：wagjo

对于打扰表示歉意，但可能还有另一个选项，就是在hasheq中不回退到hashCode，而是在请求非值时抛出异常。这将导致更清晰的哈希类型划分。当然这将阻止将非值放入hash-set中。

Answer 13

评论者：alexmiller

但没有一个简单的检查来确定“值的存在”吗？

Answer 14

评论者：jafingerhut

一个建议，如果它有价值的话：在 Util.hasheq 方法中，用针对 java.util.Collection 实例的一个测试来代替对 Set、List 和 Map 的三个单独的测试。它不包括 Map.Entry。

Answer 15

评论者：alexmiller

Map 也不扩展 Collection。