Прямо доступная структура данных Java

У меня следующая ситуация:

Структура данных, которую можно только продлить (я только когда-либо добавить вещи в хвост)
Мне нужно уметь отслеживать, какие элементы у меня уже есть (у меня есть индекс, и в идеале я хочу начать перемещая список снова из этого конкретного элемента)
Я бы хотел, чтобы чтения никогда не блокировались, и добавление новый элемент только блокирует хвост очереди, а не вся очередь

Это структура, которая сильно изменена несколькими потоками.

Какая была бы лучшая структура данных для этого?

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

ConcurrentLinkedQueue. Это решило бы мою проблему concurrency, но проблема в том, что мне нужно было бы сохранить текущую позицию итерации, а не целочисленный индекс. У этого есть проблема, что он возвращает слабо согласованный итератор, который не гарантирует возврат новых объектов, которые были добавлены в список с момента создания итератора (source: javadoc)

ConcurrentHashMap с индексом в виде ключей. Это имеет то преимущество, что я могу напрямую получить доступ к данным, соответствующим правильному индексу, но есть проблема, что нет оператора getNext, который позволит мне эффективно перемещать элементы из индекса, индексировать + 1 и т.д.

Векторы. Это позволило бы решить большинство моих проблем, разрешив что-то, что не будет бросать исключения одновременной модификации и допускать прямой доступ. Однако, учитывая, что все методы синхронизированы, производительность плоха по сравнению с аррайалистами. Учитывая, что я только хочу расширить структуру, а не вставлять записи посередине, я не желаю идти на это тяжелое весовое решение, где чтение также страдает от хита производительности (тогда как, учитывая мой usecase, индекс элемента никогда не меняется, поэтому нет необходимости синхронизировать чтения, которые не являются хвостом)

Пользовательская структура данных: сохраните массив объектов, которые я хочу сохранить, и указатель на хвост этого массива (последний набор элементов), при вставке нового объекта, заблокируйте хвост и объект, на который указывает хвост. Когда объект превышает свой текущий размер, операция блокировки изменяется.

Какая была бы лучшая стратегия/любая другая более эффективная реализация?

Ответ 1

Структура CopyOnWriteArrayList может решить вашу проблему (java.util.concurrent).

CopyOnWriteArrayList является потокобезопасным, потому что все мутативные операции реализованы путем создания копии списка.
Проблема ConcurrentModificationException устраняется, поскольку массив не изменяется при повторе. Так называемый snapshot style iterator использует ссылку на состояние массива при создании итератора.
Если вы читаете гораздо больше, чем записи, используйте CopyOnWriteArrayList, иначе используйте Vector.
Vector вводит небольшую задержку синхронизации для каждой операции, когда CopyOnWriteArrayList имеет более длительную задержку для записи (из-за копирования), но без задержки для чтения.
Vector требуется явная синхронизация, когда вы выполняете итерацию (так что операции записи не могут выполняться одновременно), CopyOnWriteArrayList не работает.

Ответ 2

Это очень похоже на то, что вам понадобится диспетчер или просто в словах, свободных от очереди. Хотел бы я добавить пример здесь, но вчера я начал работать над этим. Я также могу рассказать вам, как это работает, или вы можете прочитать здесь гораздо лучшее объяснение:

Общая идея заключается в том, что он полностью блокирован, он использует только регистры CAS (в java AtomicXXX). Я просто влюбился в эту идею.

LMAX

Ответ 3

В этом я пришел к тому же решению, что и @MissingNumber.

Использовать ConcurrentHashMap в качестве структуры данных резервного копирования:

non-blocking-reads
потокобезопасное добавление

Чтобы добавить произвольный доступ по индексу, используйте AtomicInteger для поддержки индекса и поместите его как ключ для извлечения значений карты.

public class ConcurrentListMap {

  private final ConcurrentHashMap<Integer, Object> backingMap;
  private final AtomicInteger index;

  public ConcurrentListMap() {
    backingMap = new ConcurrentHashMap();
    index = new AtomicInteger(0);
  }

  public int append(final Object value) {
    final int newIndex = index.incrementAndGet();
    backingMap.put(newIndex, value);
    return newIndex;
  }

  public Object get(final int entry) {
    return backingMap.get(entry);
  }

  public int getTailIndex() {
    return index.get();
  }
}

Ответ 4

Как sk2212, я думаю, что java.util.Vector соответствует вашим трем пунктам.

Векторы могут быть расширены с помощью метода add, который добавляет элементы в конце список.
Векторы имеют метод get(index) для получения конкретного элемента при определенном индексе.
Векторы являются потокобезопасными: java Безопасность векторов и потоков http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Ответ 5

ConcurrentHashMap с индексом, поскольку ключи могут решить вашу проблему, но вам нужно сделать больше работы для этого.

Подобно следующему псевдокоду.

Map<Integer , ConfiguredObject > myMap = new ConcurrentHashMap<Integer,ConfiguredObject >();

class ConfiguredObject 
{
   YourObject Object;// the object which you want to map for map[key];
   ConfiguredObject Next;//the object which you want to map for map[key+1];
   ConfiguredObject Previous;//the object which you want to map for map[key-1];
   YourObject NextObject;
   YourObject PrevObject;
}

Таким образом, это должно решить все ваши проблемы.

Concurrency Framework заботится.

Индексирование Ключи - это ваши индексы.

Итерация, с этим кодом, если у вас есть индекс, вы можете использовать

myMap.get(key).Next ;
myMap.get(key).Previous ;

Все, что вам нужно сделать, это определить настраиваемый объект и написать конструктор соответственно с осторожностью.

Надеюсь, это поможет вам.

Ответ 6

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

Вы можете использовать временный список для добавления объектов и при разблокировке чтения, вы добавляете содержимое tmpList в ArrayList.

Ответ 7

Я собираюсь предложить ConcurrentSkipListSet, потому что:

1) Это одновременно.

2) Это a Set.

3) Это также NavigableSet, таким образом, также a SortedSet.

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

Ответ 8

Вам нужно использовать единую структуру данных? Что делать, если вы использовали два - один для "активной" части списка, а другой для списка "элементы, которые вы видели"? Вы можете использовать Vector для "активной" части и своего рода менеджера, который периодически перемещает элементы в список "элементы, которые вы видели".