Concurrent Map with fixed size

Question

I need a map with the following requirements :

1. It should be highly concurrent. The put(), get() and remove() methods may be called by multiple threads simultaneously.

2. It should be of fixed size. If the size of the HashMap reaches to the max value (e.g. 10000), addition of a new entry to the map should not be allowed. It CAN'T be LRU cache where the oldest entry gets removed on reaching maximum size.

ConcurrentHashMap may satisfy #1. But, not sure how #2 can be implemented on top of ConcurrentHashMap without impacting concurrency (Adding a custom put() method which will add to the map only when the size is lesser than the max size, needs to be "synchronized". That will defeat the purpose of using concurrent HashMap).

Please let me know your thoughts.

Solution 1

You could implement a map that delegates to a ConcurrentHashMap, using a counting semaphore to limit the number of items in the map. The Semaphore class uses an atomically-updated int to keep track of the permits, so it wouldn't incur much extra overhead.

Solution 2

Try this:

public static class ConcurrentFixedMap<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_ENTRIES;
    private ConcurrentFixedMap(int size) {
        super(size);
        this.MAX_ENTRIES = size;
    }

    public static <K, V> Map<K, V> init(int size) {
        return Collections.synchronizedMap(new ConcurrentFixedMap<>(size));
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_ENTRIES;
    }
}

Solution 3

How about maintaining the size of Hashmap at all times to ensure the total number of elements inserted? You can use AtomicInteger so that you don't have to synchronize/lock a regular int and sacrifice the benefit of using ConcurrentHashMap.

Solution 4

You can do all these yourself, and the java SE arsenal alone might supply what you require, but I strongly recommend an easier and more scalable methodology as doing all this work yourself would be re-inventing the wheel. Try one of these in memory data grids :

• Ehcache
• Hazelcast

For instance in ehcache you can achieve what you want by a configuration similar to :

<cache 
 name="myCache"
 maxElementsInMemory="10000"
 eternal="true"
 overflowToDisk="false" />

View more solutions

Comments

[vefthym]

check the size before putting?

[Nathan Hughes]

in concurrenthashmap the size reported is not exact. maybe use concurrenthashmap with a counting semaphore?

[heorhi]

"not sure how #2 can be implemented on top of ConcurrentHashMap without impacting concurrency"... I don't see why it is going to be a problem. You create a wrapper that, on top of concurrent map introduces counter. For synchronizing access to counter you use your own syncronizing primitive (e.g., ReentrantLock) to minimize additional overhead and have it separated from the concurrent map sync. Then everything should work just fine

[vefthym]

@NathanHughes I think you should write a new answer and get the problem solved. +1

[Ar5hv1r]

How strict does this maximum have to be? If some race conditions are tolerable, I'd think simply adding a check to all mutator methods would work (though note size()is not constant time). If you really need a hard cap, you're going to have trouble enforcing this without dramatically hurting concurrency - even the semaphore idea requires synchronizing. Could you provide a bit more detail as to your use case, and why you think a fixed-size concurrent collection is the right solution? This sounds like an XY problem to me.

[Arnab Biswas]

No the sizing requirements is not strict. We just want to make sure that in the worst case, our server does not go OOM.

[jezg1993]

Changing concurrencyLevel in no way addresses his problem of a fixed-size ConcurrentMap.

[Vishy]

The main downside being that this would be many orders of magnitude slower.

[Pumpkin]

I can agree that it would but then again one should be selective when choosing what to optimize. Some of the distributed hash maps I use hold over millions of data in seperate regions with their associated services responding within acceptable timeframes. Considering all that, 10000 is a very very small number.

[Arnab Biswas]

I have not yet checked the details, but, I don't need a distributed cache. I can live with a simple hash map satisfying the above mentioned requirements. So, does that mean ConcurrentHashMap with semaphore makes more sense?

[Arnab Biswas]

Agreed. This is not going to address the fixed size ConcurrentMap problem.

[Pumpkin]

You don't have to use it in a distributed manner, though it would be nice for it to be able to become one should you need it. And imagine a scenario in which you suddenly decided that you need LRU, wouldn't it be nice to turn it on with a line of configuraion ? My point is the key value DB concept, whether as data grid or cache, is already being worked on by the community. Why create your own simple implementation, when you can use one that is created and supported with great effort by the community.

[Pumpkin]

And should you need something beyond the scope of what is already created before you, you can always contribute the project and help us all.

[Ralf H]

Use Semaphore's tryAcquire before put and release after remove, since you don't want to block.

[Ashley Frieze]

Agreed from me too, but it will improve the concurrency, which was his other concern. Worth noting.

[Arnab Biswas]

Hi anaken, welcome to Stackoverflow! Thanks for answering this question which is almost 8 years old. Unfortunately, I can't check your answer since I no longer use Java. But, I am sure it will be useful for other community members.

[Seth]

This didn't work for me, I found inserting 500k items asynchronously resulted in a map with size~300k entries. Here's my pseudocode: AtomicInteger value = new AtomicInteger(0); for (int i = 0; i < 500000; i++) { newScheduledThreadPool.execute(() -> { int getValue = value.getAndIncrement(); concurrent.put(String.valueOf(getValue), getValue); }); }