An alternative way to support ShareableModule, Modules.override and Multibinder: use annotations that compare equal iff the binding strategy matches, so Guice will dedupe for us.

This CL includes a noteworthy adaptation of an earlier attempt which caused timeouts in some client tests, forcing a rollback ([]). Because Key caches its hashCode, we were inadvertently inserting every binding for a given multibound set into the same hashmap bucket, causing at best O(n^2) behaviour (and possibly worse, depending on how HashMap is implemented). To fix this, this CL adds changes to core Guice to recompute the Key's hashCode at injector construction time. (In fact, at the end of every Elements.getElements call, so any SPI-based code gets the same benefits.)
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=51233981
diff --git a/core/src/com/google/inject/Key.java b/core/src/com/google/inject/Key.java
index e8bba82..7842c66 100644
--- a/core/src/com/google/inject/Key.java
+++ b/core/src/com/google/inject/Key.java
@@ -131,6 +131,11 @@
     this.hashCode = computeHashCode();
   }
 
+  /**
+   * Computes the hash code for this key. This logic is duplicated in {@link
+   * com.google.inject.internal.RehashableKeys.Keys#needsRehashing}; if it is
+   * changed here, be sure to change it there also.
+   */
   private int computeHashCode() {
     return typeLiteral.hashCode() * 31 + annotationStrategy.hashCode();
   }
