diff --git a/build.xml b/build.xml
index 203d504..09acb0d 100644
--- a/build.xml
+++ b/build.xml
@@ -105,6 +105,7 @@
         <pathelement location="lib/javax.inject.jar"/>
         <pathelement location="lib/aopalliance.jar"/>
         <pathelement location="lib/guava-16.0.1.jar"/>
+        <pathelement location="lib/build/guava-testlib-16.0.1.jar"/>
         <pathelement location="lib/build/junit.jar"/>
         <pathelement location="lib/build/servlet-api-2.5.jar"/>
         <pathelement location="lib/build/easymock.jar"/>
diff --git a/core/pom.xml b/core/pom.xml
index e420035..ffb78ab 100644
--- a/core/pom.xml
+++ b/core/pom.xml
@@ -29,6 +29,12 @@
       <artifactId>guava</artifactId>
       <version>16.0.1</version>
     </dependency>
+    <dependency>
+      <groupId>com.google.guava</groupId>
+      <artifactId>guava-testlib</artifactId>
+      <version>16.0.1</version>
+      <scope>test</scope>
+    </dependency>
     <!--
      | CGLIB is embedded by default by the JarJar build profile
     -->
diff --git a/core/src/com/google/inject/internal/AbstractBindingProcessor.java b/core/src/com/google/inject/internal/AbstractBindingProcessor.java
index 72dae2b..e1a0bba 100644
--- a/core/src/com/google/inject/internal/AbstractBindingProcessor.java
+++ b/core/src/com/google/inject/internal/AbstractBindingProcessor.java
@@ -98,7 +98,7 @@
     }
 
     // prevent the parent from creating a JIT binding for this key
-    injector.state.parent().blacklist(key, binding.getSource());
+    injector.state.parent().blacklist(key, injector.state, binding.getSource());
     injector.state.putBinding(key, binding);
   }
 
diff --git a/core/src/com/google/inject/internal/InheritingState.java b/core/src/com/google/inject/internal/InheritingState.java
index 2d694cb..06e0ec4 100644
--- a/core/src/com/google/inject/internal/InheritingState.java
+++ b/core/src/com/google/inject/internal/InheritingState.java
@@ -56,12 +56,13 @@
   /*end[AOP]*/
   private final List<TypeListenerBinding> typeListenerBindings = Lists.newArrayList();
   private final List<ProvisionListenerBinding> provisionListenerBindings = Lists.newArrayList(); 
-  private final WeakKeySet blacklistedKeys = new WeakKeySet();
+  private final WeakKeySet blacklistedKeys;
   private final Object lock;
 
   InheritingState(State parent) {
     this.parent = checkNotNull(parent, "parent");
     this.lock = (parent == State.NONE) ? this : parent.lock();
+    this.blacklistedKeys = new WeakKeySet(lock);
   }
 
   public State parent() {
@@ -154,9 +155,9 @@
     return result;
   }
 
-  public void blacklist(Key<?> key, Object source) {
-    parent.blacklist(key, source);
-    blacklistedKeys.add(key, source);
+  public void blacklist(Key<?> key, State state, Object source) {
+    parent.blacklist(key, state, source);
+    blacklistedKeys.add(key, state, source);
   }
 
   public boolean isBlacklisted(Key<?> key) {
diff --git a/core/src/com/google/inject/internal/InjectorImpl.java b/core/src/com/google/inject/internal/InjectorImpl.java
index 6faab97..10bd9be 100644
--- a/core/src/com/google/inject/internal/InjectorImpl.java
+++ b/core/src/com/google/inject/internal/InjectorImpl.java
@@ -791,7 +791,7 @@
     }
 
     BindingImpl<T> binding = createJustInTimeBinding(key, errors, jitDisabled, jitType);
-    state.parent().blacklist(key, binding.getSource());
+    state.parent().blacklist(key, state, binding.getSource());
     jitBindings.put(key, binding);
     return binding;
   }
diff --git a/core/src/com/google/inject/internal/State.java b/core/src/com/google/inject/internal/State.java
index d824cc1..3c9e081 100644
--- a/core/src/com/google/inject/internal/State.java
+++ b/core/src/com/google/inject/internal/State.java
@@ -105,7 +105,7 @@
       return ImmutableList.of();
     }
 
