在ClojureScript中，能否将js/BigInt用作映射键？

Question

js/BigInt支持等式测试 (= (js/BigInt 4) (js/BigInt 4)) 是真的，所以我预计可以在映射中使用它作为键（我不知道用于查找的哈希函数是什么）
但是，我发现了一些意外的行为

(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个条目的映射得到了工作？

谢谢

Answer 1

js/BigInt不能作为哈希映射键使用。

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

-
返回其参数的哈希码。注意这与=一致。
targeting
(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还原器测试： http://clojurescript.net/）。

这表明hash函数无法处理js/BigInt，因此在计算hashmap中的位置时。

散列表使用hash函数计算数组（桶或插槽）的索引，也可以称为hash码，从中可以找到所需值。
（https://en.wikipedia.org/wiki/Hash_table#Hashing）

计算的位置不正确（因为基于hash函数，新的js/BigInt与hashmap中的js/BigInt值不同）。

之所以与某些hashmap配合工作，是因为这两种情况使用了不同的实现。ClojureScript实现了更多hashmap接口： 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

您可以在以下链接中看到实现切换的示例： https://cljs.github.io/api/cljs.core/PersistentArrayMap 基于HASHMAP-THRESHOLD属性。

有关不同实现存在的原因，请参阅以下细节： https://stackoverflow.com/questions/16516176/what-is-the-difference-between-clojures-apersistentmap-implementations

因此，当hashmap很小的时候，它像数组一样工作，并且不使用 equality hash，只使用 =。然后，当hashmap变大时，首先使用hash来决定hashmap中的位置，然后使用 = 获取实际值。

这基本上是怎么工作的。

Comments

谢谢，这完美地解释了为什么在小型尺寸测试中它似乎是有效的。
我记得曾经读到过有关Clojure的东西，但我显然忘记了。

Answer 2

您可以通过实现两个使它正常工作的核心协议来使js/BigInt在hashmap中工作

• 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))))