17

我试图弄清楚 PersistentHashMap、PersistentArrayMap、PersistentTreeMap 和 PersistentStructMap 之间的区别。

另外,如果我使用{:a 1}它,它会给我一个 PersistentArrayMap,但是如果我给它对象或键以外的东西,它可以更改为其他任何一个吗?

4

2 回答 2

18

您列出的四个实现分为三组:

  1. "literal" :PersistentArrayMapPersistentHashMap: 处理映射字面量时使用的基本映射类型(尽管构造函数也可用于处理重复键的不同行为——在 Clojure 1.5.x 中,当发现重复键时,构造函数会抛出异常,构造函数像左一样工作-to-right 重复conj;这种行为一直在从一个版本演变到另一个版本)。当超过一定数量的条目(9 IIRC)时,数组映射被提升为哈希映射。存在数组映射是因为它们对于小映射更快;它们还与哈希映射不同,因为它们在提升到哈希映射之前按插入顺序保留条目(您可以使用clojure.core/array-map获得任意大的数组映射,如果你真的知道你会从插入顺序遍历中受益,并且映射不会太大,可能会超过通常的阈值,这可能会很有用;注意。这样一个超大数组映射的后续assoc将返回一个哈希映射)。数组映射使用键和值交错的数组;PHM 使用 Phil Bagwell 的哈希数组映射树的持久版本,具有用于哈希冲突的单独链接以及用于大部分空节点和至少半满节点的单独节点类型,并且很容易成为 Clojure 中最复杂的数据结构。

  2. sortedPersistentTreeMap实例仅由特殊请求创建(调用sorted-mapor sorted-map-by)。它们被实现为红黑树,并以特定顺序维护条目,如果使用创建,则由默认compare比较器指定,如果使用创建,则由sorted-map用户提供的比较器指定sorted-map-by

  3. 特殊用途,可能已弃用PersistentStructMap不经常使用,并且大多被视为已弃用以支持记录,尽管我实际上现在不记得是否有过正式的弃用通知。最初的目的是为地图提供对某些常用键的特别快速访问。这现在可以在使用关键字进行字段访问时通过记录来完成(关键字位于运算符位置: (:foo instance-of-some-record-with-field-foo)),但重要的是要注意记录不是=具有相同条目的常规映射。

所有这四种内置映射类型都属于同一个“相等分区”,也就是说,当(且仅当)它们包含相同的键(由 Clojure 的=) 具有相同的对应值。上面 3. 中提到的记录是类似映射的,但每种记录类型都形成了自己的相等分区。

于 2013-05-13T07:23:05.747 回答
5

它们是持久映射的不同实现(它们都是扩展的APersistentMap)。因此,a PersistentArrayMap使用数组作为底层数据结构来实现持久映射,类似地,其他实现使用不同的底层数据结构。

不同实现的原因是它们在不同情况下提供不同的好处(因为实现的效率取决于底层数据结构)。

从开发人员的角度来看,它是抽象出来的,因此您不应该直接使用它们,而是使用APersistentMap抽象类或IPersistentMap接口(以防某些特定情况需要进行一些类型检查等)。

根据地图中元素的数量,使用各种实现。

(type (into {} (map #(-> [% %]) (range 5))))
=> PersistentArrayMap
(type (into {} (map #(-> [% %]) (range 10))))
=> PersistentHashMap
于 2013-05-13T06:55:10.933 回答