What Java Data Structure/Solution would best fit these requirements?

Question

I need a java data structure/solution that meets these requirements. What best fits these?

1) Object's insertion order must be kept

2) Object's must be unique (These are database objects that are uniquely identified by a UUID).

3) If a newer object with the same ID is added, the older version of the object should be over-written/removed

4) The Solution should be accessible by many threads.

5) When the first object added to the Structure is read/used, it should be removed from the data structure

Answer 1

There are a couple of possibilities here. The simplest might be to start with a LinkedHashSet. That will provide you with the uniqueness and predictable ordering that you require. Then, you could wrap the resulting set to make it thread-safe:

Set<T> s = Collections.synchronizedSet(new LinkedHashSet<T>(...));

Note: Since a Set doesn't really define a method for retrieving items from it, your code would have to manually invoke Set.remove(Object).

Alternatively, you could wrap a LinkedHashMap, which does provide a hook for the delete-on-read semantics you require:

class DeleteOnReadMap<K, V> implements Map<K, V> {

    private Map<K, V> m = new LinkedHashMap<K, V>();

    // implement Map "read" methods Map with delete-on-read semantics
    public V get(K key) {
        // ...
    }
    // (other read methods here)

    // implement remaining Map methods by forwarding to inner Map
    public V put(K key, V value) {
        return m.put(key, value);
    }
    // (remaining Map methods here)
}

Finally, wrap an instance of your custom Map to make it thread-safe:

Map<K, V> m = Collections.synchronizedMap(new DeleteOnReadMap<K, V>(...));

Answer 2

My thought is something like the following:

 Collections.synchronizedMap(new LinkedHashMap<K, V>());

I think that takes care of everything except requirement 5, but you can do that by using the remove() method instead of get().

This won't be quite as efficient as a ConcurrentMap would be - synchronization locks the entire map on every access, but I think ConncurrentMap implementations can use read-write locks and selective locking on only part of the map to allow multiple non-conflicting accesses to go on simultaneously. If you wanted, you could probably get better performance by writing your own subclass of some existing Map implementation.