data-structures - Clojure 集合背后的数据结构是什么？

Question

我最近在 Software Engineering Radio 上收听了Rich Hickey 的采访。在采访中，Rich 提到 Clojure 的集合被实现为树。我希望用另一种语言实现持久数据结构，并想了解集合和 Clojure 的其他持久数据结构是如何实现的。

在以下场景中，树在每个点会是什么样子？

1. 创建集合{1 2 3}

2. 创建和的{1 2 3}联合{4}

3. 创造和的{1 2 3 4}差异{1}

我想了解生成的三组（{1 2 3}、{1 2 3 4}和{2 3 4}）如何共享结构，以及如何处理“删除”。

我还想知道一个节点可能拥有的最大分支数。Rich 在采访中提到，树木很浅，所以推测分支因子大于 2。

Answer 1

您可能需要阅读 Phil Bagwell 的作品。他对数据结构的研究是 Clojure、Haskell 和 Scala 持久数据结构的基础。

Phil 在 Clojure/Conj 上有这个演讲：http ://www.youtube.com/watch?v=K2NYwP90bNs

还有一些论文：

• 快速功能列表、哈希列表、双端队列和可变长度数组
• 理想哈希树
• 更多来自菲尔这里

您还可以阅读Chris Okasaki 的Purely Functional Data Structures。这篇博客文章谈到了这本书： http: //okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

Answer 2

你真的应该阅读Clojure Programming，它非常详细地介绍了这一点，包括图片。简而言之，集合是对树的深度优先搜索。我们可以像这样展示您的示例：

(def x #{1 2 3})

x
|
| \
|\ 3
1 \
   2

(def y (conj x 4))

 x  y
 | / \
 | \   4
 |\ 3
 1 \
    2

 (def z (difference y #{1}))

 x  y
 | / \
 | \  4
 |\ 3
 1/\
z-  2

请注意，这些只是指示性的，我并不是说这正是 Clojure 内部使用的布局。这是要点。

Answer 3

我喜欢 SCdF 的绘图和解释，但如果您正在寻找更深入的内容，您应该阅读Higher-Order上关于 Clojure 数据结构的优秀系列文章。它详细解释了 Clojure 的映射是如何工作的，而 Clojure 的集合只是其映射之上的一个薄层：#{:a :b}实现为一个环绕{:a :a, :b :b}.

Answer 4

这是一个起点：https ://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashSet.java

您可以看到它是根据 PersistentHashMap 实现的。