diff --git a/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java b/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java
index 79ca076..21c9e09 100644
--- a/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java
+++ b/quickstep/src/com/android/quickstep/util/TaskKeyByLastActiveTimeCache.java
@@ -44,7 +44,7 @@
     private final PriorityQueue<Task.TaskKey> mQueue;
 
     public TaskKeyByLastActiveTimeCache(int maxSize) {
-        mMap = new HashMap(maxSize);
+        mMap = new HashMap(0);
         mQueue = new PriorityQueue<>(Comparator.comparingLong(t -> t.lastActiveTime));
         mMaxSize = new AtomicInteger(maxSize);
     }
@@ -106,7 +106,8 @@
     }
 
     /**
-     * Adds an entry to the cache, optionally evicting the last accessed entry
+     * Adds an entry to the cache, optionally evicting the last accessed entry excluding the newly
+     * added entry
      */
     @Override
     public final synchronized void put(Task.TaskKey key, V value) {
@@ -117,9 +118,9 @@
                 mQueue.remove(entry.mKey);
             }
 
+            removeExcessIfNeeded(mMaxSize.get() - 1);
             mMap.put(key.id, new Entry<>(key, value));
             mQueue.add(key);
-            removeExcessIfNeeded();
         } else {
             Log.e(TAG, "Unexpected null key or value: " + key + ", " + value);
         }
@@ -143,11 +144,11 @@
     @Override
     public synchronized void updateCacheSizeAndRemoveExcess(int cacheSize) {
         mMaxSize.compareAndSet(mMaxSize.get(), cacheSize);
-        removeExcessIfNeeded();
+        removeExcessIfNeeded(mMaxSize.get());
     }
 
-    private synchronized void removeExcessIfNeeded() {
-        while (mQueue.size() > mMaxSize.get() && !mQueue.isEmpty()) {
+    private synchronized void removeExcessIfNeeded(int maxSize) {
+        while (mQueue.size() > maxSize && !mQueue.isEmpty()) {
             Task.TaskKey key = mQueue.poll();
             mMap.remove(key.id);
         }