Список неизменных Java

Question

В настоящее время я создаю кэш LRU, где мне нужно хранить последние N вставленных элементов. Элементы будут вставляться часто (т. Е. Многие операции записи), а операции чтения обычно возвращают большое количество событий всегда строго в последовательности , хотя и начинающихся в произвольной точке в кэше. Например, предположим, что кэш содержит события:

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

Допустимая операция чтения - возвращать итератор для событий [2, 3, 4].

Из-за потенциально долгоживущих операций чтения я хотел бы использовать структуру данных, в которой я могу безопасно перебирать логическую копию последовательности для каждой попытки чтения, таким образом предотвращая чтение из кэша задерживая любые последующие записи. Однако использование ванильного Java ArrayList или LinkedList подразумевает большие издержки при создании полной копии.

Мой вопрос: существуют ли какие-либо сторонние библиотеки Java, которые предоставляют неизменные структуры данных, подобные Scala, в результате чего попытки изменить структуру данных возвращают новую неизменную копию (которая фактически основана на исходных данных структура и, следовательно, операция копирования очень быстро)? Очевидно, что структура данных не может соответствовать API коллекций Java, поскольку операции, подобные add(T), должны будут возвращать новую коллекцию (а не void).

(Пожалуйста, без комментариев / ответов, ссылаясь на случай преждевременной оптимизации.)

Заранее спасибо.

Примечание

Guava's ImmutableList почти достигает того, что мне нужно: он позволяет вам звонить copyOf, где копия обычно ссылается на оригинал (избегая выполнения реальной копии). К сожалению, вы не можете пойти другим путем, добавить элемент в список и получить обратно копию, содержащую новый элемент.

Answer 1

Функциональная Java поставляется в форме библиотеки (не другого языка) и предоставляет неизменные коллекции. Не уверен, что он подойдет вам, но стоит попробовать.

Answer 2

Google Guava имеет неизменных коллекций .

Answer 3

JDK 9 имеет новые фабрики of() метода. Например. Вы можете иметь неизменный набор как

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 4

гуава

Google Guava может удовлетворить ваши потребности.

Если вы хотите обновить кэш, используйте шаблон в Guava для создания нового кэша из старого, а затем удалите старый.

Чтобы обновить кэш, создайте ImmutableList.Builder() и инициализируйте его существующим ImmutableList. Измените список через интерфейс Builder. Затем вызовите .build(), чтобы получить новый ImmutableList, и удалите старый кеш. Новый кэш будет повторно использовать все старые объекты, так что это очень легкая операция.

Когда кто-то хочет неизменную копию кэша (или один из его элементов), верните copyOf (), и он получит доступ к неизменяемому снимку.

Предостережение: если вы работаете с потоками, убедитесь, что вы завернули список в объект и синхронизировали его методы get () и insert ().

Вы можете узнать больше на сайте Гуавы .

Answer 5

Похоже, что вы хотите реализовать здесь односвязный список, который затем может использоваться различными объектами-обертками.Вы когда-нибудь хотите удалять элементы или добавляете только новые?

Если есть только добавление и удаление, я предполагаю более простой вариант 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 6

Вы смотрели на CopyOnWriteArrrayList ?Каждая мутация в списке будет копировать все содержимое в новый резервный массив, оставляя текущий массив, который вы можете повторять, без изменений.

Answer 7

Pure4J

Предоставляет неизменные коллекции через копии классов постоянных коллекций Clojure. Это может быть не совсем то, что вам нужно, поскольку речь идет о применении чисто функциональной семантики (подмножеств) Java-программ.

С другой стороны, он имеет гарантии неизменности как для элементов, так и для коллекций. Когда вы добавляете / удаляете элемент из коллекции, вы получаете новую коллекцию, а оригинал остается неизменным.