CODEWITHSUNDEEP
javalinkedhashmap
Kevin
Kevin

Reputation: 3379

LinkedHashMap removeEldestEntry removing 2 elements?

I looked at this thread: LinkedHashMap removeEldestEntry: How many elements are removed?

And it states that removeEldestEntry removes only 1 element. This makes sense to me, but when I debug through my code, it seems to be removing 2 elements. I'm not sure why.

public class LRUCache {
    LinkedHashMap<Integer, Integer> LRUMap;

    public LRUCache(int capacity) {
        LRUMap = new LinkedHashMap<Integer, Integer>() {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return LRUMap.size() > capacity;
            }
        };
    }

    public int get(int key) {
        if (LRUMap.containsKey(key)) {
            int val = LRUMap.remove(key);
            LRUMap.put(key,  val);
            return val;
        }
        return -1;
    }

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

    public static void main(String[] args) {    
        LRUCache c = new LRUCache(2);
        c.set(2,1);
        c.set(1,1);
        c.set(2,3);
        c.set(4,1);
    }
}

So you can see from this that it will insert: (2,1) and (1,1). The next element is where things get messy. Because the key 2 already exists, it overwrites the (2,1) element with (2,3). After this, when I insert (4,1), I already have 2 elements, so it should remove the eldest entry: (1,1). However, it removes both (2,3) and (1,1), leaving me with only (4,1) in the Map.

Any ideas why? I assume this has something to do with the key being replaced and (2,3) being at the start of the list, like it is the eldest entry, even though it shouldn't be. But I'm still confused why it would remove 2 elements.

On a side note, it looks like it is storing the eldest element at the front of the LinkedHashMap, which would also give us a constant time removal of the eldest entry. Is this true?

Upvotes: 2

Views: 1245

Answers (1)

Sean Mickey
Sean Mickey

Reputation: 7716

The key behavioral feature of LinkedHashMap to understand is that the Map.Entry<Integer, Integer> members of the map are organized to preserve insertion order, which answers the questions you have related to the ordering of the members within the Map. So if we walk through each line of code in your main method, we will see the following:

  1. After c.set(2,1) the contents of LRUMap will be: {2=1}.
  2. After c.set(1,1) the contents of LRUMap will be: {2=1, 1=1}.
  3. After c.set(2,3) the contents of LRUMap will be: {2=3, 1=1}. This action simply updates the value mapped for the key (2) from 1 to 3 and is not considered to be a structural change, so the order of the members is maintained.
  4. After c.set(4,1) the contents of LRUMap will be: {1=1, 4=1}. The mapping: 2=3 is considered to be the eldest entry, so it is removed (and the mapping: 1=1 is retained).

Since it is clear from your intent that you want to create a least-recently-used cache, you should consider changing the construction of your LinkedHashMap to move away from insertion-order member storage in favor of last-access member ordering. The LinkedHashMap class provides an alternative constructor to support this type of usage:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

If you pass the value: true for the accessOrder parameter, the member mappings will be stored in access-order (which is what you want to use for an LRU cache) or if you pass the value: false for the accessOrder parameter, the member mappings will be stored in insertion-order.

Upvotes: 3

Related Questions