diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
index b1846ca..9ac4789 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -28,8 +28,8 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.SpellChecker;
 import java.io.Serializable;
-import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;
@@ -99,7 +99,7 @@
 
     private final Mutability mutability;
     final Frame parent;
-    final Map<String, Object> bindings = new HashMap<>();
+    final Map<String, Object> bindings = new LinkedHashMap<>();
     // The label for the target this frame is defined in (e.g., //foo:bar.bzl).
     @Nullable
     private Label label;
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
index cccb746..0575203 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
@@ -497,6 +497,32 @@
   }
 
   @Test
+  public void testExportAliasedName() throws Exception {
+    // When there are multiple names aliasing the same SkylarkExportable, the first one to be
+    // declared should be used. Make sure we're not using lexicographical order, hash order,
+    // non-deterministic order, or anything else.
+    evalAndExport(
+        "def _impl(ctx): pass",
+        "d = rule(implementation = _impl)",
+        "a = d",
+        // Having more names improves the chance that non-determinism will be caught.
+        "b = d",
+        "c = d",
+        "e = d",
+        "f = d",
+        "foo = d",
+        "bar = d",
+        "baz = d",
+        "x = d",
+        "y = d",
+        "z = d");
+    String dName = ((RuleFunction) lookup("d")).getRuleClass().getName();
+    String fooName = ((RuleFunction) lookup("foo")).getRuleClass().getName();
+    assertThat(dName).isEqualTo("d");
+    assertThat(fooName).isEqualTo("d");
+  }
+
+  @Test
   public void testOutputToGenfiles() throws Exception {
     evalAndExport("def impl(ctx): pass", "r1 = rule(impl, output_to_genfiles=True)");
     RuleClass c = ((RuleFunction) lookup("r1")).getRuleClass();