Easy solution using java.util.LinkedHashMap


#1

The easiest solution is to use java.util.LinkedHashMap.
Here is my solution:

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache {

    private final Map<Integer, Integer> cache;

    public LRUCache(final int cacheCapacity) {
        this.cache = new LinkedHashMap<Integer, Integer>(cacheCapacity, 100.0f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > cacheCapacity;
            }
        };
    }

    public int get(int key) {
        if (cache.containsKey(key))
            return cache.get(key);
        return -1;
    }

    public void set(int key, int value) {
        cache.put(key, value);
    }

}

#2

What are the other 2 paramaters 100.0f and true in removeEldestEntry function??


#3

@ankur-kumar_397, here is that constructor signature

new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder)

The entries of a LinkedHashMap can be iterated either in the order the keys were first added to the Map (that’s the default behavior) or according to access order (i.e. the most recently accessed entry will be the last entry iterated over).

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

I hope, I’ve answered your query!! :slight_smile:


#4

Thanks a lot for the detailed explanation.


#5

@holland, @satya_bolenedi
load factor is decimal form of percent ex. 0.75. In our case 1 would be enough, don’t you think that 100 is an overkill?


#6

“Set or insert the value if the key is not already present” - How is this ensured in this solution? For example, if capacity if 2 and we try to set( 2, 1) and set(2, 2), output is 2. According to that statement, it should be 1. Are we not handling that in the solution?


#7

Can you please clarify that why load factor is 100.0f here?Is it ensuring that the map will not be resized?
(I am confused here,because the size can be capacity+1…i.e. the new element will be added first and then removeEldestEntry will be called to check if the size >capacity?)
P.S. I checked geeks and stackoverflow,but didn’t get any satisfactory answer.