不可变集合实现

Question

关于不可变集合,我有一个普遍的问题.我将使用Java作为参考实验室,因为我最了解它.

首先,是否有一种确保不变性的一般方法？我的意思是,是否应该复制整个集合,进行更改然后返回新对象？有没有更复杂,更通用的方法？

更进一步,那些"明显的"(对我来说)可变的集合,比如树？通常它们被实现为具有N个子节点的节点.在这种情况下,您如何保证不变性？递归地克隆和复制所有引用？

根据以上内容,我想知道这些集合的最佳方法是什么:

1. List - 基于数组,我们在进行更改之前会复制它？
2. 队列 - 前面和后面的两个数组,在返回之前克隆？基于bode的实现怎么样？
3. 树
4. Hashmap - 复制存储桶数组以及所有冲突列表？
5. 组

非常感谢您的回复.

Answer 1

令人高兴的是,大部分内容已经为您完成,请查看包含ImmutableCollection,ImmutableList,ImmutableSet,ImmutableMap等的google guava.

通过阻止这些类的子类(通过使它们成为最终类,或使它们的构造函数成为私有)来确保不变性.

当您从可变集合中创建不可变集合时,将复制可变集合中的数据,然后不允许所有变异操作 - 它们将抛出异常(UnsupportedOperationException例如).

出于性能原因,番石榴库将尽力不复制数据(如果不需要).例如,如果你已经有了一个ImmutableMap,并且创建了一个新的ImmutableMap.copyOf(theOtherImmutableMap),那么没有数据被复制,因为我们已经知道另一个地图是不可变的,所以可以对相同的数据进行两次引用.