在ClojureScript中是否可以将js/BigInt用作字典键？

Question

js/BigInt支持等号测试（= (js/BigInt 4) (js/BigInt 4)）为true，因此我预计可以使用它作为字典中的键（我不知道用于查找的哈希函数是什么）
然而我发现了意外的行为

(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

您可以在此处查看当实现改变时的示例：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))))