diff -u new/src/java.security.jgss/share/classes/sun/security/krb5/internal/rcache/AuthList.java new/src/java.security.jgss/share/classes/sun/security/krb5/internal/rcache/AuthList.java
--- new/src/java.security.jgss/share/classes/sun/security/krb5/internal/rcache/AuthList.java	2018-02-11 12:27:44.000000000 +0800
+++ new/src/java.security.jgss/share/classes/sun/security/krb5/internal/rcache/AuthList.java	2018-02-23 09:48:44.000000000 +0800
@@ -55,6 +55,9 @@
     private final LinkedList<AuthTimeWithHash> entries;
     private final int lifespan;
 
+    // entries.getLast().ctime, updated after each cleanup.
+    private volatile int oldestTime = Integer.MIN_VALUE;
+
     /**
      * Constructs a AuthList.
      */
@@ -72,6 +75,8 @@
 
         if (entries.isEmpty()) {
             entries.addFirst(t);
+            oldestTime = t.ctime;
+            return;
         } else {
             AuthTimeWithHash temp = entries.getFirst();
             int cmp = temp.compareTo(t);
@@ -108,10 +113,10 @@
         long timeLimit = currentTime.getSeconds() - lifespan;
         long veryOld = timeLimit - (lifespan > 60 ? 60 : lifespan);
 
-        // Only trigger a cleanup when there exist *very* old items
-        // (lifespan + 1 min ago). This makes sure the cleanup is done
+        // Only trigger a cleanup when very old entries exist
+        // (lifespan + 1 min ago). This ensures a cleanup is done
         // at most every minute.
-        if (entries.getLast().ctime > veryOld) {
+        if (oldestTime > veryOld) {
             return;
         }
 
@@ -128,9 +133,12 @@
                         break;
                     }
                 }
-                return;
+                break;
             }
         }
+
+        AuthTimeWithHash last = entries.peekLast();
+        oldestTime = last == null ? Integer.MIN_VALUE : last.ctime;
     }
 
     public boolean isEmpty() {