不可变集合实现

Question

不可变集合实现

javacollectionsimmutability

3

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

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

进一步说，那么像树这样的“显而易见”的（对我来说）可变集合怎么办？通常它们被实现为具有N个子节点的节点。在这种情况下，如何确保不可变性？递归克隆和复制所有引用？

接下来，我想知道对于这些集合，什么是最好的方法：

1. 基于数组的列表 - 在进行更改之前复制它？ 2. 队列 - 为前面和后面分别使用两个数组，在返回之前进行克隆？基于节点的实现呢？ 3. 树 4. 哈希映射 - 复制桶数组以及所有冲突列表吗？ 5. 集合

非常感谢您的回答。

- Bober02

4个回答

2

在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)

除此之外还有其他策略，您可以在此基础上进行实施，但我建议从这里开始。

- TechTrip

0

Clojure包含不可变（或持久）集合。

它提供了您需要的所有集合，并支持通过构建进行突变：简单地说，添加或删除新元素会返回一个新的集合，通常情况下，它通过巧妙地使用Trie类型的数据结构来重用旧集合的大部分内容。

单独使用这些集合在纯Java中并不适合 - 它们是为Clojure设计的。

Pure4j是将这些集合（以及Clojure所倡导的不可变/值类型风格）移植到Java语言的尝试。这可能是您需要的。

免责声明：我是Pure4J的开发人员

- Rob Moffat

0

我假设你的意图是理解在函数式语言（如Haskell等）框架中不可变集合的工作原理。其思想是所有集合都是不可变和最终的，从而避免了与可变性、同步等相关的多线程陷阱，但仍然允许您添加、删除和修改，就像它们是可变的一样。

我见过的最好的例子是Clojure的源代码。这是一种类似于Lisp的语言，因此将不可变集合作为核心特性处理。我强烈建议查看Clojure中集合的实现方式，因为它们肯定会回答你的许多问题。可能有些东西会太复杂（我仍然几乎不理解tries）。请参见这里，祝你好运。

- Java Drinker

为什么它们是final的？为了防止他人在其上放置可变方法吗？ - Bober02

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- daveb · Accepted Answer

非常高兴，其中很大部分已经为您完成了，可以查看Google Guava，它拥有ImmutableCollection、ImmutableList、ImmutableSet、ImmutableMap等等。

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

当您从可变集合创建不可变集合时，可变集合中的数据将被复制，然后禁止所有更改操作——它们会抛出异常（例如UnsupportedOperationException）。

出于性能考虑，如果不需要复制数据，Guava库会尽力避免复制。例如，如果您已经拥有一个ImmutableMap，并使用ImmutableMap.copyOf(theOtherImmutableMap)创建一个新的ImmutableMap，则不会复制数据，因为我们已经知道其他映射是不可变的，拥有两个对同一数据的引用是可以的。