diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
index 1741fb2..ed96fe4 100644
--- a/include/utils/LruCache.h
+++ b/include/utils/LruCache.h
@@ -200,11 +200,11 @@
         return false;
     }
     Entry* entry = *find_result;
+    mSet->erase(entry);
     if (mListener) {
         (*mListener)(entry->key, entry->value);
     }
     detachFromCache(*entry);
-    mSet->erase(entry);
     delete entry;
     return true;
 }
diff --git a/libutils/tests/LruCache_test.cpp b/libutils/tests/LruCache_test.cpp
index 580b980..dd95c57 100644
--- a/libutils/tests/LruCache_test.cpp
+++ b/libutils/tests/LruCache_test.cpp
@@ -73,6 +73,13 @@
 
 ssize_t ComplexValue::instanceCount = 0;
 
+struct KeyWithPointer {
+    int *ptr;
+    bool operator ==(const KeyWithPointer& other) const {
+        return *ptr == *other.ptr;
+    }
+};
+
 } // namespace
 
 
@@ -84,6 +91,10 @@
     return hash_type(value.k);
 }
 
+template<> inline android::hash_t hash_type(const KeyWithPointer& value) {
+    return hash_type(*value.ptr);
+}
+
 class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
 public:
     EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
@@ -98,6 +109,14 @@
     StringValue lastValue;
 };
 
+class InvalidateKeyCallback : public OnEntryRemoved<KeyWithPointer, StringValue> {
+public:
+    void operator()(KeyWithPointer& k, StringValue&) {
+        delete k.ptr;
+        k.ptr = nullptr;
+    }
+};
+
 class LruCacheTest : public testing::Test {
 protected:
     virtual void SetUp() {
@@ -293,6 +312,25 @@
     EXPECT_EQ(3, callback.callbackCount);
 }
 
+TEST_F(LruCacheTest, CallbackRemovesKeyWorksOK) {
+    LruCache<KeyWithPointer, StringValue> cache(1);
+    InvalidateKeyCallback callback;
+    cache.setOnEntryRemovedListener(&callback);
+    KeyWithPointer key1;
+    key1.ptr = new int(1);
+    KeyWithPointer key2;
+    key2.ptr = new int(2);
+
+    cache.put(key1, "one");
+    // As the size of the cache is 1, the put will call the callback.
+    // Make sure everything goes smoothly even if the callback invalidates
+    // the key (b/24785286)
+    cache.put(key2, "two");
+    EXPECT_EQ(1U, cache.size());
+    EXPECT_STREQ("two", cache.get(key2));
+    cache.clear();
+}
+
 TEST_F(LruCacheTest, IteratorCheck) {
     LruCache<int, int> cache(100);