-    public void blacklist(Key<?> key, Object source) {
+    public void blacklist(Key<?> key, State state, Object source) {
     }
 
     public boolean isBlacklisted(Key<?> key) {
@@ -165,9 +165,9 @@
   /**
    * Forbids the corresponding injector from creating a binding to {@code key}. Child injectors
    * blacklist their bound keys on their parent injectors to prevent just-in-time bindings on the
-   * parent injector that would conflict.
+   * parent injector that would conflict and pass along their state to control the lifetimes.
    */
-  void blacklist(Key<?> key, Object source);
+  void blacklist(Key<?> key, State state, Object source);
 
   /**
    * Returns true if {@code key} is forbidden from being bound in this injector. This indicates that
diff --git a/core/src/com/google/inject/internal/WeakKeySet.java b/core/src/com/google/inject/internal/WeakKeySet.java
index 761cd35..022aa4f 100644
--- a/core/src/com/google/inject/internal/WeakKeySet.java
+++ b/core/src/com/google/inject/internal/WeakKeySet.java
@@ -16,37 +16,86 @@
 
 package com.google.inject.internal;
 
+import com.google.common.base.Objects;
+import com.google.common.base.Preconditions;
+import com.google.common.cache.Cache;
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.RemovalCause;
+import com.google.common.cache.RemovalListener;
+import com.google.common.cache.RemovalNotification;
+import com.google.common.collect.LinkedHashMultiset;
 import com.google.common.collect.Maps;
+import com.google.common.collect.Multiset;
 import com.google.common.collect.Sets;
 import com.google.inject.Key;
 import com.google.inject.internal.util.SourceProvider;
 
+import java.lang.annotation.Annotation;
 import java.util.Map;
 import java.util.Set;
 
 /**
  * Minimal set that doesn't hold strong references to the contained keys.
  *
- * @author jessewilson@google.com (Jesse Wilson)
+ * @author dweis@google.com (Daniel Weis)
  */
 final class WeakKeySet {
 
-  // TODO(user): Instead of relying on Key#toString(), consider maintaining a set of custom weak
-  // references for child injectors. On some actions, we can poll the ReferenceQueue and clear the
-  // relevant blacklisted values. This would allow us to avoid forcing the toString memoization on
-  // Key and fix the memory leak referenced in
-  // https://code.google.com/p/google-guice/issues/detail?id=756.
+  /**
+   * The key for the Map is {@link Key} for most bindings, String for multibindings.
+   * <p>
+   * Reason being that multibinding Key's annotations hold a reference to their injector, implying
+   * we'd leak memory.
+   */
+  private Map<Object, Multiset<Object>> backingSet;
+  
+  /**
+   * This is already locked externally on add and getSources but we need it to handle clean up in
+   * the evictionCache's RemovalListener.
+   */
+  private final Object lock;
 
   /**
-   * We store strings rather than keys so we don't hold strong references.
-   *
-   * <p>One potential problem with this approach is that parent and child injectors cannot define
-   * keys whose class names are equal but class loaders are different. This shouldn't be an issue
-   * in practice.
+   * Tracks child injector lifetimes and evicts blacklisted keys/sources after the child injector is
+   * garbage collected.
    */
-  private Map<String, Set<Object>> backingSet;
+  private final Cache<State, Set<KeyAndSource>> evictionCache = CacheBuilder.newBuilder()
+      .weakKeys()
+      .removalListener(
+          new RemovalListener<State, Set<KeyAndSource>>() {
+            @Override
+            public void onRemoval(RemovalNotification<State, Set<KeyAndSource>> notification) {
+              Preconditions.checkState(RemovalCause.COLLECTED.equals(notification.getCause()));
 
-  public void add(Key<?> key, Object source) {
+              cleanUpForCollectedState(notification.getValue());
+            }
+          })
+      .build();
+
+  /**
+   * There may be multiple child injectors blacklisting a certain key so only remove the source
+   * that's relevant.
+   */
+  private void cleanUpForCollectedState(Set<KeyAndSource> keysAndSources) {
+    synchronized (lock) {
+      
+      for (KeyAndSource keyAndSource : keysAndSources) {
+        Multiset<Object> set = backingSet.get(keyAndSource.mapKey);
+        if (set != null) {
+          set.remove(keyAndSource.source);
+          if (set.isEmpty()) {
+            backingSet.remove(keyAndSource.mapKey);
+          }
+        }
+      }
+    }
+  }
+
+  WeakKeySet(Object lock) {
+    this.lock = lock;
+  }
+
+  public void add(Key<?> key, State state, Object source) {
     if (backingSet == null) {
       backingSet = Maps.newHashMap();
     }
@@ -55,22 +104,74 @@
     if (source instanceof Class || source == SourceProvider.UNKNOWN_SOURCE) {
       source = null;
     }
-    String k = key.toString();
-    Set<Object> sources = backingSet.get(k);
+    Object mapKey = toMapKey(key);
+    Multiset<Object> sources = backingSet.get(mapKey);
     if (sources == null) {
-      sources = Sets.newLinkedHashSet();
-      backingSet.put(k, sources);
+      sources = LinkedHashMultiset.create();
+      backingSet.put(mapKey, sources);
     }
-    sources.add(Errors.convert(source));
+    Object convertedSource = Errors.convert(source);
+    sources.add(convertedSource);
+
+    // Avoid all the extra work if we can.
+    if (state.parent() != State.NONE) {
+      Set<KeyAndSource> keyAndSources = evictionCache.getIfPresent(state);
+      if (keyAndSources == null) {
+        evictionCache.put(state, keyAndSources = Sets.newHashSet());
+      }
+      keyAndSources.add(new KeyAndSource(mapKey, convertedSource));
+    }
   }
 
   public boolean contains(Key<?> key) {
-    // avoid calling key.toString() if the backing set is empty. toString is expensive in aggregate,
-    // and most WeakKeySets are empty in practice (because they're used by top-level injectors)
-    return backingSet != null && backingSet.containsKey(key.toString());
+    evictionCache.cleanUp();
+    return backingSet != null && backingSet.containsKey(key);
   }
 
   public Set<Object> getSources(Key<?> key) {
-    return backingSet.get(key.toString());
+    evictionCache.cleanUp();
+    Multiset<Object> sources = backingSet.get(key);
+    return (sources == null) ? null : sources.elementSet();
+  }
+  
+  private static Object toMapKey(Key<?> key) {
+    Annotation annotation = key.getAnnotation();
+    if (annotation != null
+        // HACK: See comment on backingSet for more info. This is tested in MultibinderTest,
+        // MapBinderTest, and OptionalBinderTest in the multibinder test suite.
+        && "com.google.inject.multibindings.RealElement".equals(annotation.getClass().getName())) {
+      return key.toString();
+    }
+    return key;
+  }
+
+  private static final class KeyAndSource {
+    final Object mapKey;
+    final Object source;
+
+    KeyAndSource(Object mapKey, Object source) {
+      this.mapKey = mapKey;
+      this.source = source;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hashCode(mapKey, source);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (this == obj) {
+        return true;
+      }
+
+      if (!(obj instanceof KeyAndSource)) {
+        return false;
+      }
+
+      KeyAndSource other = (KeyAndSource) obj;
+      return Objects.equal(mapKey, other.mapKey)
+          && Objects.equal(source, other.source);
+    }
   }
 }
diff --git a/core/test/com/google/inject/AllTests.java b/core/test/com/google/inject/AllTests.java
index 54f4dea..c0fd13f 100644
--- a/core/test/com/google/inject/AllTests.java
+++ b/core/test/com/google/inject/AllTests.java
@@ -20,6 +20,7 @@
 import com.google.inject.internal.MoreTypesTest;
 import com.google.inject.internal.RehashableKeysTest;
 import com.google.inject.internal.UniqueAnnotationsTest;
+import com.google.inject.internal.WeakKeySetTest;
 import com.google.inject.internal.util.LineNumbersTest;
 import com.google.inject.matcher.MatcherTest;
 import com.google.inject.name.NamedEquivalanceTest;
@@ -106,6 +107,7 @@
     suite.addTestSuite(TypeLiteralInjectionTest.class);
     suite.addTestSuite(TypeLiteralTest.class);
     suite.addTestSuite(TypeLiteralTypeResolutionTest.class);
+    suite.addTestSuite(WeakKeySetTest.class);
 
     // internal
     suite.addTestSuite(LineNumbersTest.class);
diff --git a/core/test/com/google/inject/internal/WeakKeySetTest.java b/core/test/com/google/inject/internal/WeakKeySetTest.java
new file mode 100644
index 0000000..c3b2df8
--- /dev/null
+++ b/core/test/com/google/inject/internal/WeakKeySetTest.java
@@ -0,0 +1,578 @@
+/**
+ * Copyright (C) 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.inject.internal;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.testing.GcFinalization;
+import com.google.inject.AbstractModule;
+import com.google.inject.Binding;
+import com.google.inject.Guice;
+import com.google.inject.Injector;
+import com.google.inject.Key;
+import com.google.inject.Scope;
+import com.google.inject.TypeLiteral;
+import com.google.inject.internal.BindingImpl;
+import com.google.inject.internal.Errors;
+/*if[AOP]*/
+import com.google.inject.internal.MethodAspect;
+/*end[AOP]*/
+import com.google.inject.internal.State;
+import com.google.inject.internal.WeakKeySet;
+import com.google.inject.spi.ProvisionListenerBinding;
+import com.google.inject.spi.ScopeBinding;
+import com.google.inject.spi.TypeConverterBinding;
+import com.google.inject.spi.TypeListenerBinding;
+
+import junit.framework.TestCase;
+
+import java.lang.annotation.Annotation;
+import java.lang.ref.WeakReference;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Tests for {@link WeakKeySet}.
+ * <p>
+ * Multibinding specific tests can be found in MultibinderTest and MapBinderTest.
+ * 
+ * @author dweis@google.com (Daniel Weis)
+ */
+public class WeakKeySetTest extends TestCase {
+
+  private WeakKeySet set;
+
+  @Override
+  protected void setUp() throws Exception {
+    set = new WeakKeySet(new Object());
+  }
+
+  public void testEviction() {
+    TestState state = new TestState();
+    Key<Integer> key = Key.get(Integer.class);
+    Object source = new Object();
+    
+    WeakReference<Key<Integer>> weakKeyRef = new WeakReference<Key<Integer>>(key);
+
+    set.add(key, state, source);
+    assertTrue(set.contains(key));
+    assertEquals(1, set.getSources(key).size());
+    assertTrue(set.getSources(key).contains(source));
+
+    state = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertFalse(set.contains(Key.get(Integer.class)));
+    assertNull(set.getSources(Key.get(Integer.class)));
+
+    // Ensure there are no hanging references.
+    key = null;
+    GcFinalization.awaitClear(weakKeyRef);
+  }
+  
+  public void testEviction_nullSource() {
+    TestState state = new TestState();
+    Key<Integer> key = Key.get(Integer.class);
+    Object source = null;
+    
+    WeakReference<Key<Integer>> weakKeyRef = new WeakReference<Key<Integer>>(key);
+
+    set.add(key, state, source);
+    assertTrue(set.contains(key));
+    assertEquals(1, set.getSources(key).size());
+    assertTrue(set.getSources(key).contains(source));
+
+    state = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertFalse(set.contains(Key.get(Integer.class)));
+    assertNull(set.getSources(Key.get(Integer.class)));
+
+    // Ensure there are no hanging references.
+    key = null;
+    GcFinalization.awaitClear(weakKeyRef);
+  }
+
+  public void testEviction_keyOverlap_2x() {
+    TestState state1 = new TestState();
+    TestState state2 = new TestState();
+    Key<Integer> key1 = Key.get(Integer.class);
+    Key<Integer> key2 = Key.get(Integer.class);
+    Object source1 = new Object();
+    Object source2 = new Object();
+
+    set.add(key1, state1, source1);
+    assertTrue(set.contains(key1));
+    assertEquals(1, set.getSources(key1).size());
+    assertTrue(set.getSources(key1).contains(source1));
+
+    set.add(key2, state2, source2);
+    assertTrue(set.contains(key2));
+    assertEquals(2, set.getSources(key2).size());
+    assertTrue(set.getSources(key2).containsAll(Arrays.asList(source1, source2)));
+
+    WeakReference<Key<Integer>> weakKey1Ref = new WeakReference<Key<Integer>>(key1);
+    WeakReference<Key<Integer>> weakKey2Ref = new WeakReference<Key<Integer>>(key2);
+    WeakReference<Object> weakSource1Ref = new WeakReference<Object>(source1);
+    WeakReference<Object> weakSource2Ref = new WeakReference<Object>(source2);
+
+    Key<Integer> key = key1 = key2 = Key.get(Integer.class);
+    state1 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertTrue(set.contains(key));
+    assertEquals(1, set.getSources(key).size());
+    assertTrue(set.getSources(key).contains(source2));
+    assertFalse(set.getSources(key).contains(source1));
+
+    source1 = source2 = null;
+    
+    GcFinalization.awaitClear(weakSource1Ref);
+    // Key1 will be referenced as the key in the sources backingSet and won't be
+    // GC'd.
+    
+    // Should not be GC'd until state2 goes away.
+    assertNotNull(weakSource2Ref.get());
+
+    state2 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertFalse(set.contains(key));
+    assertNull(set.getSources(key));
+
+    GcFinalization.awaitClear(weakKey2Ref);
+    GcFinalization.awaitClear(weakSource2Ref);
+    // Now that the backing set is emptied, key1 is released.
+    GcFinalization.awaitClear(weakKey1Ref);
+  }
+  
+  public void testNoEviction_keyOverlap_2x() {
+    TestState state1 = new TestState();
+    TestState state2 = new TestState();
+    Key<Integer> key1 = Key.get(Integer.class);
+    Key<Integer> key2 = Key.get(Integer.class);
+    Object source1 = new Object();
+    Object source2 = new Object();
+
+    set.add(key1, state1, source1);
+    assertTrue(set.contains(key1));
+    assertEquals(1, set.getSources(key1).size());
+    assertTrue(set.getSources(key1).contains(source1));
+
+    set.add(key2, state2, source2);
+    assertTrue(set.contains(key2));
+    assertEquals(2, set.getSources(key2).size());
+    assertTrue(set.getSources(key1).containsAll(Arrays.asList(source1, source2)));
+
+    WeakReference<Key<Integer>> weakKey1Ref = new WeakReference<Key<Integer>>(key1);
+    WeakReference<Key<Integer>> weakKey2Ref = new WeakReference<Key<Integer>>(key2);
+
+    Key<Integer> key = key1 = key2 = Key.get(Integer.class);
+
+    GcFinalization.awaitFullGc();
+
+    assertTrue(set.contains(key));
+    assertEquals(2, set.getSources(key).size());
+    assertTrue(set.getSources(key1).containsAll(Arrays.asList(source1, source2)));
+
+    // Ensure the keys don't get GC'd when states are still referenced. key1 will be present in the
+    // as the map key but key2 could be GC'd if the implementation does something wrong.
+    assertNotNull(weakKey1Ref.get());
+    assertNotNull(weakKey2Ref.get());
+  }
+
+  public void testEviction_keyAndSourceOverlap_null() {
+    TestState state1 = new TestState();
+    TestState state2 = new TestState();
+    Key<Integer> key1 = Key.get(Integer.class);
+    Key<Integer> key2 = Key.get(Integer.class);
+    Object source = null;
+
+    set.add(key1, state1, source);
+    assertTrue(set.contains(key1));
+    assertEquals(1, set.getSources(key1).size());
+    assertTrue(set.getSources(key1).contains(source));
+
+    set.add(key2, state2, source);
+    assertTrue(set.contains(key2));
+
+    // Same source so still only one value.
+    assertEquals(1, set.getSources(key2).size());
+    assertTrue(set.getSources(key1).contains(source));
+
+    WeakReference<Key<Integer>> weakKey1Ref = new WeakReference<Key<Integer>>(key1);
+    WeakReference<Key<Integer>> weakKey2Ref = new WeakReference<Key<Integer>>(key2);
+    WeakReference<Object> weakSourceRef = new WeakReference<Object>(source);
+
+    Key<Integer> key = key1 = key2 = Key.get(Integer.class);
+    state1 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertTrue(set.contains(key));
+
+    // Should still have a single source.
+    assertEquals(1, set.getSources(key).size());
+    assertTrue(set.getSources(key1).contains(source));
+    
+    source = null;
+
+    GcFinalization.awaitClear(weakSourceRef);
+    // Key1 will be referenced as the key in the sources backingSet and won't be
+    // GC'd.
+
+    state2 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertFalse(set.contains(key));
+    assertNull(set.getSources(key));
+
+    GcFinalization.awaitClear(weakKey2Ref);
+    GcFinalization.awaitClear(weakSourceRef);
+    // Now that the backing set is emptied, key1 is released.
+    GcFinalization.awaitClear(weakKey1Ref);
+  }
+  
+  public void testEviction_keyAndSourceOverlap_nonNull() {
+    TestState state1 = new TestState();
+    TestState state2 = new TestState();
+    Key<Integer> key1 = Key.get(Integer.class);
+    Key<Integer> key2 = Key.get(Integer.class);
+    Object source = new Object();
+
+    set.add(key1, state1, source);
+    assertTrue(set.contains(key1));
+    assertEquals(1, set.getSources(key1).size());
+    assertTrue(set.getSources(key1).contains(source));
+
+    set.add(key2, state2, source);
+    assertTrue(set.contains(key2));
+
+    // Same source so still only one value.
+    assertEquals(1, set.getSources(key2).size());
+    assertTrue(set.getSources(key1).contains(source));
+
+    WeakReference<Key<Integer>> weakKey1Ref = new WeakReference<Key<Integer>>(key1);
+    WeakReference<Key<Integer>> weakKey2Ref = new WeakReference<Key<Integer>>(key2);
+    WeakReference<Object> weakSourceRef = new WeakReference<Object>(source);
+
+    Key<Integer> key = key1 = key2 = Key.get(Integer.class);
+    state1 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertTrue(set.contains(key));
+
+    // Should still have a single source.
+    assertEquals(1, set.getSources(key).size());
+    assertTrue(set.getSources(key1).contains(source));
+    
+    source = null;
+
+    GcFinalization.awaitFullGc();
+    assertNotNull(weakSourceRef.get());
+    // Key1 will be referenced as the key in the sources backingSet and won't be
+    // GC'd.
+
+    state2 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertFalse(set.contains(key));
+    assertNull(set.getSources(key));
+
+    GcFinalization.awaitClear(weakKey2Ref);
+    GcFinalization.awaitClear(weakSourceRef);
+    // Now that the backing set is emptied, key1 is released.
+    GcFinalization.awaitClear(weakKey1Ref);
+  }
+
+  public void testEviction_keyOverlap_3x() {
+    TestState state1 = new TestState();
+    TestState state2 = new TestState();
+    TestState state3 = new TestState();
+    Key<Integer> key1 = Key.get(Integer.class);
+    Key<Integer> key2 = Key.get(Integer.class);
+    Key<Integer> key3 = Key.get(Integer.class);
+    Object source1 = new Object();
+    Object source2 = new Object();
+    Object source3 = new Object();
+
+    set.add(key1, state1, source1);
+    assertTrue(set.contains(key1));
+    assertEquals(1, set.getSources(key1).size());
+    assertTrue(set.getSources(key1).contains(source1));
+
+    set.add(key2, state2, source2);
+    assertTrue(set.contains(key2));
+    assertEquals(2, set.getSources(key2).size());
+    assertTrue(set.getSources(key1).containsAll(Arrays.asList(source1, source2)));
+
+    set.add(key3, state3, source3);
+    assertTrue(set.contains(key3));
+    assertEquals(3, set.getSources(key3).size());
+    assertTrue(set.getSources(key1).containsAll(Arrays.asList(source1, source2, source3)));
+
+    WeakReference<Key<Integer>> weakKey1Ref = new WeakReference<Key<Integer>>(key1);
+    WeakReference<Key<Integer>> weakKey2Ref = new WeakReference<Key<Integer>>(key2);
+    WeakReference<Key<Integer>> weakKey3Ref = new WeakReference<Key<Integer>>(key3);
+    WeakReference<Object> weakSource1Ref = new WeakReference<Object>(source1);
+    WeakReference<Object> weakSource2Ref = new WeakReference<Object>(source2);
+    WeakReference<Object> weakSource3Ref = new WeakReference<Object>(source3);
+
+    Key<Integer> key = key1 = key2 = key3 = Key.get(Integer.class);
+    state1 = null;
+
+    GcFinalization.awaitFullGc();
+
+    assertTrue(set.contains(key));
+    assertEquals(2, set.getSources(key).size());
+    assertTrue(set.getSources(key).containsAll(Arrays.asList(source2, source3)));
+
+    source1 = null;
+    // Key1 will be referenced as the key in the sources backingSet and won't be
+    // GC'd.
+    GcFinalization.awaitClear(weakSource1Ref);
+
+    state2 = null;
+    GcFinalization.awaitFullGc();
+
+    assertTrue(set.contains(key));
+    assertEquals(1, set.getSources(key).size());
+    assertTrue(set.getSources(key).contains(source3));
+
+    GcFinalization.awaitClear(weakKey2Ref);
+    
+    source2 = null;
+    GcFinalization.awaitClear(weakSource2Ref);
+    // Key1 will be referenced as the key in the sources backingSet and won't be
+    // GC'd.
+
+    state3 = null;
+    GcFinalization.awaitFullGc();
+
+    assertFalse(set.contains(Key.get(Integer.class)));
+    assertNull(set.getSources(Key.get(Integer.class)));
+
+    GcFinalization.awaitClear(weakKey3Ref);
+    source3 = null;
+    GcFinalization.awaitClear(weakSource3Ref);
+    // Now that the backing set is emptied, key1 is released.
+    GcFinalization.awaitClear(weakKey1Ref);
+  }
+
+  public void testWeakKeySet_integration() {
+    Injector parentInjector = Guice.createInjector(new AbstractModule() {
+          @Override protected void configure() {
+            bind(Integer.class).toInstance(4);
+          }
+        });
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+
+    Injector childInjector = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        bind(String.class).toInstance("bar");
+      }
+    });
+    WeakReference<Injector> weakRef = new WeakReference<Injector>(childInjector);
+    assertBlacklisted(parentInjector, Key.get(String.class));
+    
+    // Clear the ref, GC, and ensure that we are no longer blacklisting.
+    childInjector = null;
+    GcFinalization.awaitClear(weakRef);
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+  }
+  
+  public void testWeakKeySet_integration_multipleChildren() {
+    Injector parentInjector = Guice.createInjector(new AbstractModule() {
+          @Override protected void configure() {
+            bind(Integer.class).toInstance(4);
+          }
+        });
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+    assertNotBlacklisted(parentInjector, Key.get(Long.class));
+
+    Injector childInjector1 = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        bind(String.class).toInstance("foo");
+      }
+    });
+    WeakReference<Injector> weakRef1 = new WeakReference<Injector>(childInjector1);
+    assertBlacklisted(parentInjector, Key.get(String.class));
+    assertNotBlacklisted(parentInjector, Key.get(Long.class));
+    
+    Injector childInjector2 = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        bind(Long.class).toInstance(6L);
+      }
+    });
+    WeakReference<Injector> weakRef2 = new WeakReference<Injector>(childInjector2);
+    assertBlacklisted(parentInjector, Key.get(String.class));
+    assertBlacklisted(parentInjector, Key.get(Long.class));
+    
+    // Clear ref1, GC, and ensure that we still blacklist.
+    childInjector1 = null;
+    GcFinalization.awaitClear(weakRef1);
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+    assertBlacklisted(parentInjector, Key.get(Long.class));
+
+    // Clear the ref, GC, and ensure that we are no longer blacklisting.
+    childInjector2 = null;
+    GcFinalization.awaitClear(weakRef2);
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+    assertNotBlacklisted(parentInjector, Key.get(Long.class));
+  }
+  
+  public void testWeakKeySet_integration_multipleChildren_overlappingKeys() {
+    Injector parentInjector = Guice.createInjector(new AbstractModule() {
+          @Override protected void configure() {
+            bind(Integer.class).toInstance(4);
+          }
+        });
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+
+    Injector childInjector1 = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        bind(String.class).toInstance("foo");
+      }
+    });
+    WeakReference<Injector> weakRef1 = new WeakReference<Injector>(childInjector1);
+    assertBlacklisted(parentInjector, Key.get(String.class));
+    
+    Injector childInjector2 = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        bind(String.class).toInstance("bar");
+      }
+    });
+    WeakReference<Injector> weakRef2 = new WeakReference<Injector>(childInjector2);
+    assertBlacklisted(parentInjector, Key.get(String.class));
+    
+    // Clear ref1, GC, and ensure that we still blacklist.
+    childInjector1 = null;
+    GcFinalization.awaitClear(weakRef1);
+    assertBlacklisted(parentInjector, Key.get(String.class));
+
+    // Clear the ref, GC, and ensure that we are no longer blacklisting.
+    childInjector2 = null;
+    GcFinalization.awaitClear(weakRef2);
+    assertNotBlacklisted(parentInjector, Key.get(String.class));
+  }
+  
+  private static void assertBlacklisted(Injector injector, Key<?> key) {
+    assertBlacklistState(injector, key, true);
+  }
+  
+  private static void assertNotBlacklisted(Injector injector, Key<?> key) {
+    assertBlacklistState(injector, key, false);
+  }
+
+  private static void assertBlacklistState(Injector injector, Key<?> key, boolean isBlacklisted) {
+    assertEquals(isBlacklisted, ((InjectorImpl) injector).state.isBlacklisted(key));
+  }
+  
+  private static class TestState implements State {
+    public State parent() {
+      return new TestState();
+    }
+
+    public <T> BindingImpl<T> getExplicitBinding(Key<T> key) {
+      return null;
+    }
+
+    public Map<Key<?>, Binding<?>> getExplicitBindingsThisLevel() {
+      throw new UnsupportedOperationException();
+    }
+
+    public void putBinding(Key<?> key, BindingImpl<?> binding) {
+      throw new UnsupportedOperationException();
+    }
+
+    public ScopeBinding getScopeBinding(Class<? extends Annotation> scopingAnnotation) {
+      return null;
+    }
+
+    public void putScopeBinding(Class<? extends Annotation> annotationType, ScopeBinding scope) {
+      throw new UnsupportedOperationException();
+    }
+
+    public void addConverter(TypeConverterBinding typeConverterBinding) {
+      throw new UnsupportedOperationException();
+    }
+
+    public TypeConverterBinding getConverter(String stringValue, TypeLiteral<?> type, Errors errors,
+        Object source) {
+      throw new UnsupportedOperationException();
+    }
+
+    public Iterable<TypeConverterBinding> getConvertersThisLevel() {
+      return ImmutableSet.of();
+    }
+
+    /*if[AOP]*/
+    public void addMethodAspect(MethodAspect methodAspect) {
+      throw new UnsupportedOperationException();
+    }
+
+    public ImmutableList<MethodAspect> getMethodAspects() {
+      return ImmutableList.of();
+    }
+    /*end[AOP]*/
+
+    public void addTypeListener(TypeListenerBinding typeListenerBinding) {
+      throw new UnsupportedOperationException();
+    }
+
+    public List<TypeListenerBinding> getTypeListenerBindings() {
+      return ImmutableList.of();
+    }
+
+    public void addProvisionListener(ProvisionListenerBinding provisionListenerBinding) {
+      throw new UnsupportedOperationException();
+    }
+
+    public List<ProvisionListenerBinding> getProvisionListenerBindings() {
+      return ImmutableList.of();
+    }
+
+    public void blacklist(Key<?> key, State state, Object source) {
+    }
+
+    public boolean isBlacklisted(Key<?> key) {
+      return true;
+    }
+
+    public Set<Object> getSourcesForBlacklistedKey(Key<?> key) {
+      throw new UnsupportedOperationException();
+    }
+
+    public Object lock() {
+      throw new UnsupportedOperationException();
+    }
+
+    public Map<Class<? extends Annotation>, Scope> getScopes() {
+      return ImmutableMap.of();
+    }
+  }
+}
diff --git a/extensions/multibindings/test/com/google/inject/multibindings/MapBinderTest.java b/extensions/multibindings/test/com/google/inject/multibindings/MapBinderTest.java
index ba0671d..70be342 100644
--- a/extensions/multibindings/test/com/google/inject/multibindings/MapBinderTest.java
+++ b/extensions/multibindings/test/com/google/inject/multibindings/MapBinderTest.java
@@ -31,6 +31,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
+import com.google.common.testing.GcFinalization;
 import com.google.inject.AbstractModule;
 import com.google.inject.Binding;
 import com.google.inject.BindingAnnotation;
