Clojure中的assoc：内部原理解释

Question

3

这是assoc的代码：

(def assoc
 (fn assoc
   ([map key val] (. clojure.lang.RT (assoc map key val)))))

- viebel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Arthur Ulfeldt · Accepted Answer

clojure.lang.RT 是Clojure运行时的主要类。它包含了构成该语言核心的大部分方法。
assoc 对所有关联数据结构，包括向量和映射，都是O(1)的。 array-map 在前几个项中是线性的，然后将自己提升为一个hash-map，因此也是O(1)的。当然，如果需要，您可以使用非O(1)的内容来实现关联接口。
从技术上讲，在通过调用另一个映射上的assoc创建的映射或向量中访问项目的访问时间为O(log32 N)。因为这些数据结构对于大小约为2^32个项目有一个上限，所以最大树深度为6，这实际上是常数时间。

Clojure的关联数据结构在空间上都是O(nLog n)（因为它们是树）。