Collections杂谈(一)

bennyhuo

发布于 2020-02-20 13:41:53

7870

发布于 2020-02-20 13:41:53

文章被收录于专栏：BennyhuoBennyhuo

Mutable & Immutable

谈及到"可变"与"不可变"，必然绕不开 var和 val这两个关键字，用Java来解释的话，前者是"variable"，后者是"final"。final对于Java开发者来说并不陌生，但也必然说不上"常用"，可在Kotlin里其地位却上升为定义变量的"关键词"，这也说明"可变"与"不可变"的概念已经深刻在Kotlin的基因里了。

因此在Kotlin里，开发者最惦记的Collections同样划分为"可变集合"(Mutable Collections)和"不可变集合"(Immutable Collections)。但这个Immutable是真的不可变吗？这里以list举一个例子：

fun main() {
    // 注意，这里不能写listof(1)，否则会被优化为SingletonList类型，其set方法是没有被实现的
    val l = listOf(1, 2)
    try {
        (l as MutableList).add(0, 2)
    } catch (e: Exception) {
        println(e)
    }
    try {
        (l as MutableList)[0] = 2
    } catch (e: Exception) {
        println(e)
    }
    l.forEach { println(it) }
}

运行结果是：

这里 ImmutableList可以强转为 MutableList并修改其中的元素。

Kotlin代码要实现100%兼容Java，则无论穿的衣服是 MutableList还是 ImmutableList，卸下伪装后都只能是Java的 List。

可以验证一下：

fun main() {
    println(TypeIntrinsics.isMutableList(listOf(1, 2)))
    println(TypeIntrinsics.isMutableList(mutableListOf(1, 2)))
}

运行结果是

你觉得堂堂JetBrains会没想到去实现一个真正的Immutable Collections？那当然不可能了，毕竟Kotlin被寄予了厚望。这个项目就是kotlinx.collections.immutable

完！剩下的自己去翻文档吧。

真正的Immutable

整个库并不复杂（因为还在开发中），但也不简单，因为相比于"可变"，"不可变"要考虑的地方更多，暂且抛开这点不谈，先来简单看看库的用法。

由于最新版本 ImmutableList接口分为 ImmutableList和 PersistentList两个接口，其含义也有所区别，因此以最新版本为准

由于要考虑到易用易理解，其提供的API和"可变集合"高度一致。

// Group A
val immutableList = (0..5).toImmutableList()
val immutableSet = (0..5).toImmutableSet()
val immutableMap = mapOf(0 to 1, 2 to 3).toImmutableMap()

// Group B
val persistentList =(0..5).toPersistentList()
val persistentSet = (0..5).toPersistentSet()
val persistentMap = mapOf(0 to 1, 2 to 3).toPersistentMap()
val persistentHashMap = mapOf(0 to 1, 2 to 3).toPersistentHashMap()

补充：还有 PersistentOrderedMap和 PersistentOrderedSet类，对应Java的 LinkedHashMap和 LinkedHashSet

那么A组和B组有什么区别呢？

// 仍然以list举例
val immutableList2 = immutableList + 6
val persistentList2 = persistentList + 6

// 输出：
// 8123456
(immutableList2 as MutableList)[0] = 8
immutableList2.forEach { print(it.toString()) }

// 下面这一行会标红(没有set方法)
immutableList2[0] = 8
// 下面这一行运行时会报错，因为不能强转
(persistentList2 as MutableList<Int>)[0] = 8
persistentList2.forEach { println(it.toString()) }

明显库里面没有为 ImmutableList重载运算符（可能是这个接口后续仍会变动，因为 ImmutableXXOf等扩展方法已经标记 Deprecated了），其加法执行运算后返回的是标准的 List。因此库里A组的方式都应该无视掉…

PersistentList连元素都不能变了！可…除了加法运算…肯定还支持减法运算。难道只是数组内元素不可变，但数组本身是可变的？下面做一个试验：

// A
val mutableList = (0..5).toMutableList()
Thread {
   mutableList.forEach {
       println(it.toString())
       Thread.sleep(1000)
   }
}.start()

Thread {
    Thread.sleep(2000)
    mutableList.removeAt(0)
}.start()

// B
val persistentList =(0..5).toPersistentList()
Thread {
    persistentList.forEach {
        println("thread 1: $it")
        Thread.sleep(1000)
    }
}.start()

Thread {
    Thread.sleep(2000)
    persistentList.removeAt(0).forEach {
        println("thread 2: $it")
    }
    Thread.sleep(2000)
    persistentList.removeAt(0).forEach {
        println("thread 2: $it")
    }
}.start()

A毫无意外报错了。而B的thread 1输出是012345，thread 2输出的是12345012345。这说明数组也是不可变，在其之上"增删"都会生成新的数组。并且由于数组的"不可变"，因此其线程安全。

共享的数据

在翻看源码实现的时候，发现了一个比较奇怪的地方，那就是其数据的保存方式。下面同样以 PersistentVector为例。

直接上图：

当tail的叶子节点数量超到32个时，则会copy成为root下的叶子节点，root的每一层最大叶子数量也是32个。示意图如下：

注意这里PersistentVector A和PersistentVector B红色框标注部分是共享的数据。这里可以以一个例子证明：

// 以下代码需要修改源码，暴露相关方法才能运行
// Block A，输出:10086123456789101112131415161718192021222324252627282930313233
val immutableList = (0..32).toPersistentList() as PersistentVector
val root = immutableList.root
val newImmutableList = immutableList.add(33)
root[0] = 10086
newImmutableList.forEach {
    print(it.toString())
}

也就是从一份 PersistentVector不断衍生出来的所有列表，都将有一部分是共享的，这将能节省不少内存，同时能让用户在极小负担下对列表进行修改。

PersistentHashMap和 PersistentHashSet等相关实现也有类似的特性。