Implementing nonblocking thread-safe list

Question

Is it possible to implement nonblocking thread-safe list using ConcurrentHashMap as a backing where you use the index as the key and elements as the values?

Answer 1

Is it possible?

The answer is that it depends on what list functionality you need.

• If you simply want to perform array-like operations on the "list" (e.g. get or set an element at a given index), then it can be done.

• If you want do things like inserting or deleting elements, or iterating the elements of the list in order, then the operation has to be blocking, and it will typically be expensive.

To illustrate, consider the problem of inserting an element at position P. To do this, you need to change the positions of all of the existing elements at P and onwards. For each one, you need to remove the element from the hashmap, and then reinsert it. Assuming that P is chosen at random, then the renumbering is O(N) where N is the "list" length. Furthermore, that renumbering has to be done atomically, so it must block other operations ... for a considerable time.

Answer 2

Yes of course. The javadoc gives information about how to use it.
1. Operations are thread-safe: HashMap is blocked, operation is executed, HashMap is unblocked and so on
2. getter is not blocking: it retrieves the most recent update
3. you can scale your HashMap whith this function
4. Add elements with put(key, values);
5. You are looking for

    ConcurrentHashMap<Integer,String> map = new ConcurrentHashMap<Integer,String> (); //Creates a new, empty map with a default
                                  // initial capacity (16), load factor (0.75) and concurrencyLevel (16).
    map.put(map.size(),"Hello"); //put is blocking so you'll have the actual size (your index) at insertion time

Answer 3

No, as there is no way to atomically remove an element.

You could implement code to move the subsequent elements down one, but it would require some additional coding.