Java 收集器一致性哈希问题

Question

c.c/hash总是使用hashCode来为Java集合生成哈希值，这与Clojure集合使用Murmur3进行哈希值比较时产生不兼容问题。

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发表的评论

添加与Jozef Wagner的clj-1372.diff相同的磁盘补丁clj-1372-2.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次发生的实例中（注意，这些中正好0个是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说“对于非值（Java集合显然属于这类）的hasheq/equiv，所有的赌注都应该撤销。”

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 的主要用户是哈希表和哈希集。因此，要体现出来，您需要将 Clojure 和 Java 集合的混合体放入其中，特别是那些比较为相等的集合的混合体。

仍在考虑这个问题。

Answer 12

由wagjo发表的评论

抱歉做了垃圾邮件，但也许还有另一种选择，不是在hasheq中使用hashCode回退，而是当请求hasheq非值时抛出异常。这将导致散列类型的更清晰分离。当然，它会阻止非值放入哈希集合中。

Answer 13

评论者：alexmiller

不过，没有简单的方法来检查“值存在”吗？

Answer 14

由jafingerhut发表的评论

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

Answer 15

评论者：alexmiller

Map也不继承Collection。