Concurrent collection to 50/50 read/write

Question

I need your advice. For a start I would like to describe preconditions.

1. I have some third party Java objects with default java.lang.Object's hashCode() and equals() implementation. Comparable interface is not implemented. The size is insignificant.
2. I need to store such objects for some time in memory. I will read and write them from different threads in 50/50 ratio (approximately 50% reads and 50% writes).
3. The order of the objects is not important. I just want to have possibility to take some object from the store, that's all. With take I mean both get and remove at the same time.
4. Sure, I want it to work as fast as possible with lowest memory consumption. I'm trying to avoid any synchronizations in my code.

First I've tried to solve this problem by myself. I've immediately rejected CopyOnWriteArray* collections due to high memory consumption. I've read it's better to use them in case of rare writes. ConcurrentHashMap in general suites for my needs but I didn't find way to make take operation atomic without synchronization. I've stopped with my investigation on ConcurrentSkipListSet collection. It contains pollFirst method which is pretty good suite to take objects.

I've implemented my solution with ConcurrentSkipListSet as a basis. I've got everything works fine except one small detail. As I mentioned above objects I'm working with don't implement Comparable. So to use chosen collection I have to somehow implement Comparator. Here's my implementation of this interface. In this example I've used directly java.lang.Object instead of my objects type. I've done this 'cause implementation is completely the same, difference is only in generic part of the class.

import java.util.Comparator;

public class ObjectComparator implements Comparator<Object> {

    public int compare(Object o1, Object o2) {
        return o1.hashCode() - o2.hashCode();
    }
}

Cons of this implementation is obvious. I've found there's no guarantee that two different objects will have different hash codes. In such case it's possible to loose some objects which is not acceptable. I've thought to return some random number in case of equal hash codes for different objects but I'm not sure it will not break ConcurrentSkipListSet implementation.

Regarding situation described I have two general questions.

1. Is it possible to implement Comparator for my object in as such way to don't return 0 for different objects and keep ConcurrentSkipListSet operability?
2. Is there some other way to store my objects?

Thank you in advance for your answers.

Answer 1

Probably you are looking for ConcurrentLinkedQueue, this will store the items based on the FiFo (first in first out) order. Because of this no hashcode and comparable requirements are present. The implementation of this queue is very efficient, without any internal locking.

One difficulty that you have (when not using locks) is that you can not check if the collection is not empty and then take one (because it might have changed after your check and before your action). Therefor the take function will return null when nothing is present. If you don't want to keep polling for data, then you can also resort to classes implementing the BlockingQueue interface, this offers functions that wait until data is available.

Answer 2

1: You could implement your comparator as such:

public int compare(Object o1, Object o2) {
    if (o1 == o2) {
        return 0;
    } else {
        int dif = o1.hashCode() - o2.hashCode();
        if (dif != 0) {
            return dif;
        } else {
            return 1; //Might cause issues
        }
    }
}

2: You can make any normal collection synchronized using java.util.Collections.synchronizedCollection() (or any other synchronized- method). For example, if you synchronize a LinkedList, you can use remove(index) to take an object.

Answer 3

ConcurrentHashMap in general suites for my needs but I didn't find way to make take operation atomic

Why not use remove in ConcurrentHashMap? Seems it is what you need.