logo标签列表

Java不可变列表

javacachingconcurrencyimmutability
7

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

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

一种合法的读操作是返回一个包含事件 [2, 3, 4] 的迭代器。由于读操作可能是长时间运行的，我想使用一种数据结构，在每次读取尝试时都可以安全地迭代逻辑副本序列，从而防止缓存读取阻塞任何后续写入。但是，使用普通的Java ArrayList 或 LinkedList 意味着需要付出较大的开销来进行完全复制。我的问题是：是否有第三方Java库提供不可变数据结构，类似于Scala，其中修改数据结构的尝试返回一个新的不可变副本（实际上基于原始数据结构，因此复制操作非常快）？ 显然，该数据结构不能符合Java集合API，因为例如add(T)等操作需要返回新集合（而不是void）。请注意，Guava的ImmutableList几乎实现了我所需的功能：它允许您调用copyOf，其中副本通常引用原始副本（避免执行实际副本）。 不幸的是，您不能沿另一条路线添加项目到列表中并返回包括新元素的副本。感谢您的帮助。
为什么你不想创建必要的Java接口，然后在Scala中实现它呢？ - Roman
Roman - 说得有道理，但整个代码库都是用Java编写的，我不想混入第二种语言。 - Adamski
@Adamski：你确定Scala集合不会做任何“花哨”的事吗？（如果有的话，请回报）。你可以查看源代码，并在Java中复制它们所做的内容。 - Thilo
我已经阅读过Scala的“List是不可变的，并且具有常数时间的prepend和线性时间的append。” https://dev59.com/BnM_5IYBdhLWcg3ww2EQ#1241394 这听起来像是一个带有尾部共享的链表（不幸的是Java的链表不允许这样做）。 - Thilo
Guava可以满足您的需求。当您想要更新缓存时，请使用构建器模式从旧缓存创建一个新缓存，然后删除旧缓存。新缓存将重用所有旧对象，因此这是一项非常轻量级的操作。当有人想要缓存的不可变副本（或其中一个项目），请返回copyOf()，他们将获得对不可变快照的访问权限。注意，如果您正在使用线程，请确保同步缓存访问和更新方法。 - mstahl
请编辑标题，因为它具有误导性，不能描述问题的实际情况。 - Basil Bourque
7个回答
7

Functional Java以库的形式提供不可变集合，它不是一种不同的编程语言。不确定它是否符合您的需求，但值得一试。

谢谢Sanjay - 看起来Seq是我需要的。 - Adamski
3
谢谢Thilo，但据我所知，ImmutableList不允许您制作包括其他元素的逻辑副本。 - Adamski
仅限于末尾。缓存在概念上是一个有界队列（用于写入目的）。 - Adamski
@Thilo：这里有点挑剔：我是荷兰人，15岁。我想确认一下：应该是“Google Guava 有 不可变集合”吧？ - Martijn Courteaux
@Martijn。也许吧。我是德国人，我知道什么。我把Guava想象成一群人，而不是一个产品的意思。就像“警察没有发现任何证据表明有恶意行为”。 - Thilo
警察总是复数的;-) - Thilo
显示剩余2条评论
2

JDK 9引入了新的of()方法工厂。例如，您可以将不可变Set设为

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

您可以使用List执行相同的操作，例如：
List<String> stringList = List.of("A", "B", "C");

还需要一个Map：

Map<String, String> doubleMap = Map.of("key1", "val1", 
                                       "key2", "val2");
有价值且方便，但这些是用于字面量和传递特定对象。我不记得能够传递现有集合以使其不可变。如果我有错请纠正我。 - Basil Bourque
@BasilBourque 抱歉，我不确定我理解你的意思。如果您需要一个集合的不可变视图，难道不能使用“Collections.unmodifiableMap”，“Collections.unmodifiableList”和“Collections.unmodifiableSet”吗？ - JeanValjean
问题要求的是“试图修改数据结构会返回一个新的不可变副本”。这个回答虽然提供了有趣的新信息，但并没有回答问题。 - Basil Bourque
2

Guava

Google Guava可以满足你的需求。

如果您需要更新缓存，请使用Guava的构建器模式从旧缓存创建一个新缓存，然后删除旧缓存。

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

当有人想要不可变的缓存副本（或其中一个条目）时，请返回copyOf()，他们将获得对不可变快照的访问。

注意，如果正在使用线程，请确保在对象中包装列表并同步其get()和insert()方法。

您可以在Guava网站上阅读更多内容。

1

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

如果只有添加而没有删除，我认为可以使用更简单的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。不过我没有完全检查它是否是线程安全的。
1

Pure4J

通过复制Clojure持久化集合类提供不可变的集合。它可能并不完全符合您的要求，因为它是关于在（Java程序的子集上）强制执行纯函数语义。

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

1
你看过CopyOnWriteArrayList了吗？对列表的每次修改都会将所有内容复制到新的支持数组中，从而使你可能正在迭代的当前数组不受影响。
1
是的，我曾经尝试过，但不幸的是，这比使用LinkedList更糟糕，因为我的写入操作非常频繁，我将永远要复制该列表。如果写入不频繁，我肯定会采取这种方法（所以我赞同你的意见：-））。 - Adamski
哦，我明白了。那你做出了一个好决定 :) 我和道格谈过为什么比较方法会抛出UnsupportedOperationException异常，原因是排序会非常慢。 - John Vint
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接