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

评论者：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/= 一致？甚至可以提及浮点数也不支持：参见 CLJ-1036

Answer 9

评论者：alexmiller

我认为应该把与 hash 相关的详细文档放在 https://clojure.org/data_structures 而不是在文档字符串中。尽管 hash 的文档字符串可能需要更新，并指向最新更改后的网站。

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 集合的 = 支持 - 这似乎很重要且有用。如果这样做是不付费的，我愿意不附加条件地说明：如果 eqiv=true，则 hasheq 是相同的。

我觉得这个票据上列出的例子实际上并不是人们可能遇到的真实问题。hasheq 的主要用户是哈希表和哈希集。所以为了得到体现，你需要把这些 Clojure 和 Java 集合混合在一起，尤其是比较相等的集合。

仍然在考虑。

Answer 12

评论者：wagjo

对不起这样打扰你，但也许还有一个选择，那就是在 hasheq 中不回退到 hashCode，而是当需要非值时抛出异常。这将会导致不同哈希类型的更清洁分离。当然，这将防止非值放入哈希集。

Answer 13

评论者：alexmiller

尽管如此，并没有简单的检查“valueness”的机制吗？

Answer 14

评论者：jafingerhut

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

Answer 15

评论者：alexmiller

Map也没有扩展Collection。