在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引擎进行测试的。

这是否是一个bug，还是我只是运气好，在少于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重放器测试：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与哈希表一起工作的两个核心协议来让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源文件中查找其他类型实现的例子。

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

Comments

谢谢你的回答。我终于有时间检查这个了。

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

我相信在哈希值冲突的情况下需要IEquiv。我稍后将会检查这一点。

我通过将我的简单解决方案移植到Clojurescript的Project Euler #14（柯尔萨茨问题）来测试了这个实现，并且它使用了含有2168611个条目的哈希表，产生了正确的答案。注意，这个问题实际上不需要BigInt。

---

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

在我的测试中，IEquiv也不必要。

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