@@ -279,7 +284,7 @@
   /**
    * Returns a new key of the specified type with the same annotation as this
    * key.
-   * 
+   *
    * @since 3.0
    */
   public <T> Key<T> ofType(Class<T> type) {
@@ -289,7 +294,7 @@
   /**
    * Returns a new key of the specified type with the same annotation as this
    * key.
-   * 
+   *
    * @since 3.0
    */
   public Key<?> ofType(Type type) {
@@ -299,7 +304,7 @@
   /**
    * Returns a new key of the specified type with the same annotation as this
    * key.
-   * 
+   *
    * @since 3.0
    */
   public <T> Key<T> ofType(TypeLiteral<T> type) {
@@ -308,7 +313,7 @@
 
   /**
    * Returns true if this key has annotation attributes.
-   * 
+   *
    * @since 3.0
    */
   public boolean hasAttributes() {
@@ -318,7 +323,7 @@
   /**
    * Returns this key without annotation attributes, i.e. with only the
    * annotation type.
-   * 
+   *
    * @since 3.0
    */
   public Key<T> withoutAttributes() {
@@ -356,7 +361,7 @@
     if (isAllDefaultMethods(annotationType)) {
       return strategyFor(generateAnnotation(annotationType));
     }
-    
+
     checkNotNull(annotationType, "annotation type");
     ensureRetainedAtRuntime(annotationType);
     ensureIsBindingAnnotation(annotationType);
diff --git a/core/src/com/google/inject/internal/BindingBuilder.java b/core/src/com/google/inject/internal/BindingBuilder.java
index 7b89dcc..a6260f3 100644
--- a/core/src/com/google/inject/internal/BindingBuilder.java
+++ b/core/src/com/google/inject/internal/BindingBuilder.java
@@ -41,7 +41,7 @@
  * @author jessewilson@google.com (Jesse Wilson)
  */
 public class BindingBuilder<T> extends AbstractBindingBuilder<T>
-    implements AnnotatedBindingBuilder<T> {
+    implements AnnotatedBindingBuilder<T>, RehashableKeys {
 
   public BindingBuilder(Binder binder, List<Element> elements, Object source, Key<T> key) {
     super(binder, elements, source, key);
@@ -157,7 +157,6 @@
     }
 
     try {
-      @SuppressWarnings("unchecked") // safe; constructor is a subtype of toConstruct
       InjectionPoint constructorPoint = InjectionPoint.forConstructor(constructor, type);
       setBinding(new ConstructorBindingImpl<T>(base.getKey(), base.getSource(), base.getScoping(),
           constructorPoint, injectionPoints));
@@ -167,6 +166,10 @@
 
     return this;
   }
+  
+  public void rehashKeys() {
+    setBinding(getBinding().withRehashedKeys());
+  }
 
   @Override public String toString() {
     return "BindingBuilder<" + getBinding().getKey().getTypeLiteral() + ">";
diff --git a/core/src/com/google/inject/internal/BindingImpl.java b/core/src/com/google/inject/internal/BindingImpl.java
index 76b5b07..a891e9d 100644
--- a/core/src/com/google/inject/internal/BindingImpl.java
+++ b/core/src/com/google/inject/internal/BindingImpl.java
@@ -108,6 +108,10 @@
   protected BindingImpl<T> withKey(Key<T> key) {
     throw new AssertionError();
   }
+  
+  public BindingImpl<T> withRehashedKeys() {
+    throw new AssertionError();
+  }
 
   @Override public String toString() {
     return Objects.toStringHelper(Binding.class)
diff --git a/core/src/com/google/inject/internal/ConstructorBindingImpl.java b/core/src/com/google/inject/internal/ConstructorBindingImpl.java
index f8fbfd2..3a89154 100644
--- a/core/src/com/google/inject/internal/ConstructorBindingImpl.java
+++ b/core/src/com/google/inject/internal/ConstructorBindingImpl.java
@@ -18,6 +18,8 @@
 
 import static com.google.common.base.Preconditions.checkState;
 import static com.google.inject.internal.Annotations.findScopeAnnotation;
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
 
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableSet;
@@ -70,14 +72,14 @@
    * @param failIfNotLinked true if this ConstructorBindingImpl's InternalFactory should
    *                             only succeed if retrieved from a linked binding
    */
-  static <T> ConstructorBindingImpl<T> create(InjectorImpl injector, Key<T> key, 
+  static <T> ConstructorBindingImpl<T> create(InjectorImpl injector, Key<T> key,
       InjectionPoint constructorInjector, Object source, Scoping scoping, Errors errors,
       boolean failIfNotLinked, boolean failIfNotExplicit)
       throws ErrorsException {
     int numErrors = errors.size();
 
     @SuppressWarnings("unchecked") // constructorBinding guarantees type is consistent
-    Class<? super T> rawType = constructorInjector == null 
+    Class<? super T> rawType = constructorInjector == null
         ? key.getTypeLiteral().getRawType()
         : (Class) constructorInjector.getDeclaringType().getRawType();
 
@@ -124,7 +126,7 @@
     return new ConstructorBindingImpl<T>(
         injector, key, source, scopedFactory, scoping, factoryFactory, constructorInjector);
   }
-  
+
   /** Returns true if the inject annotation is on the constructor. */
   private static boolean hasAtInject(Constructor cxtor) {
     return cxtor.isAnnotationPresent(Inject.class)
@@ -139,7 +141,7 @@
     factory.provisionCallback =
       injector.provisionListenerStore.get(this);
   }
-  
+
   /** True if this binding has been initialized and is ready for use. */
   boolean isInitialized() {
     return factory.constructorInjector != null;
@@ -153,7 +155,7 @@
       return constructorInjectionPoint;
     }
   }
-  
+
   /** Returns a set of dependencies that can be iterated over to clean up stray JIT bindings. */
   Set<Dependency<?>> getInternalDependencies() {
     ImmutableSet.Builder<InjectionPoint> builder = ImmutableSet.builder();
@@ -168,10 +170,10 @@
       builder.add(getConstructor())
              .addAll(getInjectableMembers());
     }
-    
-    return Dependency.forInjectionPoints(builder.build());   
+
+    return Dependency.forInjectionPoints(builder.build());
   }
-  
+
   public <V> V acceptTargetVisitor(BindingTargetVisitor<? super T, V> visitor) {
     checkState(factory.constructorInjector != null, "not initialized");
     return visitor.visit(this);
@@ -211,6 +213,14 @@
         null, key, getSource(), factory, getScoping(), factory, constructorInjectionPoint);
   }
 
+  @Override public BindingImpl<T> withRehashedKeys() {
+    if (needsRehashing(getKey())) {
+      return withKey(rehash(getKey()));
+    } else {
+      return this;
+    }
+  }
+
   @SuppressWarnings("unchecked") // the raw constructor member and declaring type always agree
   public void applyTo(Binder binder) {
     InjectionPoint constructor = getConstructor();
@@ -225,7 +235,7 @@
         .add("scope", getScoping())
         .toString();
   }
-  
+
   @Override
   public boolean equals(Object obj) {
     if(obj instanceof ConstructorBindingImpl) {
@@ -237,7 +247,7 @@
       return false;
     }
   }
-  
+
   @Override
   public int hashCode() {
     return Objects.hashCode(getKey(), getScoping(), constructorInjectionPoint);
@@ -249,7 +259,7 @@
     private boolean allowCircularProxy;
     private ConstructorInjector<T> constructorInjector;
     private ProvisionListenerStackCallback<T> provisionCallback;
-    
+
     Factory(boolean failIfNotLinked, Key<?> key) {
       this.failIfNotLinked = failIfNotLinked;
       this.key = key;
@@ -259,7 +269,7 @@
     public T get(Errors errors, InternalContext context, Dependency<?> dependency, boolean linked)
         throws ErrorsException {
       checkState(constructorInjector != null, "Constructor not ready");
-      
+
       if(failIfNotLinked && !linked) {
         throw errors.jitDisabled(key).toException();
       }
diff --git a/core/src/com/google/inject/internal/InstanceBindingImpl.java b/core/src/com/google/inject/internal/InstanceBindingImpl.java
index 57129b1..82d8908 100644
--- a/core/src/com/google/inject/internal/InstanceBindingImpl.java
+++ b/core/src/com/google/inject/internal/InstanceBindingImpl.java
@@ -16,6 +16,9 @@
 
 package com.google.inject.internal;
 
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
+
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableSet;
 import com.google.inject.Binder;
@@ -83,6 +86,14 @@
     return new InstanceBindingImpl<T>(getSource(), key, getScoping(), injectionPoints, instance);
   }
 
+  public BindingImpl<T> withRehashedKeys() {
+    if (needsRehashing(getKey())) {
+      return withKey(rehash(getKey()));
+    } else {
+      return this;
+    }
+  }
+
   public void applyTo(Binder binder) {
     // instance bindings aren't scoped
     binder.withSource(getSource()).bind(getKey()).toInstance(instance);
@@ -95,7 +106,7 @@
         .add("instance", instance)
         .toString();
   }
-  
+
   @Override
   public boolean equals(Object obj) {
     if(obj instanceof InstanceBindingImpl) {
@@ -107,7 +118,7 @@
       return false;
     }
   }
-  
+
   @Override
   public int hashCode() {
     return Objects.hashCode(getKey(), getScoping());
diff --git a/core/src/com/google/inject/internal/LinkedBindingImpl.java b/core/src/com/google/inject/internal/LinkedBindingImpl.java
index 33b9a7c..71ccf8e 100644
--- a/core/src/com/google/inject/internal/LinkedBindingImpl.java
+++ b/core/src/com/google/inject/internal/LinkedBindingImpl.java
@@ -16,6 +16,9 @@
 
 package com.google.inject.internal;
 
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
+
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableSet;
 import com.google.inject.Binder;
@@ -50,7 +53,7 @@
   public Key<? extends T> getLinkedKey() {
     return targetKey;
   }
-  
+
   public Set<Dependency<?>> getDependencies() {
     return ImmutableSet.<Dependency<?>>of(Dependency.get(targetKey));
   }
@@ -63,6 +66,20 @@
     return new LinkedBindingImpl<T>(getSource(), key, getScoping(), targetKey);
   }
 
+  public BindingImpl<T> withRehashedKeys() {
+    boolean keyNeedsRehashing = needsRehashing(getKey());
+    boolean targetKeyNeedsRehashing = needsRehashing(targetKey);
+    if (keyNeedsRehashing || targetKeyNeedsRehashing) {
+      return new LinkedBindingImpl<T>(
+          getSource(),
+          keyNeedsRehashing ? rehash(getKey()) : getKey(),
+          getScoping(),
+          targetKeyNeedsRehashing ? rehash(targetKey) : targetKey);
+    } else {
+      return this;
+    }
+  }
+
   public void applyTo(Binder binder) {
     getScoping().applyTo(binder.withSource(getSource()).bind(getKey()).to(getLinkedKey()));
   }
@@ -75,7 +92,7 @@
         .add("target", targetKey)
         .toString();
   }
-  
+
   @Override
   public boolean equals(Object obj) {
     if(obj instanceof LinkedBindingImpl) {
@@ -87,7 +104,7 @@
       return false;
     }
   }
-  
+
   @Override
   public int hashCode() {
     return Objects.hashCode(getKey(), getScoping(), targetKey);
diff --git a/core/src/com/google/inject/internal/LinkedProviderBindingImpl.java b/core/src/com/google/inject/internal/LinkedProviderBindingImpl.java
index f2204ba..4841e92 100644
--- a/core/src/com/google/inject/internal/LinkedProviderBindingImpl.java
+++ b/core/src/com/google/inject/internal/LinkedProviderBindingImpl.java
@@ -16,6 +16,9 @@
 
 package com.google.inject.internal;
 
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
+
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableSet;
 import com.google.inject.Binder;
@@ -32,7 +35,7 @@
 
   final Key<? extends javax.inject.Provider<? extends T>> providerKey;
   final DelayedInitialize delayedInitializer;
-  
+
   private LinkedProviderBindingImpl(InjectorImpl injector, Key<T> key, Object source,
       InternalFactory<? extends T> internalFactory, Scoping scoping,
       Key<? extends javax.inject.Provider<? extends T>> providerKey,
@@ -54,7 +57,7 @@
     this.providerKey = providerKey;
     this.delayedInitializer = null;
   }
-  
+
   static <T> LinkedProviderBindingImpl<T> createWithInitializer(InjectorImpl injector, Key<T> key,
       Object source, InternalFactory<? extends T> internalFactory, Scoping scoping,
       Key<? extends javax.inject.Provider<? extends T>> providerKey,
@@ -70,17 +73,17 @@
   public Key<? extends javax.inject.Provider<? extends T>> getProviderKey() {
     return providerKey;
   }
-  
+
   public void initialize(InjectorImpl injector, Errors errors) throws ErrorsException {
     if (delayedInitializer != null) {
       delayedInitializer.initialize(injector, errors);
     }
   }
-  
+
   public Set<Dependency<?>> getDependencies() {
     return ImmutableSet.<Dependency<?>>of(Dependency.get(providerKey));
   }
-  
+
   public BindingImpl<T> withScoping(Scoping scoping) {
     return new LinkedProviderBindingImpl<T>(getSource(), getKey(), scoping, providerKey);
   }
@@ -89,6 +92,20 @@
     return new LinkedProviderBindingImpl<T>(getSource(), key, getScoping(), providerKey);
   }
 
+  public BindingImpl<T> withRehashedKeys() {
+    boolean keyNeedsRehashing = needsRehashing(getKey());
+    boolean providerKeyNeedsRehashing = needsRehashing(providerKey);
+    if (keyNeedsRehashing || providerKeyNeedsRehashing) {
+      return new LinkedProviderBindingImpl<T>(
+          getSource(),
+          keyNeedsRehashing ? rehash(getKey()) : getKey(),
+          getScoping(),
+          providerKeyNeedsRehashing ? rehash(providerKey) : providerKey);
+    } else {
+      return this;
+    }
+  }
+
   public void applyTo(Binder binder) {
     getScoping().applyTo(binder.withSource(getSource())
         .bind(getKey()).toProvider(getProviderKey()));
@@ -102,7 +119,7 @@
         .add("provider", providerKey)
         .toString();
   }
-  
+
   @Override
   public boolean equals(Object obj) {
     if(obj instanceof LinkedProviderBindingImpl) {
@@ -114,7 +131,7 @@
       return false;
     }
   }
-  
+
   @Override
   public int hashCode() {
     return Objects.hashCode(getKey(), getScoping(), providerKey);
diff --git a/core/src/com/google/inject/internal/ProviderInstanceBindingImpl.java b/core/src/com/google/inject/internal/ProviderInstanceBindingImpl.java
index ad02fef..971a1d0 100644
--- a/core/src/com/google/inject/internal/ProviderInstanceBindingImpl.java
+++ b/core/src/com/google/inject/internal/ProviderInstanceBindingImpl.java
@@ -16,6 +16,9 @@
 
 package com.google.inject.internal;
 
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
+
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableSet;
 import com.google.inject.Binder;
@@ -86,6 +89,14 @@
         getSource(), key, getScoping(), injectionPoints, providerInstance);
   }
 
+  public BindingImpl<T> withRehashedKeys() {
+    if (needsRehashing(getKey())) {
+      return withKey(rehash(getKey()));
+    } else {
+      return this;
+    }
+  }
+
   public void applyTo(Binder binder) {
     getScoping().applyTo(
         binder.withSource(getSource()).bind(getKey()).toProvider(getProviderInstance()));
@@ -100,7 +111,7 @@
         .add("provider", providerInstance)
         .toString();
   }
-  
+
   @Override
   public boolean equals(Object obj) {
     if(obj instanceof ProviderInstanceBindingImpl) {
@@ -112,7 +123,7 @@
       return false;
     }
   }
-  
+
   @Override
   public int hashCode() {
     return Objects.hashCode(getKey(), getScoping());
diff --git a/core/src/com/google/inject/internal/RehashableKeys.java b/core/src/com/google/inject/internal/RehashableKeys.java
new file mode 100644
index 0000000..2fff215
--- /dev/null
+++ b/core/src/com/google/inject/internal/RehashableKeys.java
@@ -0,0 +1,40 @@
+package com.google.inject.internal;
+
+import com.google.inject.Key;
+
+/**
+ * Interface for types that can rehash their {@link Key} instances.
+ *
+ * @author chrispurcell@google.com (Chris Purcell)
+ */
+public interface RehashableKeys {
+  void rehashKeys();
+
+  /** Utility methods for key rehashing. */
+  public static class Keys {
+
+    /**
+     * Returns true if the cached hashcode for the given key is out-of-date. This will only occur
+     * if the key contains a mutable annotation.
+     */
+    public static boolean needsRehashing(Key<?> key) {
+      if (!key.hasAttributes()) {
+        return false;
+      }
+      int newHashCode = key.getTypeLiteral().hashCode() * 31 + key.getAnnotation().hashCode();
+      return (key.hashCode() != newHashCode);
+    }
+
+    /** Returns a copy of the given key with an up-to-date hashcode. */
+    public static <T> Key<T> rehash(Key<T> key) {
+      if (key.hasAttributes()) {
+        // This will recompute the hashcode for us.
+        return Key.get(key.getTypeLiteral(), key.getAnnotation());
+      } else {
+        return key;
+      }
+    }
+
+    private Keys() { }
+  }
+}
diff --git a/core/src/com/google/inject/internal/UntargettedBindingImpl.java b/core/src/com/google/inject/internal/UntargettedBindingImpl.java
index 8af74a2..0c31130 100644
--- a/core/src/com/google/inject/internal/UntargettedBindingImpl.java
+++ b/core/src/com/google/inject/internal/UntargettedBindingImpl.java
@@ -16,6 +16,9 @@
 
 package com.google.inject.internal;
 
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
+
 import com.google.common.base.Objects;
 import com.google.inject.Binder;
 import com.google.inject.Key;
@@ -49,6 +52,14 @@
     return new UntargettedBindingImpl<T>(getSource(), key, getScoping());
   }
 
+  public BindingImpl<T> withRehashedKeys() {
+    if (needsRehashing(getKey())) {
+      return withKey(rehash(getKey()));
+    } else {
+      return this;
+    }
+  }
+
   public void applyTo(Binder binder) {
     getScoping().applyTo(binder.withSource(getSource()).bind(getKey()));
   }
@@ -58,7 +69,7 @@
         .add("key", getKey())
         .add("source", getSource())
         .toString();
-  }  
+  }
 
   @Override
   public boolean equals(Object obj) {
@@ -70,7 +81,7 @@
       return false;
     }
   }
-  
+
   @Override
   public int hashCode() {
     return Objects.hashCode(getKey(), getScoping());
diff --git a/core/src/com/google/inject/spi/Elements.java b/core/src/com/google/inject/spi/Elements.java
index 73999b3..65cfc28 100644
--- a/core/src/com/google/inject/spi/Elements.java
+++ b/core/src/com/google/inject/spi/Elements.java
@@ -43,6 +43,7 @@
 import com.google.inject.internal.ExposureBuilder;
 import com.google.inject.internal.PrivateElementsImpl;
 import com.google.inject.internal.ProviderMethodsModule;
+import com.google.inject.internal.RehashableKeys;
 import com.google.inject.internal.util.SourceProvider;
 import com.google.inject.internal.util.StackTraceElements;
 import com.google.inject.matcher.Matcher;
@@ -120,6 +121,7 @@
       // Free the memory consumed by the stack trace elements cache
       StackTraceElements.clearCache();
     }
+    binder.rehashKeys();
     return Collections.unmodifiableList(binder.elements);
   }
 
@@ -147,10 +149,11 @@
         guice_include_stack_traces_property);
   }
 
-  private static class RecordingBinder implements Binder, PrivateBinder {
+  private static class RecordingBinder implements Binder, PrivateBinder, RehashableKeys {
     private final Stage stage;
     private final Set<Module> modules;
     private final List<Element> elements;
+    private final List<RehashableKeys> rehashables;
     private final Object source;
     /** The current modules stack */
     private ModuleSource moduleSource = null;
@@ -164,6 +167,7 @@
       this.stage = stage;
       this.modules = Sets.newHashSet();
       this.elements = Lists.newArrayList();
+      this.rehashables = Lists.newArrayList();
       this.source = null;
       this.sourceProvider = SourceProvider.DEFAULT_INSTANCE.plusSkippedClasses(
           Elements.class, RecordingBinder.class, AbstractModule.class,
@@ -180,6 +184,7 @@
       this.stage = prototype.stage;
       this.modules = prototype.modules;
       this.elements = prototype.elements;
+      this.rehashables = prototype.rehashables;
       this.source = source;
       this.moduleSource = prototype.moduleSource;
       this.sourceProvider = sourceProvider;
@@ -192,6 +197,7 @@
       this.stage = parent.stage;
       this.modules = Sets.newHashSet();
       this.elements = privateElements.getElementsMutable();
+      this.rehashables = Lists.newArrayList();
       this.source = parent.source;
       this.moduleSource = parent.moduleSource;
       this.sourceProvider = parent.sourceProvider;
@@ -215,7 +221,7 @@
 
     @SuppressWarnings("unchecked") // it is safe to use the type literal for the raw type
     public void requestInjection(Object instance) {
-      requestInjection((TypeLiteral) TypeLiteral.get(instance.getClass()), instance);
+      requestInjection((TypeLiteral<Object>) TypeLiteral.get(instance.getClass()), instance);
     }
 
     public <T> void requestInjection(TypeLiteral<T> type, T instance) {
@@ -294,7 +300,9 @@
     }
 
     public <T> AnnotatedBindingBuilder<T> bind(Key<T> key) {
-      return new BindingBuilder<T>(this, elements, getElementSource(), key);
+      BindingBuilder<T> builder = new BindingBuilder<T>(this, elements, getElementSource(), key);
+      rehashables.add(builder);
+      return builder;
     }
 
     public <T> AnnotatedBindingBuilder<T> bind(TypeLiteral<T> typeLiteral) {
@@ -312,6 +320,7 @@
     public <T> Provider<T> getProvider(final Key<T> key) {
       final ProviderLookup<T> element = new ProviderLookup<T>(getElementSource(), key);
       elements.add(element);
+      rehashables.add(element.getKeyRehasher());
       return element.getProvider();
     }
 
@@ -340,8 +349,10 @@
 
     public PrivateBinder newPrivateBinder() {
       PrivateElementsImpl privateElements = new PrivateElementsImpl(getElementSource());
+      RecordingBinder binder = new RecordingBinder(this, privateElements);
       elements.add(privateElements);
-      return new RecordingBinder(this, privateElements);
+      rehashables.add(binder);
+      return binder;
     }
 
     public void disableCircularProxies() {
@@ -448,6 +459,12 @@
       return partialCallStack;
     }
 
+    @Override public void rehashKeys() {
+      for (RehashableKeys rehashable : rehashables) {
+        rehashable.rehashKeys();
+      }
+    }
+
     @Override public String toString() {
       return "Binder";
     }
diff --git a/core/src/com/google/inject/spi/ProviderLookup.java b/core/src/com/google/inject/spi/ProviderLookup.java
index cb58591..050b59c 100644
--- a/core/src/com/google/inject/spi/ProviderLookup.java
+++ b/core/src/com/google/inject/spi/ProviderLookup.java
@@ -18,10 +18,13 @@
 
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
 
 import com.google.inject.Binder;
 import com.google.inject.Key;
 import com.google.inject.Provider;
+import com.google.inject.internal.RehashableKeys;
 
 /**
  * A lookup of the provider for a type. Lookups are created explicitly in a module using
@@ -35,7 +38,7 @@
  */
 public final class ProviderLookup<T> implements Element {
   private final Object source;
-  private final Key<T> key;
+  private Key<T> key;  // effectively final, as it will not change once it escapes into user code
   private Provider<T> delegate;
 
   public ProviderLookup(Object source, Key<T> key) {
@@ -98,4 +101,14 @@
       }
     };
   }
+
+  RehashableKeys getKeyRehasher() {
+    return new RehashableKeys() {
+      @Override public void rehashKeys() {
+        if (needsRehashing(key)) {
+          key = rehash(key);
+        }
+      }
+    };
+  }
 }
diff --git a/core/test/com/google/inject/AllTests.java b/core/test/com/google/inject/AllTests.java
index 2030726..4740b93 100644
--- a/core/test/com/google/inject/AllTests.java
+++ b/core/test/com/google/inject/AllTests.java
@@ -18,6 +18,7 @@
 
 import com.google.common.collect.ImmutableSet;
 import com.google.inject.internal.MoreTypesTest;
+import com.google.inject.internal.RehashableKeysTest;
 import com.google.inject.internal.UniqueAnnotationsTest;
 import com.google.inject.internal.util.LineNumbersTest;
 import com.google.inject.matcher.MatcherTest;
@@ -94,6 +95,7 @@
     suite.addTestSuite(ProvisionListenerTest.class);
     // ProxyFactoryTest is AOP-only
     suite.addTestSuite(ReflectionTest.class);
+    suite.addTestSuite(RehashableKeysTest.class);
     suite.addTestSuite(RequestInjectionTest.class);
     suite.addTestSuite(RequireAtInjectOnConstructorsTest.class);
     suite.addTestSuite(ScopesTest.class);
diff --git a/core/test/com/google/inject/internal/RehashableKeysTest.java b/core/test/com/google/inject/internal/RehashableKeysTest.java
new file mode 100644
index 0000000..d1676ac
--- /dev/null
+++ b/core/test/com/google/inject/internal/RehashableKeysTest.java
@@ -0,0 +1,132 @@
+package com.google.inject.internal;
+
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import com.google.inject.BindingAnnotation;
+import com.google.inject.Key;
+import com.google.inject.name.Names;
+
+import junit.framework.TestCase;
+
+import java.lang.annotation.Annotation;
+import java.lang.annotation.Retention;
+
+/**
+ * @author chrispurcell@google.com (Chris Purcell)
+ */
+public class RehashableKeysTest extends TestCase {
+
+  public void testNeedsRehashing_noAnnotation() {
+    Key<?> key = Key.get(Integer.class);
+    assertFalse(needsRehashing(key));
+  }
+
+  public void testNeedsRehashing_noParametersAnnotation() {
+    Key<?> key = Key.get(Integer.class, NoParametersAnnotation.class);
+    assertFalse(needsRehashing(key));
+  }
+
+  public void testNeedsRehashing_immutableAnnotation() {
+    Key<?> key = Key.get(Integer.class, Names.named("testy"));
+    assertFalse(needsRehashing(key));
+  }
+
+  public void testNeedsRehashing_mutableAnnotation() {
+    MutableTestAnnotation annotation = new MutableTestAnnotation(100);
+    Key<?> key = Key.get(Integer.class, annotation);
+    assertFalse(needsRehashing(key));
+
+    annotation.setValue(101);
+    assertTrue(needsRehashing(key));
+
+    Key<?> key2 = Key.get(Integer.class, annotation);
+    assertTrue(needsRehashing(key));
+    assertFalse(needsRehashing(key2));
+
+    annotation.setValue(102);
+    assertTrue(needsRehashing(key));
+    assertTrue(needsRehashing(key2));
+
+    annotation.setValue(100);
+    assertFalse(needsRehashing(key));
+    assertTrue(needsRehashing(key2));
+  }
+
+  public void testRehash_noParametersAnnotation() {
+    Key<?> key = Key.get(Integer.class, NoParametersAnnotation.class);
+    assertSame(key, rehash(key));
+  }
+
+  public void testRehash_noAnnotation() {
+    Key<?> key = Key.get(Integer.class);
+    assertSame(key, rehash(key));
+  }
+
+  public void testRehash_immutableAnnotation() {
+    Key<?> key = Key.get(Integer.class, Names.named("testy"));
+    Key<?> keyCopy = rehash(key);
+    assertEquals(key, keyCopy);
+    assertEquals(key.hashCode(), keyCopy.hashCode());
+  }
+
+  public void testRehash_mutableAnnotation() {
+    MutableTestAnnotation annotation = new MutableTestAnnotation(100);
+    Key<?> key = Key.get(Integer.class, annotation);
+    Key<?> keyCopy = rehash(key);
+    assertTrue(key.equals(keyCopy));
+    assertTrue(key.hashCode() == keyCopy.hashCode());
+
+    annotation.setValue(101);
+    Key<?> keyCopy2 = rehash(key);
+    assertTrue(key.equals(keyCopy2));
+    assertFalse(key.hashCode() == keyCopy2.hashCode());
+
+    annotation.setValue(100);
+    Key<?> keyCopy3 = rehash(keyCopy2);
+    assertTrue(key.equals(keyCopy3));
+    assertTrue(key.hashCode() == keyCopy3.hashCode());
+    assertTrue(keyCopy2.equals(keyCopy3));
+    assertFalse(keyCopy2.hashCode() == keyCopy3.hashCode());
+  }
+
+  @Retention(RUNTIME) @BindingAnnotation
+  private @interface NoParametersAnnotation { }
+
+  @Retention(RUNTIME) @BindingAnnotation
+  private @interface TestAnnotation {
+    int value();
+  }
+
+  private static class MutableTestAnnotation implements TestAnnotation {
+
+    private int value;
+
+    MutableTestAnnotation(int value) {
+      this.value = value;
+    }
+
+    public Class<? extends Annotation> annotationType() {
+      return TestAnnotation.class;
+    }
+
+    public int value() {
+      return value;
+    }
+
+    void setValue(int value) {
+      this.value = value;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      return (obj instanceof TestAnnotation) && (((TestAnnotation) obj).value() == value);
+    }
+
+    @Override
+    public int hashCode() {
+      return value;
+    }
+  }
+}
diff --git a/extensions/multibindings/src/com/google/inject/multibindings/MapBinder.java b/extensions/multibindings/src/com/google/inject/multibindings/MapBinder.java
index c6c4f0e..2b0a2dc 100644
--- a/extensions/multibindings/src/com/google/inject/multibindings/MapBinder.java
+++ b/extensions/multibindings/src/com/google/inject/multibindings/MapBinder.java
@@ -16,6 +16,8 @@
 
 package com.google.inject.multibindings;
 
+import static com.google.inject.internal.RehashableKeys.Keys.needsRehashing;
+import static com.google.inject.internal.RehashableKeys.Keys.rehash;
 import static com.google.inject.multibindings.Element.Type.MAPBINDER;
 import static com.google.inject.multibindings.Multibinder.checkConfiguration;
 import static com.google.inject.multibindings.Multibinder.checkNotNull;
@@ -95,7 +97,7 @@
  * that module can order its bindings appropriately. Avoid relying on the
  * iteration order of elements contributed by different modules, since there is
  * no equivalent mechanism to order modules.
- * 
+ *
  * <p>The map is unmodifiable.  Elements can only be added to the map by
  * configuring the MapBinder.  Elements can never be removed from the map.
  *
@@ -224,7 +226,7 @@
         Map.class, Entry.class, keyType.getType(), Types.providerOf(valueType.getType())));
   }
 
-  private static <K, V> MapBinder<K, V> newMapBinder(Binder binder, 
+  private static <K, V> MapBinder<K, V> newMapBinder(Binder binder,
       TypeLiteral<K> keyType, TypeLiteral<V> valueType,
       Key<Map<K, V>> mapKey, Key<Map<K, Provider<V>>> providerMapKey,
       Key<Map<K, Set<V>>> multimapKey, Key<Map<K, Set<Provider<V>>>> providerMultimapKey,
@@ -301,7 +303,7 @@
 
     /* the target injector's binder. non-null until initialization, null afterwards */
     private Binder binder;
-    
+
     private boolean permitDuplicates;
     private ImmutableList<Map.Entry<K, Binding<V>>> mapBindings;
 
@@ -384,7 +386,7 @@
       });
 
       final Provider<Map<K, Provider<V>>> mapProvider = binder.getProvider(providerMapKey);
-      binder.bind(mapKey).toProvider(new RealMapWithExtensionProvider<Map<K, V>>(mapKey) {        
+      binder.bind(mapKey).toProvider(new RealMapWithExtensionProvider<Map<K, V>>(mapKey) {
         public Map<K, V> get() {
           Map<K, V> map = new LinkedHashMap<K, V>();
           for (Entry<K, Provider<V>> entry : mapProvider.get().entrySet()) {
@@ -428,7 +430,7 @@
           if (isInitialized()) {
             return (List)mapBindings; // safe because mapBindings is immutable
           } else {
-            throw new UnsupportedOperationException("getElements() not supported for module bindings");   
+            throw new UnsupportedOperationException("getElements() not supported for module bindings");
           }
         }
 
@@ -436,7 +438,7 @@
           if (isInitialized()) {
             return permitDuplicates;
           } else {
-            throw new UnsupportedOperationException("permitsDuplicates() not supported for module bindings");   
+            throw new UnsupportedOperationException("permitsDuplicates() not supported for module bindings");
           }
         }
 
@@ -453,7 +455,7 @@
               return false; // cannot match;
             }
 
-            return key.equals(mapKey) 
+            return key.equals(mapKey)
                 || key.equals(providerMapKey)
                 || key.equals(multimapKey)
                 || key.equals(providerMultimapKey)
@@ -576,7 +578,7 @@
       }
 
       @Override public boolean equals(Object o) {
-        return o instanceof MultimapBinder 
+        return o instanceof MultimapBinder
             && ((MultimapBinder<?, ?>) o).multimapKey.equals(multimapKey);
       }
     }
@@ -585,23 +587,30 @@
      * Implementation of {@code {@link Map.Entry}&lt;K, {@link Provider}&lt;V&gt;&gt;} that
      * defines equality based on the provider's key rather than the provider itself. This allows
      * Guice to remove duplicate bindings.
-     * 
+     *
      * @param <K> the map's key type
      * @param <V> the type provided by the map's values
      */
     private static final class ProviderMapEntry<K, V> implements Map.Entry<K, Provider<V>> {
       private final K key;
       private final Provider<V> provider;
-      private final Key<V> valueKey;
+      private volatile Key<V> valueKey;
 
       private ProviderMapEntry(K key, Provider<V> provider, Key<V> valueKey) {
         this.key = key;
         this.provider = provider;
         this.valueKey = valueKey;
       }
-      
+
       public Key<V> getValueKey() {
-        return valueKey;
+        // Every time, check if the value key needs rehashing.
+        // If so, update the field as an optimization for next time.
+        Key<V> currentValueKey = valueKey;
+        if (needsRehashing(currentValueKey)) {
+          currentValueKey = rehash(currentValueKey);
+          valueKey = currentValueKey;
+        }
+        return currentValueKey;
       }
 
       public K getKey() {
@@ -624,12 +633,15 @@
       @Override public boolean equals(Object obj) {
         return obj instanceof ProviderMapEntry
             && key.equals(((ProviderMapEntry<?, ?>) obj).getKey())
-            && valueKey.equals(((ProviderMapEntry<?, ?>) obj).getValueKey());
+            && getValueKey().equals(((ProviderMapEntry<?, ?>) obj).getValueKey());
       }
 
+      /**
+       * Again, we are not following the normal rules for Map.Entry, this time to avoid
+       * our hashCode changing if our {@link #valueKey} does.
+       */
       @Override public int hashCode() {
-        return 127 * ("key".hashCode() ^ key.hashCode())
-            + 127 * ("valueKey".hashCode() ^ valueKey.hashCode());
+        return key.hashCode();
       }
 
       @Override public String toString() {
@@ -644,24 +656,24 @@
         super(equality);
       }
     }
-    
+
     /**
      * A base class for ProviderWithDependencies that need equality
      * based on a specific object.
      */
     private static abstract class RealMapBinderProviderWithDependencies<T> implements ProviderWithDependencies<T> {
       private final Object equality;
-      
+
       public RealMapBinderProviderWithDependencies(Object equality) {
         this.equality = equality;
       }
-      
+
       @Override
       public boolean equals(Object obj) {
         return this.getClass() == obj.getClass() &&
           equality.equals(((RealMapBinderProviderWithDependencies<?>)obj).equality);
       }
-      
+
       @Override
       public int hashCode() {
         return equality.hashCode();
diff --git a/extensions/multibindings/src/com/google/inject/multibindings/RealElement.java b/extensions/multibindings/src/com/google/inject/multibindings/RealElement.java
index 198c98e..185d647 100644
--- a/extensions/multibindings/src/com/google/inject/multibindings/RealElement.java
+++ b/extensions/multibindings/src/com/google/inject/multibindings/RealElement.java
@@ -37,8 +37,7 @@
  * 
  * <p>Annotation equality is defined based on the binding it is used in, letting Guice spot and
  * remove duplicate bindings without false conflicts. However, as the binding is mutable, so is
- * the annotation. To minimise issues with hashtables, the hashCode will not mutate once the
- * binding type has been set.
+ * the annotation.
  * 
  * @author chrispurcell@google.com (Chris Purcell)
  */
@@ -149,23 +148,13 @@
   
   /**
    * Returns the hash code of this annotation. This depends on the binding the annotation is in.
-   * It is guaranteed, however, that the hash code will not change once the binding has been
-   * built.
    * 
    * <p>This <b>does not</b> match the definition of {@link Annotation#hashCode}. However, as
    * these annotations will only ever be used within Guice, and {@link Element} itself is package
    * private and will never be used as an annotation, this should not cause problems.
    */
   @Override public int hashCode() {
-    switch (targetType) {
-      case INSTANCE:
-      case PROVIDER_INSTANCE:
-        // Target is mutable; don't include it in the hash.
-        return Objects.hashCode(setName, type, mapKey, scope, targetType);
-        
-      default:
-        return Objects.hashCode(setName, type, mapKey, scope, targetType, target);
-    }
+    return Objects.hashCode(setName, type, mapKey, scope, targetType, target);
   }
 
   private enum TargetType {
diff --git a/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java b/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java
index 70b88bf..70be338 100644
--- a/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java
+++ b/extensions/multibindings/test/com/google/inject/multibindings/MultibinderTest.java
@@ -27,6 +27,8 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.inject.AbstractModule;
 import com.google.inject.Binding;
@@ -42,10 +44,13 @@
 import com.google.inject.Scopes;
 import com.google.inject.Stage;
 import com.google.inject.TypeLiteral;
+import com.google.inject.internal.RehashableKeys;
 import com.google.inject.name.Named;
 import com.google.inject.name.Names;
 import com.google.inject.spi.DefaultBindingTargetVisitor;
 import com.google.inject.spi.Dependency;
+import com.google.inject.spi.Element;
+import com.google.inject.spi.Elements;
 import com.google.inject.spi.HasDependencies;
 import com.google.inject.spi.InstanceBinding;
 import com.google.inject.spi.LinkedKeyBinding;
@@ -70,6 +75,7 @@
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 /**
@@ -83,6 +89,8 @@
   final TypeLiteral<Set<Integer>> setOfInteger = new TypeLiteral<Set<Integer>>() {};
   final TypeLiteral<String> stringType = TypeLiteral.get(String.class);
   final TypeLiteral<Integer> intType = TypeLiteral.get(Integer.class);
+  final TypeLiteral<List<String>> listOfStrings = new TypeLiteral<List<String>>() {};
+  final TypeLiteral<Set<List<String>>> setOfListOfStrings = new TypeLiteral<Set<List<String>>>() {};
 
   public void testMultibinderAggregatesMultipleModules() {
     Module abc = new AbstractModule() {
@@ -360,7 +368,7 @@
         return String.format("ValueType(%d,%d)", a, b);
       }
     }
-    
+
     Module module1 = new AbstractModule() {
       protected void configure() {
         final Multibinder<ValueType> multibinder =
@@ -667,7 +675,7 @@
   /**
    * Doubly-installed modules should not conflict, even when one is overridden.
    */
-  public void testModuleOverrideRepeatedInstallsAndMultibindings() {
+  public void testModuleOverrideRepeatedInstallsAndMultibindings_toInstance() {
     Module ab = new AbstractModule() {
       @Override protected void configure() {
         Multibinder<String> multibinder = Multibinder.newSetBinder(binder(), String.class);
@@ -675,20 +683,168 @@
         multibinder.addBinding().toInstance("B");
       }
     };
-    
+
     // Guice guarantees this assertion, as the same module cannot be installed twice.
     assertEquals(ImmutableSet.of("A", "B"),
         Guice.createInjector(ab, ab).getInstance(Key.get(setOfString)));
-    
+
     // Guice will only guarantee this assertion if Multibinder ensures the bindings match.
     Injector injector = Guice.createInjector(ab, Modules.override(ab).with(ab));
     assertEquals(ImmutableSet.of("A", "B"),
         injector.getInstance(Key.get(setOfString)));
   }
 
+  public void testModuleOverrideRepeatedInstallsAndMultibindings_toKey() {
+    Module ab = new AbstractModule() {
+      @Override protected void configure() {
+        Key<String> aKey = Key.get(String.class, Names.named("A_string"));
+        Key<String> bKey = Key.get(String.class, Names.named("B_string"));
+        bind(aKey).toInstance("A");
+        bind(bKey).toInstance("B");
+
+        Multibinder<String> multibinder = Multibinder.newSetBinder(binder(), String.class);
+        multibinder.addBinding().to(aKey);
+        multibinder.addBinding().to(bKey);
+      }
+    };
+
+    // Guice guarantees this assertion, as the same module cannot be installed twice.
+    assertEquals(ImmutableSet.of("A", "B"),
+        Guice.createInjector(ab, ab).getInstance(Key.get(setOfString)));
+
+    // Guice will only guarantee this assertion if Multibinder ensures the bindings match.
+    Injector injector = Guice.createInjector(ab, Modules.override(ab).with(ab));
+    assertEquals(ImmutableSet.of("A", "B"),
+        injector.getInstance(Key.get(setOfString)));
+  }
+
+  public void testModuleOverrideRepeatedInstallsAndMultibindings_toProviderInstance() {
+    // Providers#of() does not redefine equals/hashCode, so use the same one both times.
+    final Provider<String> aProvider = Providers.of("A");
+    final Provider<String> bProvider = Providers.of("B");
+    Module ab = new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<String> multibinder = Multibinder.newSetBinder(binder(), String.class);
+        multibinder.addBinding().toProvider(aProvider);
+        multibinder.addBinding().toProvider(bProvider);
+      }
+    };
+
+    // Guice guarantees this assertion, as the same module cannot be installed twice.
+    assertEquals(ImmutableSet.of("A", "B"),
+        Guice.createInjector(ab, ab).getInstance(Key.get(setOfString)));
+
+    // Guice will only guarantee this assertion if Multibinder ensures the bindings match.
+    Injector injector = Guice.createInjector(ab, Modules.override(ab).with(ab));
+    assertEquals(ImmutableSet.of("A", "B"),
+        injector.getInstance(Key.get(setOfString)));
+  }
+
+  private static class AStringProvider implements Provider<String> {
+    public String get() {
+      return "A";
+    }
+  }
+
+  private static class BStringProvider implements Provider<String> {
+    public String get() {
+      return "B";
+    }
+  }
+
+  public void testModuleOverrideRepeatedInstallsAndMultibindings_toProviderKey() {
+    Module ab = new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<String> multibinder = Multibinder.newSetBinder(binder(), String.class);
+        multibinder.addBinding().toProvider(Key.get(AStringProvider.class));
+        multibinder.addBinding().toProvider(Key.get(BStringProvider.class));
+      }
+    };
+
+    // Guice guarantees this assertion, as the same module cannot be installed twice.
+    assertEquals(ImmutableSet.of("A", "B"),
+        Guice.createInjector(ab, ab).getInstance(Key.get(setOfString)));
+
+    // Guice will only guarantee this assertion if Multibinder ensures the bindings match.
+    Injector injector = Guice.createInjector(ab, Modules.override(ab).with(ab));
+    assertEquals(ImmutableSet.of("A", "B"),
+        injector.getInstance(Key.get(setOfString)));
+  }
+
+  private static class StringGrabber {
+    private final String string;
+
+    @SuppressWarnings("unused")  // Found by reflection
+    public StringGrabber(@Named("A_string") String string) {
+      this.string = string;
+    }
+
+    @SuppressWarnings("unused")  // Found by reflection
+    public StringGrabber(@Named("B_string") String string, int unused) {
+      this.string = string;
+    }
+
+    @Override
+    public int hashCode() {
+      return string.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      return (obj instanceof StringGrabber) && ((StringGrabber) obj).string.equals(string);
+    }
+
+    @Override
+    public String toString() {
+      return "StringGrabber(" + string + ")";
+    }
+
+    static Set<String> values(Iterable<StringGrabber> grabbers) {
+      Set<String> result = new HashSet<String>();
+      for (StringGrabber grabber : grabbers) {
+        result.add(grabber.string);
+      }
+      return result;
+    }
+  }
+
+  public void testModuleOverrideRepeatedInstallsAndMultibindings_toConstructor() {
+    TypeLiteral<Set<StringGrabber>> setOfStringGrabber = new TypeLiteral<Set<StringGrabber>>() {};
+    Module ab = new AbstractModule() {
+      @Override protected void configure() {
+        Key<String> aKey = Key.get(String.class, Names.named("A_string"));
+        Key<String> bKey = Key.get(String.class, Names.named("B_string"));
+        bind(aKey).toInstance("A");
+        bind(bKey).toInstance("B");
+        bind(Integer.class).toInstance(0);  // used to disambiguate constructors
+
+        Multibinder<StringGrabber> multibinder =
+            Multibinder.newSetBinder(binder(), StringGrabber.class);
+        try {
+          multibinder.addBinding().toConstructor(
+              StringGrabber.class.getConstructor(String.class));
+          multibinder.addBinding().toConstructor(
+              StringGrabber.class.getConstructor(String.class, int.class));
+        } catch (NoSuchMethodException e) {
+          fail("No such method: " + e.getMessage());
+        }
+      }
+    };
+
+    // Guice guarantees this assertion, as the same module cannot be installed twice.
+    assertEquals(ImmutableSet.of("A", "B"),
+        StringGrabber.values(
+            Guice.createInjector(ab, ab).getInstance(Key.get(setOfStringGrabber))));
+
+    // Guice will only guarantee this assertion if Multibinder ensures the bindings match.
+    Injector injector = Guice.createInjector(ab, Modules.override(ab).with(ab));
+    assertEquals(ImmutableSet.of("A", "B"),
+        StringGrabber.values(injector.getInstance(Key.get(setOfStringGrabber))));
+  }
+
   /**
    * Unscoped bindings should not conflict, whether they were bound with no explicit scope, or
-   * explicitly bound in {@link Scopes.NO_SCOPE}.
+   * explicitly bound in {@link Scopes#NO_SCOPE}.
    */
   public void testDuplicateUnscopedBindings() {
     Module singleBinding = new AbstractModule() {
@@ -696,7 +852,7 @@
         bind(Integer.class).to(Key.get(Integer.class, named("A")));
         bind(Integer.class).to(Key.get(Integer.class, named("A"))).in(Scopes.NO_SCOPE);
       }
-      
+
       @Provides @Named("A")
       int provideInteger() {
         return 5;
@@ -709,13 +865,148 @@
         multibinder.addBinding().to(Key.get(Integer.class, named("A"))).in(Scopes.NO_SCOPE);
       }
     };
-    
+
     assertEquals(5,
         (int) Guice.createInjector(singleBinding).getInstance(Integer.class));
     assertEquals(ImmutableSet.of(5),
         Guice.createInjector(singleBinding, multibinding).getInstance(Key.get(setOfInteger)));
   }
 
+  /**
+   * Ensure key hash codes are fixed at injection time, not binding time.
+   */
+  public void testKeyHashCodesFixedAtInjectionTime() {
+    Module ab = new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<List<String>> multibinder = Multibinder.newSetBinder(binder(), listOfStrings);
+        List<String> list = Lists.newArrayList();
+        multibinder.addBinding().toInstance(list);
+        list.add("A");
+        list.add("B");
+      }
+    };
+
+    Injector injector = Guice.createInjector(ab);
+    for (Entry<Key<?>, Binding<?>> entry : injector.getAllBindings().entrySet()) {
+      Key<?> bindingKey = entry.getKey();
+      Key<?> clonedKey;
+      if (bindingKey.getAnnotation() != null) {
+        clonedKey = Key.get(bindingKey.getTypeLiteral(), bindingKey.getAnnotation());
+      } else if (bindingKey.getAnnotationType() != null) {
+        clonedKey = Key.get(bindingKey.getTypeLiteral(), bindingKey.getAnnotationType());
+      } else {
+        clonedKey = Key.get(bindingKey.getTypeLiteral());
+      }
+      assertEquals(bindingKey, clonedKey);
+      assertEquals("Incorrect hashcode for " + bindingKey + " -> " + entry.getValue(),
+          bindingKey.hashCode(), clonedKey.hashCode());
+    }
+  }
+
+  /**
+   * Ensure bindings do not rehash their keys once returned from {@link Elements#getElements}.
+   */
+  public void testBindingKeysFixedOnReturnFromGetElements() {
+    final List<String> list = Lists.newArrayList();
+    Module ab = new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<List<String>> multibinder = Multibinder.newSetBinder(binder(), listOfStrings);
+        multibinder.addBinding().toInstance(list);
+        list.add("A");
+        list.add("B");
+      }
+    };
+
+    InstanceBinding<?> binding = Iterables.getOnlyElement(
+        Iterables.filter(Elements.getElements(ab), InstanceBinding.class));
+    Key<?> keyBefore = binding.getKey();
+    assertEquals(listOfStrings, keyBefore.getTypeLiteral());
+    assertFalse(RehashableKeys.Keys.needsRehashing(keyBefore));
+
+    list.add("C");
+    Key<?> keyAfter = binding.getKey();
+    assertSame(keyBefore, keyAfter);
+    assertTrue(RehashableKeys.Keys.needsRehashing(keyAfter));
+  }
+
+  /*
+   * Verify through gratuitous mutation that key hashCode snapshots and whatnot happens at the right
+   * times, by binding two lists that are different at injector creation, but compare equal when the
+   * module is configured *and* when the set is instantiated.
+   */
+  public void testConcurrentMutation_bindingsDiffentAtInjectorCreation() {
+    // We initially bind two equal lists
+    final List<String> list1 = Lists.newArrayList();
+    final List<String> list2 = Lists.newArrayList();
+    Module module = new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<List<String>> multibinder = Multibinder.newSetBinder(binder(), listOfStrings);
+        multibinder.addBinding().toInstance(list1);
+        multibinder.addBinding().toInstance(list2);
+      }
+    };
+    List<Element> elements = Elements.getElements(module);
+
+    // Now we change the lists so they no longer match, and create the injector.
+    list1.add("A");
+    list2.add("B");
+    Injector injector = Guice.createInjector(Elements.getModule(elements));
+
+    // Now we change the lists so they compare equal again, and create the set.
+    list1.add(1, "B");
+    list2.add(0, "A");
+    try {
+      injector.getInstance(Key.get(setOfListOfStrings));
+      fail();
+    } catch (ProvisionException e) {
+      assertEquals(1, e.getErrorMessages().size());
+      assertContains(
+          Iterables.getOnlyElement(e.getErrorMessages()).getMessage().toString(),
+          "Set injection failed due to duplicated element \"[A, B]\"");
+    }
+
+    // Finally, we change the lists again so they are once more different, and ensure the set
+    // contains both.
+    list1.remove("A");
+    list2.remove("B");
+    Set<List<String>> set = injector.getInstance(Key.get(setOfListOfStrings));
+    assertEquals(ImmutableSet.of(ImmutableList.of("A"), ImmutableList.of("B")), set);
+  }
+
+  /*
+   * Verify through gratuitous mutation that key hashCode snapshots and whatnot happen at the right
+   * times, by binding two lists that compare equal at injector creation, but are different when the
+   * module is configured *and* when the set is instantiated.
+   */
+  public void testConcurrentMutation_bindingsSameAtInjectorCreation() {
+    // We initially bind two distinct lists
+    final List<String> list1 = Lists.newArrayList("A");
+    final List<String> list2 = Lists.newArrayList("B");
+    Module module = new AbstractModule() {
+      @Override protected void configure() {
+        Multibinder<List<String>> multibinder = Multibinder.newSetBinder(binder(), listOfStrings);
+        multibinder.addBinding().toInstance(list1);
+        multibinder.addBinding().toInstance(list2);
+      }
+    };
+    List<Element> elements = Elements.getElements(module);
+
+    // Now we change the lists so they compare equal, and create the injector.
+    list1.add(1, "B");
+    list2.add(0, "A");
+    Injector injector = Guice.createInjector(Elements.getModule(elements));
+
+    // Now we change the lists again so they are once more different, and create the set.
+    list1.remove("A");
+    list2.remove("B");
+    Set<List<String>> set = injector.getInstance(Key.get(setOfListOfStrings));
+
+    // The set will contain just one of the two lists.
+    // (In fact, it will be the first one we bound, but we don't promise that, so we won't test it.)
+    assertTrue(ImmutableSet.of(ImmutableList.of("A")).equals(set)
+        || ImmutableSet.of(ImmutableList.of("B")).equals(set));
+  }
+
   @BindingAnnotation
   @Retention(RetentionPolicy.RUNTIME)
   @Target({ElementType.FIELD, ElementType.PARAMETER, ElementType.METHOD})