@@ -60,6 +61,7 @@
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.lang.annotation.Target;
+import java.lang.ref.WeakReference;
 import java.lang.reflect.Method;
 import java.util.Arrays;
 import java.util.Collections;
@@ -871,7 +873,7 @@
     expected.put(1, 1);
     expected.put(2, 2);
     assertEquals(expected, s1);
-  }  
+  }
 
   public void testTwoMapBindersAreDistinct() {
     Injector injector = Guice.createInjector(new AbstractModule() {
@@ -908,4 +910,32 @@
     assertFalse(map2Binding.containsElement(a));
     assertTrue(map2Binding.containsElement(b));
   }
+
+  // Tests for com.google.inject.internal.WeakKeySet not leaking memory.
+  public void testWeakKeySet_integration_mapbinder() {
+    Key<Map<String, String>> mapKey = Key.get(new TypeLiteral<Map<String, String>>() {});
+    
+    Injector parentInjector = Guice.createInjector(new AbstractModule() {
+          @Override protected void configure() {
+            bind(String.class).toInstance("hi");
+          }
+        });
+    WeakKeySetUtils.assertNotBlacklisted(parentInjector, mapKey);
+
+    Injector childInjector = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        MapBinder<String, String> binder =
+            MapBinder.newMapBinder(binder(), String.class, String.class);
+        binder.addBinding("bar").toInstance("foo");
+      }
+    });
+    WeakReference<Injector> weakRef = new WeakReference<Injector>(childInjector);
+    WeakKeySetUtils.assertBlacklisted(parentInjector, mapKey);
+    
+    // Clear the ref, GC, and ensure that we are no longer blacklisting.
+    childInjector = null;
+    
+    GcFinalization.awaitClear(weakRef);
+    WeakKeySetUtils.assertNotBlacklisted(parentInjector, mapKey);
+  }
 }
