java不可变集合的实现

Question

我有一个关于不可变集合的一般性问题。我将使用Java作为我最熟悉的参考语言

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

再进一步讲，“显而易见的”（对我来说）可变集合（如树）又如何呢？通常，它们被实现为具有N个子节点的节点。在这种情况下，您如何确保不变性？是否以递归方式克隆和复制所有引用

根据以上内容，我想知道什么是这些收藏的最佳方式：

1. 在进行更改之前，我们将复制哪些基于列表的数组
2. 队列-前后两个阵列，返回前克隆？那么基于bode的实现呢
3. 树木
4. Hashmap-复制bucket数组以及所有冲突列表
5. 设置

非常感谢您的回复

Answer 1

Clojure包含这样的不可变（或持久）collections

它提供了您所关注的所有集合，并通过构造支持变异：简单地说，添加或删除新元素将返回一个新集合，它通常通过巧妙地使用Trie类型的数据结构来重用旧集合的大部分

就其本身而言，它们不适合在纯Java中使用——它们是为在Clojure中使用而设计的

Pure4j是将这些（以及Clojure提倡的不可变/基于值的样式）移植到Java语言的尝试。这可能就是你想要的

免责声明：我是Pure4J的开发者

Answer 2

我假设您的目的是了解不可变集合如何在函数式语言（如haskell等）的框架内工作。其思想是所有集合都是不可变的和最终的，从而避免了所有多线程在易变性、同步等方面的问题，但仍然允许您添加、删除和修改它们，就好像它们是可变的一样

我看到的最好的例子是Clojure的源代码。它是一种类似lisp的语言，因此将不可变集合作为核心功能处理。我强烈建议大家看看clojure中的集合是如何实现的，因为它们肯定会回答您的许多问题。可能有些事情太复杂了（我还是不太明白）。见here祝你好运

Answer 3

就Java而言，Collections实用程序类是您的朋友。我建议使用给定的API，而不是手动执行这些操作。特别是看不可变和不可修改的方法

例如，就不可变而言，有：

<T> List<T>
emptyList() 
          Returns the empty list (immutable).
static
<K,V> Map<K,V>
emptyMap() 
          Returns the empty map (immutable).
static
<T> Set<T>
emptySet() 
          Returns the empty set (immutable).

对于不可修改的，您有：

static
<T> Collection<T>
unmodifiableCollection(Collection<? extends T> c) 
          Returns an unmodifiable view of the specified collection.
static
<T> List<T>
unmodifiableList(List<? extends T> list) 
          Returns an unmodifiable view of the specified list.
static
<K,V> Map<K,V>
unmodifiableMap(Map<? extends K,? extends V> m) 
          Returns an unmodifiable view of the specified map.
static
<T> Set<T>
unmodifiableSet(Set<? extends T> s) 
          Returns an unmodifiable view of the specified set.
static
<K,V> SortedMap<K,V>
unmodifiableSortedMap(SortedMap<K,? extends V> m) 
          Returns an unmodifiable view of the specified sorted map.
static
<T> SortedSet<T>
unmodifiableSortedSet(SortedSet<T> s) 

下面还有一些其他的和一些策略可以实施，但我将从这里开始

Answer 4

令人高兴的是，这些已经为您完成了很多，请查看google guava，其中有ImmutableCollection、ImmutableList、ImmutableSet、ImmutableMap等等

通过防止这些类的子类（使它们成为最终类或使它们的构造函数成为私有类）来确保不变性

当您从可变集合创建不可变集合时，将复制可变集合中的数据，然后不允许所有突变操作-它们将抛出异常（UnsupportedOperationException）

出于性能原因，guava库将尽最大努力不复制数据（如果不需要）。例如，如果您已经有了一个ImmutableMap，并使用ImmutableMap.copyOf(theOtherImmutableMap)创建了一个新的映射，那么不会复制任何数据，因为我们已经知道另一个映射是不可变的，所以可以对同一数据有两个引用