diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceInfo.java b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceInfo.java
index 938fc3f..64df46e 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceInfo.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceInfo.java
@@ -31,10 +31,10 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.List;
 import java.util.Locale;
 import java.util.Map;
+import java.util.TreeMap;
 
 /**
  * A class representing a discovered mDNS service instance.
@@ -205,17 +205,14 @@
         // compatibility. We should prefer only {@code textEntries} if it's not null.
         List<TextEntry> entries =
                 (this.textEntries != null) ? this.textEntries : parseTextStrings(this.textStrings);
-        Map<String, byte[]> attributes = new HashMap<>(entries.size());
+        // The map of attributes is case-insensitive.
+        final Map<String, byte[]> attributes = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
         for (TextEntry entry : entries) {
-            String key = entry.getKey().toLowerCase(Locale.ENGLISH);
-
             // Per https://datatracker.ietf.org/doc/html/rfc6763#section-6.4, only the first entry
             // of the same key should be accepted:
             // If a client receives a TXT record containing the same key more than once, then the
             // client MUST silently ignore all but the first occurrence of that attribute.
-            if (!attributes.containsKey(key)) {
-                attributes.put(key, entry.getValue());
-            }
+            attributes.putIfAbsent(entry.getKey(), entry.getValue());
         }
         this.attributes = Collections.unmodifiableMap(attributes);
         this.interfaceIndex = interfaceIndex;
@@ -311,12 +308,12 @@
      */
     @Nullable
     public byte[] getAttributeAsBytes(@NonNull String key) {
-        return attributes.get(key.toLowerCase(Locale.ENGLISH));
+        return attributes.get(key);
     }
 
     /** Returns an immutable map of all attributes. */
     public Map<String, String> getAttributes() {
-        Map<String, String> map = new HashMap<>(attributes.size());
+        Map<String, String> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
         for (Map.Entry<String, byte[]> kv : attributes.entrySet()) {
             final byte[] value = kv.getValue();
             map.put(kv.getKey(), value == null ? null : new String(value, UTF_8));
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceInfoTest.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceInfoTest.java
index 76728cf..4db0f1a 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceInfoTest.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceInfoTest.java
@@ -119,6 +119,26 @@
     }
 
     @Test
+    public void constructor_createWithUppercaseKeys_correctAttributes() {
+        MdnsServiceInfo info =
+                new MdnsServiceInfo(
+                        "my-mdns-service",
+                        new String[] {"_testtype", "_tcp"},
+                        List.of(),
+                        new String[] {"my-host", "local"},
+                        12345,
+                        "192.168.1.1",
+                        "2001::1",
+                        List.of("KEY=Value"),
+                        /* textEntries= */ null);
+
+        assertEquals("Value", info.getAttributeByKey("key"));
+        assertEquals("Value", info.getAttributeByKey("KEY"));
+        assertEquals(1, info.getAttributes().size());
+        assertEquals("KEY", info.getAttributes().keySet().iterator().next());
+    }
+
+    @Test
     public void getInterfaceIndex_constructorWithDefaultValues_returnsMinusOne() {
         MdnsServiceInfo info =
                 new MdnsServiceInfo(