Grappling with ConcurrentHashMap

[Steven Rodeo]

HI folks,

Apologies, if this is trivial.

I am implementing a cache.

The KEY being a "String" and the VALUE being an List. I wrote this code to this effect.

Is this function thread safe ?. For instance what happens if another thread comes by and deletes a given mapping for a key.

  public void cache(String key, String value) {

        List<String> currentMapping = myCache.get(key);
        if (currentMapping == null) {
            List<String> newMapping = new ArrayList<String>();
            List<String> addMapping = myCache.putIfAbsent(key, newMapping);
            if (addMapping == null) { // No Mapping existed before, that's why Null {
                currentMapping = newMapping;
            }
        }
        synchronized (currentMapping) {
            currentMapping.add(value);
        }
    }

Thanks Much
-SM

[Winston Gutkowski]

Steven Rodeo wrote:I am implementing a cache.
The KEY being a "String" and the VALUE being an List.

I guess my first question would be: why a List?
Since Lists allow duplicates, value could be added many times for the same key. Is that what you want?

I wrote this code to this effect.
Is this function thread safe ?.

Looks it; however, it seems a bit tortuous. How about just:

public void cache(String key, String value) {
   List<String> currentMapping = myCache.putIfAbsent(key, new ArrayList<String>());
   synchronized (currentMapping) {
      currentMapping.add(value);
   }
}

Winston

[Winston Gutkowski]

Steven Rodeo wrote:Is this function thread safe?

It also occurred to me that if each entry in your cache was also a Concurrent collection, you could do the whole thing in one line, viz:

ConcurrentHashMap<String, ConcurrentLinkedQueue<String>> myCache =
   new ConcurrentHashMap<String, ConcurrentLinkedQueue<String>>();
...
public void cache(String key, String value) {
   myCache.putIfAbsent(key, new ConcurrentLinkedQueue<String>()).add(value);
}

Winston

[Mike Simmons]

Winston Gutkowski wrote:

myCache.putIfAbsent(key, new ConcurrentLinkedQueue<String>()).add(value);

But putIfAbsent() returns null if the key was not previously mapped.

[Steven Rodeo]

This is going to throw a NullPointerException ?. I see this from the javadocs

putIfAbsent

public V putIfAbsent(K key,
                     V value)
If the specified key is not already associated with a value, associate it with the given value. This is equivalent to
   if (!map.containsKey(key)) 
      return map.put(key, value);
   else
      return map.get(key);

Except that the action is performed atomically.

Specified by: putIfAbsent in interface ConcurrentMap<K,V>

Parameters:
key - key with which the specified value is to be associated.
value - value to be associated with the specified key.

Returns:
previous value associated with specified key, or null if there was no mapping for key.

Throws:
NullPointerException - if the specified key or value is null.

[Winston Gutkowski]

Mike Simmons wrote:

Winston Gutkowski wrote:

myCache.putIfAbsent(key, new ConcurrentLinkedQueue<String>()).add(value);

But putIfAbsent() returns null if the key was not previously mapped.

Oh yeah. Duh. Seems to me they might have missed a beat there - I guess it's to keep it consistent with HashMap, but why return null when you don't have to?

@Steven: My apologies. I guess it has to be:

List<String> currentMapping = myCache.putIfAbsent(key, new ArrayList<String>());
if (currentMapping == null)
   currentMapping = myCache.get(key);
synchronized (currentMapping) {
   currentMapping.add(value);
}

but I am right that if you use a Concurrent dataset you don't need the synchronized block.

Winston

[Jeff Verdegan]

I usually do it as:

if (!map.containsKey(k)) {
  map.putIfAbsent(k, new V());
}
V v = map.get(k);

// OR

map.putIfAbsent(k, new V());
V v = map.get(k);

The tradeoff between an unneeded lookup and an unneeded object creation may be a bit of premature optimization in either direction, but I'll usually go with the first case (extra lookup).

[Winston Gutkowski]

Jeff Verdegan wrote:The tradeoff between an unneeded lookup and an unneeded object creation may be a bit of premature optimization in either direction, but I'll usually go with the first case (extra lookup).

Yeah, I guess if it's a cache, the first style might save you creating a lot of empty Lists (or V's) unnecessarily.

Winston

[Pat Farrell]

First thing I'd ask is why are you implementing a cache? There are lots of existing implementations that are free, open source, debugged, documented, etc.

So if you want to learn, lets keep going. But if you just want to use one, I'd start with the Google Guava com.google.common.cache.* classes.

Once you get the fundamentals working, you really need to thing long and hard about what strategies you want to use, when do you kick entries out of the cache, how often do you kick one or more out, what is the loading strategy, etc.

The initial discussion of them usually start with a last used goes out first strategy, but that is not optimal in many real world usages.