@@ -770,7 +1061,7 @@
 
     assertEquals(ImmutableSet.<String>of("A"), injector.getInstance(Key.get(setOfString)));
   }
-  
+
   // See issue 670
   public void testSetAndMapValueAreDistinctInSpi() {
     Injector injector = Guice.createInjector(new AbstractModule() {
@@ -786,11 +1077,11 @@
     Binding<Map<String, String>> mapbinding = injector.getBinding(Key.get(mapOfStringString));
     mapbinding.acceptTargetVisitor(collector);
     assertNotNull(collector.mapbinding);
-    
+
     Binding<Set<String>> setbinding = injector.getBinding(Key.get(setOfString));
     setbinding.acceptTargetVisitor(collector);
     assertNotNull(collector.setbinding);
-    
+
     // Capture the value bindings and assert we have them right --
     // they'll always be in the right order because we preserve
     // binding order.
@@ -800,27 +1091,27 @@
     Binding<String> b = bindings.get(1);
     assertEquals("A", ((InstanceBinding<String>)a).getInstance());
     assertEquals("b", ((InstanceBinding<String>)b).getInstance());
-    
+
     // Now make sure "A" belongs only to the set binding,
     // and "b" only belongs to the map binding.
     assertFalse(collector.mapbinding.containsElement(a));
     assertTrue(collector.mapbinding.containsElement(b));
-    
+
     assertTrue(collector.setbinding.containsElement(a));
     assertFalse(collector.setbinding.containsElement(b));
   }
-  
+
   private static class Collector extends DefaultBindingTargetVisitor<Object, Object> implements
       MultibindingsTargetVisitor<Object, Object> {
     MapBinderBinding<? extends Object> mapbinding;
     MultibinderBinding<? extends Object> setbinding;
-    
+
     @Override
     public Object visit(MapBinderBinding<? extends Object> mapbinding) {
       this.mapbinding = mapbinding;
       return null;
     }
-    
+
     @Override
     public Object visit(MultibinderBinding<? extends Object> multibinding) {
      this.setbinding = multibinding;