diff --git a/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java b/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java
index 9494e5e..d317525 100644
--- a/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java
+++ b/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java
@@ -34,6 +34,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
+import com.google.common.testing.GcFinalization;
 import com.google.inject.AbstractModule;
 import com.google.inject.Binding;
 import com.google.inject.BindingAnnotation;
@@ -72,6 +73,7 @@
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.lang.annotation.Target;
+import java.lang.ref.WeakReference;
 import java.lang.reflect.Method;
 import java.util.Arrays;
 import java.util.Collections;
@@ -1129,4 +1131,31 @@
     assertFalse(collector.optionalbinding.containsElement(b));
     assertTrue(collector.optionalbinding.containsElement(c));
   }
+  
+  // Tests for com.google.inject.internal.WeakKeySet not leaking memory.
+  public void testWeakKeySet_integration_multibinder() {
+    Key<Set<String>> setKey = Key.get(new TypeLiteral<Set<String>>() {});
+
+    Injector parentInjector = Guice.createInjector(new AbstractModule() {
+          @Override protected void configure() {
+            bind(String.class).toInstance("hi");
+          }
+        });
+    WeakKeySetUtils.assertNotBlacklisted(parentInjector, setKey);
+
+    Injector childInjector = parentInjector.createChildInjector(new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<String> binder = Multibinder.newSetBinder(binder(), String.class);
+        binder.addBinding().toInstance("foo");
+      }
+    });
+    WeakReference<Injector> weakRef = new WeakReference<Injector>(childInjector);
+    WeakKeySetUtils.assertBlacklisted(parentInjector, setKey);
+   
+    // Clear the ref, GC, and ensure that we are no longer blacklisting.
+    childInjector = null;
+   
+    GcFinalization.awaitClear(weakRef);
+    WeakKeySetUtils.assertNotBlacklisted(parentInjector, setKey);
+  }
 }
