Thread safety of this queue backed by ConcurrentHashMap
What if you have 2 threads that submit the same E. The first one runs untill the switch here in the code snippet below. Then the second thread runs up to that point. Both pass the check because it's not in the map yet, but then both will put in a new Future in the map.

@Override
public Future&lt;E&gt; submit(E e) {
    if (!itemsBeingWorkedOn.containsKey(e)) {
        //***switch here***
        itemsBeingWorkedOn.put(e, asyncWorker.executeWorkAsync(e, this));
    } else {
        LOGGER.debug("Rejected [{}] as it's already being worked on", e);
    }
    return itemsBeingWorkedOn.get(e);
}


Easiest way to make this thread safe would be to just make the entire method synchronised. If you're expecting to skip a lot that are already in you might consider this idea based on double checked locking:

@Override
public Future&lt;E&gt; submit(E e) {
    if (!itemsBeingWorkedOn.containsKey(e)) {
        synchronised(this){
            if (!itemsBeingWorkedOn.containsKey(e)) {
                itemsBeingWorkedOn.put(e, asyncWorker.executeWorkAsync(e, this));
           }
       }
    } else {
        LOGGER.debug("Rejected [{}] as it's already being worked on", e);
    }
    return itemsBeingWorkedOn.get(e);
}


This might have some really sublte unexpected results when one finishes (and is taken out of the map) just when another is submitted (this can return null). Depending on how you intend to use the class this may not be a problem though.