在ClojureScript中能否使用js/BigInt作为Map键？

Question

js/BigInt支持相等性测试 (= (js/BigInt 4) (js/BigInt 4))返回true，因此我本以为可以使用它作为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引擎进行了测试。

这是不是bug，或者是我在地图键少于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，因此在计算 hashmap 中的位置时

哈希表使用哈希函数计算一个索引，也称为哈希码，将其映射到桶（槽）数组中，从而可以找到所需值。
(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

您可以在此处看到实现切换的示例：基于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))))