diff --git a/extensions/multibindings/test/com/google/inject/multibindings/OptionalBinderTest.java b/extensions/multibindings/test/com/google/inject/multibindings/OptionalBinderTest.java
index 1393e0c..246c7a3 100644
--- a/extensions/multibindings/test/com/google/inject/multibindings/OptionalBinderTest.java
+++ b/extensions/multibindings/test/com/google/inject/multibindings/OptionalBinderTest.java
@@ -29,6 +29,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
+import com.google.common.testing.GcFinalization;
 import com.google.inject.AbstractModule;
 import com.google.inject.Binding;
 import com.google.inject.BindingAnnotation;
@@ -59,6 +60,7 @@
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.lang.annotation.Target;
+import java.lang.ref.WeakReference;
 import java.lang.reflect.Method;
 import java.util.List;
 import java.util.Map.Entry;
@@ -911,6 +913,30 @@
     assertEquals(2, i2.intValue());
   }
   
+ // Tests for com.google.inject.internal.WeakKeySet not leaking memory.
+ public void testWeakKeySet_integration() {   
+   Injector parentInjector = Guice.createInjector(new AbstractModule() {
+         @Override protected void configure() {
+           bind(String.class).toInstance("hi");
+         }
+       });
+   WeakKeySetUtils.assertNotBlacklisted(parentInjector, Key.get(Integer.class));
+
+   Injector childInjector = parentInjector.createChildInjector(new AbstractModule() {
+     @Override protected void configure() {
+       OptionalBinder.newOptionalBinder(binder(), Integer.class).setDefault().toInstance(4);
+     }
+   });
+   WeakReference<Injector> weakRef = new WeakReference<Injector>(childInjector);
+   WeakKeySetUtils.assertBlacklisted(parentInjector, Key.get(Integer.class));
+   
+   // Clear the ref, GC, and ensure that we are no longer blacklisting.
+   childInjector = null;
+   
+   GcFinalization.awaitClear(weakRef);
+   WeakKeySetUtils.assertNotBlacklisted(parentInjector, Key.get(Integer.class));
+ }
+  
   @SuppressWarnings("unchecked") 
   private <V> Set<V> setOf(V... elements) {
     return ImmutableSet.copyOf(elements);
diff --git a/extensions/multibindings/test/com/google/inject/multibindings/WeakKeySetUtils.java b/extensions/multibindings/test/com/google/inject/multibindings/WeakKeySetUtils.java
new file mode 100644
index 0000000..0dc5a8e
--- /dev/null
+++ b/extensions/multibindings/test/com/google/inject/multibindings/WeakKeySetUtils.java
@@ -0,0 +1,68 @@
+/**
+ * Copyright (C) 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.inject.multibindings;
+
+import com.google.inject.Injector;
+import com.google.inject.Key;
+
+import junit.framework.TestCase;
+
+import java.lang.reflect.Field;
+import java.lang.reflect.Method;
+
+/**
+ * Utilities for verifying com.google.inject.internal.WeakKeySet is not leaking memory.
+ * 
+ * @author dweis@google.com (Daniel Weis)
+ */
+final class WeakKeySetUtils {
+  
+  private WeakKeySetUtils() {}
+  
+  static void assertBlacklisted(Injector injector, Key<?> key) {
+    assertBlacklistState(injector, key, true);
+  }
+ 
+  static void assertNotBlacklisted(Injector injector, Key<?> key) {
+    assertBlacklistState(injector, key, false);
+  }
+
+  private static final Field stateField;
+  private static final Method isBlacklistedMethod; 
+  static {
+    try {
+      stateField =
+          Class.forName("com.google.inject.internal.InjectorImpl").getDeclaredField("state");
+      stateField.setAccessible(true);
+      isBlacklistedMethod =
+          Class.forName("com.google.inject.internal.State").getMethod("isBlacklisted", Key.class);
+      isBlacklistedMethod.setAccessible(true);
+    } catch (Exception e) {
+      throw new Error(e);
+    }
+  }
+
+  private static void assertBlacklistState(Injector injector, Key<?> key, boolean isBlacklisted) {
+    try {
+      TestCase.assertEquals(
+          isBlacklisted,
+          ((Boolean) isBlacklistedMethod.invoke(stateField.get(injector), key)).booleanValue());
+    } catch (Exception e) {
+      throw new RuntimeException(e);
+    }
+  }
+}
diff --git a/extensions/pom.xml b/extensions/pom.xml
index 1298e5d..55ee9b8 100644
--- a/extensions/pom.xml
+++ b/extensions/pom.xml
@@ -55,6 +55,16 @@
       <scope>test</scope>
     </dependency>
     <!--
+     | Some extension tests depend on guava test libs which are not inherited
+     | from test scope.
+    -->
+    <dependency>
+      <groupId>com.google.guava</groupId>
+      <artifactId>guava-testlib</artifactId>
+      <version>16.0.1</version>
+      <scope>test</scope>
+    </dependency>
+    <!--
      | Some extension tests depend on cglib which is not embedded
      | in an execution that doesn't include package.
     -->
diff --git a/lib/build/guava-testlib-16.0.1.jar b/lib/build/guava-testlib-16.0.1.jar
new file mode 100644
index 0000000..59150aa
--- /dev/null
+++ b/lib/build/guava-testlib-16.0.1.jar
Binary files differ