在ClojureScript中可以使用js/BigInt作为map键吗？

Question

js/BigInt支持相等性测试（= (js/BigInt 4) (js/BigInt 4)）为真，因此我预计可以在map中使用它作为键（我不知道用于查找的哈希函数是什么）
然而，我遇到了一些意外的行为

(get {0 0 1 1 2 2 3 3 (js/BigInt 4) 4 5 5 7 7 8 8} (js/BigInt 4))

返回预期的4，但

(get {0 0 1 1 2 2 3 3 (js/BigInt 4) 4 5 5 7 7 8 8 9 9} (js/BigInt 4))

返回nil

此测试使用了Firefox或Safari作为JavaScript引擎。

这是错误还是我只是运气好，对于具有少于10个条目的map，它发挥了作用？

谢谢

Answer 1

js/BigInt不能作为哈希图键。

哈希图需要正确支持hashCode和equals的键。
(https://clojure.org/reference/data_structures#Maps)

-
> 返回其参数的哈希码。注意这是与=一致的哈希码
注意：这是与=一致的哈希码
> (https://cljs.github.io/api/cljs.core/hash)

现在，如果检查js/Number的哈希值，对于相同的数字它总是相同的

(hash (js/Number 4)) ;; => 4
(hash (js/Number 4)) ;; => 4

但对于js/BigInt，每次结果都不同

(hash (js/BigInt 4)) ;; => 15
(hash (js/BigInt 4)) ;; => 16

(使用在线cljs repl： http://clojurescript.net/)。

这表明哈希函数在js/BigInt上不起作用，因此当计算hashtable中的位置时...

哈希表使用哈希函数计算一个索引，也称为哈希码，将其映射到桶或槽数组中，从其中可以找到所需的值。
(https://en.wikipedia.org/wiki/Hash_table#Hashing)

计算的位置不正确（根据哈希函数，新的js/BigInt与哈希表中的js/BigInt值不同）。

它之所以能在某些hashmap中工作，是因为这两种情况下使用了不同的实现。ClojureScript为哈希表实现了更多的接口：https://cljs.github.io/api/cljs.core/#IMap

(type {0 0 1 1 2 2 3 3 (js/BigInt 4) 4 5 5 7 7 8 8}) ;; => cljs.core/PersistentArrayMap
(type {0 0 1 1 2 2 3 3 (js/BigInt 4) 4 5 5 7 7 8 8 9 9}) ;; => cljs.core/PersistentHashMap

当实现切换时，您可以看到示例：基于HASHMAP-THRESHOLD属性：https://cljs.github.io/api/cljs.core/PersistentArrayMap

有关不同实现存在的原因的更多详细信息：https://stackoverflow.com/questions/16516176/what-is-the-difference-between-clojures-apersistentmap-implementations

因此，如果哈希表较小，它就像数组一样工作，并且不使用等价值哈希，只使用等号（=）。然后，当哈希表变得更大时，首先使用哈希值来确定哈希表中的位置，然后使用等号（=）在位置处获取具体值。

大致就是这样工作的。

Comments

谢谢，这完美地解释了为什么小尺寸测试似乎工作正常。
我记得我在某个时候读到过关于Clojure的内容，但显然忘记了。

Answer 2

您可以通过实现两个核心协议来使js/BigInt与哈希表一起工作

• cljs.core/IHash
• cljs.core/IEquiv

这意味着

(extend-type js/BigInt
  IHash
  (-hash [this] ... impl ...)

  IEquiv
  (-equiv [this other] ... impl ...))

(可能在没有IEquiv的情况下工作得很好，不确定)

您可以在自己的代码中这样做。我没有对js/BigInt做任何事情，所以我不知道具体的实现会是怎样的。但应该是很容易的。您可以在cljs.core的源代码中查找其他类型的示例实现。

如果没有实现这些协议，它将使用默认实现，为js/BigInt的每个新实例分配一个唯一的id作为“哈希”。这就是为什么它在哈希表中不起作用。

Comments

感谢回答。我终于有一些时间来检查这个了。

我添加了一个简单的定义，它把 BigInt 转换为十六进制字符串，然后使用字符串哈希函数并计算其哈希值。
 
    (extend-type js/BigInt
        IHash
        (-hash  [this] (hash (.toString this 16)))
     )

我预计在哈希值冲突的情况下需要 IEquiv。稍后我会尝试检查这一点。

我通过将我的简单解决方案迁移到 Clojurescript 中的 Project Euler #14（Collatz 问题）来测试该实现，并使用包含 2168611 条记录的哈希表生成了正确的答案。注意，这个问题实际上不需要 BigInt。

---

在我的测试中，使用 `(.toString this 32)` 更快，可能是因为它需要分配更短的字符串。

在我的测试中，IEquiv 不是必需的。

(extend-protocol IHash
  js/BigInt
  (-hash [this]
    (hash (.toString this 32))))