diff --git a/luni/src/test/java/libcore/java/util/LinkedHashMapTest.java b/luni/src/test/java/libcore/java/util/LinkedHashMapTest.java
index c7de1f6..e82e66d 100644
--- a/luni/src/test/java/libcore/java/util/LinkedHashMapTest.java
+++ b/luni/src/test/java/libcore/java/util/LinkedHashMapTest.java
@@ -18,6 +18,8 @@
 
 import java.util.LinkedHashMap;
 import java.util.Map;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicInteger;
 
 public class LinkedHashMapTest extends junit.framework.TestCase {
 
@@ -205,4 +207,31 @@
         assertEquals("key1", newest.getKey());
         assertEquals("value3", newest.getValue());
     }
+
+    // http://b/27929722
+    // This tests the behaviour is consistent with earlier Android releases.
+    // This behaviour is NOT consistent with the RI. Future Android releases
+    // might change this.
+    public void test_removeEldestEntry() {
+        final AtomicBoolean removeEldestEntryReturnValue = new AtomicBoolean(false);
+        final AtomicInteger removeEldestEntryCallCount = new AtomicInteger(0);
+        LinkedHashMap<String, String> m = new LinkedHashMap<String, String>() {
+            @Override
+            protected boolean removeEldestEntry(Entry eldest) {
+                removeEldestEntryCallCount.incrementAndGet();
+                return removeEldestEntryReturnValue.get();
+            }
+        };
+
+        m.put("foo", "bar");
+        assertEquals(0, removeEldestEntryCallCount.get());
+        m.put("baz", "quux");
+        assertEquals(1, removeEldestEntryCallCount.get());
+
+        removeEldestEntryReturnValue.set(true);
+        m.put("foob", "faab");
+        assertEquals(2, removeEldestEntryCallCount.get());
+        assertEquals(2, m.size());
+        assertFalse(m.containsKey("foo"));
+    }
 }
diff --git a/ojluni/src/main/java/java/util/LinkedHashMap.java b/ojluni/src/main/java/java/util/LinkedHashMap.java
index 81b8a7a..7853d46 100755
--- a/ojluni/src/main/java/java/util/LinkedHashMap.java
+++ b/ojluni/src/main/java/java/util/LinkedHashMap.java
@@ -440,13 +440,27 @@
      * removes the eldest entry if appropriate.
      */
     void addEntry(int hash, K key, V value, int bucketIndex) {
-        super.addEntry(hash, key, value, bucketIndex);
+        // Previous Android releases called removeEldestEntry() before actually
+        // inserting a value but after increasing the size.
+        // The RI is documented to call it afterwards.
+        // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
 
         // Remove eldest entry if instructed
         LinkedHashMapEntry<K,V> eldest = header.after;
-        if (removeEldestEntry(eldest)) {
-            removeEntryForKey(eldest.key);
+        if (eldest != header) {
+            boolean removeEldest;
+            size++;
+            try {
+                removeEldest = removeEldestEntry(eldest);
+            } finally {
+                size--;
+            }
+            if (removeEldest) {
+                removeEntryForKey(eldest.key);
+            }
         }
+
+        super.addEntry(hash, key, value, bucketIndex);
     }
 
     /**
@@ -473,7 +487,12 @@
         size++;
     }
 
-    /**
+    // Intentionally make this not JavaDoc, as the we don't conform to
+    // the behaviour documented here (we call removeEldestEntry before
+    // inserting the new value to be consistent with previous Android
+    // releases).
+    // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
+    /*
      * Returns <tt>true</tt> if this map should remove its eldest entry.
      * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
      * inserting a new entry into the map.  It provides the implementor