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

评论者：wagjo

对于映射也存在相同的问题，因此 hasheq 应该为 java.util.Map 也提供一个特殊案例。

Answer 2

评论者：wagjo

添加了修补程序，用于修复 j.u. Map、Set 和 List。

Answer 3

评论者：jafingerhut

添加了 patch 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'对象，但这与clojure的互操原则相矛盾（互操作简单、快速、没有惊喜）。

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构建过程中，我看到了以下一系列类，它们中出现了此问题（注意，这些中没有任何一个是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/=保证一致性的短语？甚至还可以提到浮点数也不行：参见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，但请在请求非值时的hasheq中抛出异常。这将导致hash类型之间的更清晰的分离。当然这会阻止将非值放入hash-set。

Answer 13

评论由中国用户：alexmiller 提出

然而，并没有简单的检查来判断“是否有值”？

Answer 14

评论者：jafingerhut

一个想法，如果它有价值的话：在Util.hasheq方法中为java.util.Collection的一个实例添加一个测试，而不是为Set、List和Map分别添加3个单独的测试。这并没有涵盖Map.Entry。

Answer 15

评论由中国用户：alexmiller 提出

Map也没有扩展Collection。