Directly accessible Java data structure

Question

I have the following situation:

• A data structure that can only be extended (I only ever add things to the tail)
• I need to be able to track which items I already have (I have an index, and ideally I want to start moving the list again from that particular item)
• I would like reads never to be blocked, and adding a new element only blocks the tail of the queue, not the entire queue

This is a structure that is heavily modified by multiple threads.

What would be the best data structure for this?

ArrayList . This would be ideal to be able to directly access the last item, apparently using an index, but this leads to the exclusion of concomitant modifications. I could make it synchronized, but would like to avoid blocking (or any blocking separately from the very last element, as this is the only one where there may be simultaneous entries to add new elements)

ConcurrentLinkedQueue . This would solve my concurrency problem, but the problem is that I would need to keep the current iteration position, not the integer index. This has a problem that it returns a weakly matched iterator, which does not guarantee the return of new objects that have been added to the list since the iterator was created (source: javadoc)

ConcurrentHashMap with an index in the form of keys. This has the advantage that I can directly access the data corresponding to the correct index, but there is a problem that there is no getNext statement that will allow me to efficiently move elements from the index, index + 1, etc.

Vectors . This would solve most of my problems by resolving something that would not throw simultaneous modification exceptions and allow direct access. However, given that all methods are synchronized, performance is poor compared to arraialists. Given that I only want to expand the structure, and not insert records in the middle, I do not want to go for this heavy weight solution, where reading also suffers from a performance hit (whereas, given my usecase, the element index never changes, so there is no need to synchronize readings that are not tail)

Custom data structure : save the array of objects that I want to save, and the pointer to the tail of this array (the last set of elements), when inserting a new object, lock the tail and the object that the tail points to. When an object exceeds its current size, the lock operation changes.

What would be a better strategy / any other more efficient implementation?

Answer 1

The CopyOnWriteArrayList structure may solve your problem (java.util.concurrent).

• CopyOnWriteArrayList is thread safe because all mutation operations are implemented by creating a copy of the list.

• The ConcurrentModificationException problem is resolved because the array does not change when retrying. The so-called snapshot style iterator uses a reference to the state of the array when creating the iterator.

• If you read much more than records, use CopyOnWriteArrayList , otherwise use Vector .

• Vector introduces a slight synchronization delay for each operation when CopyOnWriteArrayList has a longer delay for writing (due to copying), but without a delay for reading.

• Vector requires explicit synchronization when you iterate (so write operations cannot be performed at the same time), CopyOnWriteArrayList does not work.

Answer 2

This is very similar to the fact that you need a dispatcher or just in words that are queue-free. I would like to add an example here, but yesterday I started working on it. I can also tell you how this works, or you can read a much better explanation here:

The general idea is that it is completely blocked, it uses only CAS registers (in java AtomicXXX). I just fell in love with this idea.

Lmax

Answer 3

In this I came to the same solution as @MissingNumber.

Use ConcurrentHashMap as backup data structure:

• non-blocking-reads
• thread safe add

To add random access by index, use AtomicInteger to support the index and place it as a key to extract map values.

 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(); } } 

Answer 4

Like sk2212 , I think java.util.Vector matches your three points.

• Vectors can be expanded using the add method, which adds items to the end of the list.
• Vectors have a get(index) method to get(index) a specific element at a specific index.
• Vectors are thread safe: java Vector and Thread Security http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Answer 5

ConcurrentHashMap with an index, since keys can solve your problem, but you need to do more work for this.

Like the following pseudo code.

 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; } 

Therefore, this should solve all your problems.

Concurrency Framework takes care.

Indexing Keys are your indexes.

Iteration , with this code, if you have an index, you can use

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

All you have to do is define a custom object and write the constructor accordingly with care.

Hope this helps you.

Answer 6

ArrayList. This would be ideal to be able to directly access the last item, apparently using an index, but this leads to the exclusion of concomitant modifications. I could make it synchronized, but would like to avoid blocking (or any blocking separately from the very last element, as this is the only one where there may be simultaneous entries to add new elements)

You can use a temporary list to add objects, and when unlocking the read, you add the contents of tmpList to the ArrayList.

Answer 7

I am going to suggest ConcurrentSkipListSet because:

1) It is at the same time.

2) This is a Set .

3) It is also a NavigableSet , thus also a SortedSet .

This gives you great flexibility, most of which you probably won't need. But besides “You can’t add elements that already exist” (which I don’t know if the problem is or good), it seems to satisfy all your requirements.

Answer 8

Do you need to use a single data structure? What if you used two - one for the "active" part of the list, and the other for the list of "items you saw"? You can use Vector for the "active" part and a kind of manager that periodically moves items to the "items you saw" list.