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

返回 null

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

这是缺陷还是我只是运气好，因为对于少于 10 个条目的映射它工作了？

谢谢

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，因此在计算在哈希表中的位置时。

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

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

它在某些哈希表中能正常工作是因为这两种情况使用了不同的实现。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

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

关于为什么存在不同实现的一些详细信息：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。我将稍后尝试检查这一点。

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

---

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

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

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