Java 不可变列表

Question

我目前正在构建一个 LRU 缓存，我需要在其中存储最后 N 个插入的项目。项目将被频繁插入（即许多写入操作），并且读取操作通常会返回大量事件始终严格按顺序，尽管从缓存中的任意点开始。例如，假设缓存包含事件：

[1, 2, 3, 4, 5, 6]

合法的读取操作是返回事件 [2, 3, 4] 上的迭代器。

由于读取操作可能是长期存在的，我想使用一种数据结构，在其中我可以安全地迭代每次读取尝试的序列的逻辑副本，从而防止缓存读取停滞任何后续写入。但是，使用普通 Java ArrayList 或 LinkedList 意味着制作完整副本的开销很大。

我的问题：是否有任何第 3 方 Java 库提供类似于 Scala 的不可变数据结构，尝试修改数据结构会返回一个新的不可变副本（实际上是基于原始数据结构和因此复制操作非常快）？显然，数据结构不符合 Java Collections API，因为像 add(T) 这样的操作需要返回新集合（而不是 void）。

（请不要评论/回答将此视为过早优化的情况。）

提前致谢。

注意

Guava 的 ImmutableList 几乎达到了我的需要：它允许您调用 copyOf ，其中副本通常引用原始副本（避免执行实际副本） 。不幸的是，您不能采取其他方式将项目添加到列表中并取回包含新元素的副本。

Answer 1

函数式 Java 以库（而不是不同的语言）的形式出现，并提供不可变的集合。不确定它是否适合您的需求，但值得一试。

Answer 2

Google Guava 具有 不可变集合。

Answer 3

Guava

Google Guava 可以满足您的需求。

当您想要更新缓存时，请使用 Guava 的构建器模式从旧缓存创建新缓存，然后删除旧缓存。

要更新缓存，请创建一个 ImmutableList.Builder() 并使用现有的 ImmutableList。通过Builder界面修改列表。然后调用.build()来获取新的ImmutableList，并删除旧的缓存。新的缓存将重用所有旧的对象，因此这是一个非常轻量级的操作。

当有人想要缓存（或其项目之一）的不可变副本时，返回 copyOf()，他们将可以访问不可变的快照。

警告，如果您正在使用线程，请确保将列表包装在一个对象中并同步它的 get() 和 get() 。 insert() 方法。

您可以访问Guava 网站了解更多信息。

Answer 4

JDK 9 有新的 of() 方法工厂。例如，您可以有一个 immutable Set 因为

Set<Integer> intSet = Set.of(1, 2, 3);

您可以对列表执行相同的操作，例如

List<String> stringList = List.of("A", "B", "C");

和 Map：

Map<String, String> doubleMap = Map.of("key1", "val1", 
                                       "key2", "val2");

Answer 5

您看过 CopyOnWriteArrrayList 吗？对列表的每次更改都会将所有内容复制到新的支持数组中，而您可能正在迭代的当前数组不受影响。

Answer 6

看起来您想在这里实现一个单链表，然后可以由不同的包装对象共享。您是否想删除元素，或者只添加新元素？

如果只添加而不删除，我想可以使用 CopyOnWriteArrayList 的更简单的变体，它只在旧数组已满时才进行复制。然后，sublist() 方法将简单地创建一个新的包装对象。

/**
 * A list which only supports appending objects.
 */
public class OnlyAppendingList<E> extends AbstractList<E> {

    private Object[] data;
    private int len;

    public int size() {
        return this.len;
    }

    public E get(int index) {
        if(index >= this.len)
           throw new IndexOutOfBoundsException(index + " >= " + this.len);
        @SuppressWarnings("unchecked")
        E res = this.data[index];
        return res;
    }

    public boolean add(E element) {
        if(len == data.length) {
             this.resize();
        }
        this.data[this.len] = element;
        this.len++;
        return true;
    }

    private void resize() {
        this.data = Arrays.copyOf(data, data.length * 2 +2);
    }

    public void add(int index, E element) {
       if(index > this.len) {
          throw new IndexOutOfBoundsException(index + " > " + len);
       }
       if(index < this.len) {
           throw new UnsupportedOperationException("we only support appending, not insertion!");
       }
       this.add(element);
    }


    /**
     * Returns an immutable sublist of this list.
     */
    public List<E> subList(final int fromIndex, final int toIndex) {
        // TODO: bounds checks
        return new SubList<E>(this.data, fromIndex, fromIndex - toIndex);
    }

    private static class SubList<E> extends AbstractList<E> {
        private Object[] data;
        private int start;
        private int len;

        SubList(Object[] data, int start, int len) {
            this.data = data; this.start = start; this.len = len;
        }

        public int size() {
            return this.len;
        }

        public E get(int index) {
            if(index >= this.len)
               throw new IndexOutOfBoundsException(index + " >= " + this.len);
            if(index < 0)
               throw new IndexOutOfBoundsException(index + " < 0");

            @SuppressWarnings("unchecked")
            E res = this.data[index + start];
            return res;
        }
        public List<E> subList(int from, int to) {
            // TODO: bounds check
            return new SubList(data, start + from, to - from);
        }
    }
}

我认为，如果这是由多个线程修改的，则应该使 add 方法同步，并使 len 变量 volatile 同步。 （我没有完全检查它是否是线程安全的。）

Answer 7

Pure4J

通过 Clojure 持久集合类的副本提供不可变集合。它可能不完全是您所追求的，因为它是关于在 java 程序（子集）上强制执行纯函数语义。

另一方面，它对元素和集合都有不变性保证。当您从集合中添加/删除元素时，您会得到一个新集合，并且原始集合保持不变。