diff --git a/CHANGELOG.md b/CHANGELOG.md
index 6c1c554..1ed9863 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,8 @@
+## 0.9.4
+
+* Add a `CanonicalizedMap` class that canonicalizes its keys to provide a custom
+  equality relation.
+
 ## 0.9.3+1
 
 * Fix all analyzer hints.
diff --git a/lib/collection.dart b/lib/collection.dart
index d640071..d24dd39 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -21,4 +21,5 @@
 export "equality.dart";
 export "iterable_zip.dart";
 export "priority_queue.dart";
+export "src/canonicalized_map.dart";
 export "wrappers.dart";
diff --git a/lib/src/canonicalized_map.dart b/lib/src/canonicalized_map.dart
new file mode 100644
index 0000000..f1cd859
--- /dev/null
+++ b/lib/src/canonicalized_map.dart
@@ -0,0 +1,115 @@
+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library dart.pkg.collection.canonicalized_map;
+
+import 'dart:collection';
+
+import 'utils.dart';
+
+/**
+ * A map whose keys are converted to canonical values of type `C`.
+ *
+ * This is useful for using case-insensitive String keys, for example. It's more
+ * efficient than a [LinkedHashMap] with a custom equality operator because it
+ * only canonicalizes each key once, rather than doing so for each comparison.
+ *
+ * By default, `null` is allowed as a key. It can be forbidden via the
+ * `isValidKey` parameter.
+ */
+class CanonicalizedMap<C, K, V> implements Map<K, V> {
+  final Function _canonicalize;
+
+  final Function _isValidKeyFn;
+
+  final _base = new Map<C, Pair<K, V>>();
+
+  /**
+   * Creates an empty canonicalized map.
+   *
+   * The [canonicalize] function should return the canonical value for the given
+   * key. Keys with the same canonical value are considered equivalent.
+   *
+   * The [isValidKey] function is called before calling [canonicalize] for
+   * methods that take arbitrary objects. It can be used to filter out keys that
+   * can't be canonicalized.
+   */
+  CanonicalizedMap(C canonicalize(K key), {bool isValidKey(K key)})
+      : _canonicalize = canonicalize,
+        _isValidKeyFn = isValidKey;
+
+  /**
+   * Creates a canonicalized map that is initialized with the key/value pairs of
+   * [other].
+   *
+   * The [canonicalize] function should return the canonical value for the given
+   * key. Keys with the same canonical value are considered equivalent.
+   *
+   * The [isValidKey] function is called before calling [canonicalize] for
+   * methods that take arbitrary objects. It can be used to filter out keys that
+   * can't be canonicalized.
+   */
+  CanonicalizedMap.from(Map<K, V> other, C canonicalize(K key),
+          {bool isValidKey(K key)})
+      : _canonicalize = canonicalize,
+        _isValidKeyFn = isValidKey {
+    addAll(other);
+  }
+
+  V operator [](Object key) {
+    if (!_isValidKey(key)) return null;
+    var pair = _base[_canonicalize(key)];
+    return pair == null ? null : pair.last;
+  }
+
+  void operator []=(K key, V value) {
+    _base[_canonicalize(key)] = new Pair(key, value);
+  }
+
+  void addAll(Map<K, V> other) {
+    other.forEach((key, value) => this[key] = value);
+  }
+
+  void clear() {
+    _base.clear();
+  }
+
+  bool containsKey(Object key) {
+    if (!_isValidKey(key)) return false;
+    return _base.containsKey(_canonicalize(key));
+  }
+
+  bool containsValue(Object value) =>
+      _base.values.any((pair) => pair.last == value);
+
+  void forEach(void f(K key, V value)) {
+    _base.forEach((key, pair) => f(pair.first, pair.last));
+  }
+
+  bool get isEmpty => _base.isEmpty;
+
+  bool get isNotEmpty => _base.isNotEmpty;
+
+  Iterable<K> get keys => _base.values.map((pair) => pair.first);
+
+  int get length => _base.length;
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    return _base.putIfAbsent(_canonicalize(key),
+        () => new Pair(key, ifAbsent())).last;
+  }
+
+  V remove(Object key) {
+    if (!_isValidKey(key)) return null;
+    var pair = _base.remove(_canonicalize(key));
+    return pair == null ? null : pair.last;
+  }
+
+  Iterable<V> get values => _base.values.map((pair) => pair.last);
+
+  String toString() => Maps.mapToString(this);
+
+  bool _isValidKey(Object key) => (key == null || key is K) &&
+      (_isValidKeyFn == null || _isValidKeyFn(key));
+}
diff --git a/lib/src/utils.dart b/lib/src/utils.dart
new file mode 100644
index 0000000..c9c7537
--- /dev/null
+++ b/lib/src/utils.dart
@@ -0,0 +1,13 @@
+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+library dart.pkg.collection.utils;
+
+/// A pair of values.
+class Pair<E, F> {
+  E first;
+  F last;
+
+  Pair(this.first, this.last);
+}
diff --git a/lib/wrappers.dart b/lib/wrappers.dart
index 2034174..509a966 100644
--- a/lib/wrappers.dart
+++ b/lib/wrappers.dart
@@ -16,6 +16,7 @@
 
 export "dart:collection" show UnmodifiableListView;
 
+export "src/canonicalized_map.dart";
 part "src/unmodifiable_wrappers.dart";
 
 /**
diff --git a/pubspec.yaml b/pubspec.yaml
index 80b0972..3d48447 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
 name: collection
-version: 0.9.3+1
+version: 0.9.4
 author: Dart Team <misc@dartlang.org>
 description: Collections and utilities functions and classes related to collections.
 homepage: http://www.dartlang.org
diff --git a/test/canonicalized_map_test.dart b/test/canonicalized_map_test.dart
new file mode 100644
index 0000000..1793777
--- /dev/null
+++ b/test/canonicalized_map_test.dart
@@ -0,0 +1,166 @@
+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "package:collection/collection.dart";
+import "package:unittest/unittest.dart";
+
+void main() {
+  group("with an empty canonicalized map", () {
+    var map;
+    setUp(() {
+      map = new CanonicalizedMap<int, String, String>(int.parse,
+          isValidKey: new RegExp(r"^\d+$").hasMatch);
+    });
+
+    test("canonicalizes keys on set and get", () {
+      map["1"] = "value";
+      expect(map["01"], equals("value"));
+    });
+
+    test("get returns null for uncanonicalizable key", () {
+      expect(map["foo"], isNull);
+    });
+
+    test("canonicalizes keys for addAll", () {
+      map.addAll({
+        "1": "value 1",
+        "2": "value 2",
+        "3": "value 3"
+      });
+      expect(map["01"], equals("value 1"));
+      expect(map["02"], equals("value 2"));
+      expect(map["03"], equals("value 3"));
+    });
+
+    test("uses the final value for addAll collisions", () {
+      map.addAll({
+        "1": "value 1",
+        "01": "value 2",
+        "001": "value 3"
+      });
+      expect(map.length, equals(1));
+      expect(map["0001"], equals("value 3"));
+    });
+
+    test("clear clears the map", () {
+      map.addAll({
+        "1": "value 1",
+        "2": "value 2",
+        "3": "value 3"
+      });
+      expect(map, isNot(isEmpty));
+      map.clear();
+      expect(map, isEmpty);
+    });
+
+    test("canonicalizes keys for containsKey", () {
+      map["1"] = "value";
+      expect(map.containsKey("01"), isTrue);
+      expect(map.containsKey("2"), isFalse);
+    });
+
+    test("containsKey returns false for uncanonicalizable key", () {
+      expect(map.containsKey("foo"), isFalse);
+    });
+
+    test("canonicalizes keys for putIfAbsent", () {
+      map["1"] = "value";
+      expect(map.putIfAbsent("01", () => throw "shouldn't run"),
+             equals("value"));
+      expect(map.putIfAbsent("2", () => "new value"), equals("new value"));
+    });
+
+    test("canonicalizes keys for remove", () {
+      map["1"] = "value";
+      expect(map.remove("2"), isNull);
+      expect(map.remove("01"), equals("value"));
+      expect(map, isEmpty);
+    });
+
+    test("remove returns null for uncanonicalizable key", () {
+      expect(map.remove("foo"), isNull);
+    });
+
+    test("containsValue returns whether a value is in the map", () {
+      map["1"] = "value";
+      expect(map.containsValue("value"), isTrue);
+      expect(map.containsValue("not value"), isFalse);
+    });
+
+    test("isEmpty returns whether the map is empty", () {
+      expect(map.isEmpty, isTrue);
+      map["1"] = "value";
+      expect(map.isEmpty, isFalse);
+      map.remove("01");
+      expect(map.isEmpty, isTrue);
+    });
+
+    test("isNotEmpty returns whether the map isn't empty", () {
+      expect(map.isNotEmpty, isFalse);
+      map["1"] = "value";
+      expect(map.isNotEmpty, isTrue);
+      map.remove("01");
+      expect(map.isNotEmpty, isFalse);
+    });
+
+    test("length returns the number of pairs in the map", () {
+      expect(map.length, equals(0));
+      map["1"] = "value 1";
+      expect(map.length, equals(1));
+      map["01"] = "value 01";
+      expect(map.length, equals(1));
+      map["02"] = "value 02";
+      expect(map.length, equals(2));
+    });
+
+    test("uses original keys for keys", () {
+      map["001"] = "value 1";
+      map["02"] = "value 2";
+      expect(map.keys, equals(["001", "02"]));
+    });
+
+    test("uses original keys for forEach", () {
+      map["001"] = "value 1";
+      map["02"] = "value 2";
+
+      var keys = [];
+      map.forEach((key, value) => keys.add(key));
+      expect(keys, equals(["001", "02"]));
+    });
+
+    test("values returns all values in the map", () {
+      map.addAll({
+        "1": "value 1",
+        "01": "value 01",
+        "2": "value 2",
+        "03": "value 03"
+      });
+
+      expect(map.values, equals(["value 01", "value 2", "value 03"]));
+    });
+  });
+
+  group("CanonicalizedMap.from", () {
+    test("canonicalizes its keys", () {
+      var map = new CanonicalizedMap.from({
+        "1": "value 1",
+        "2": "value 2",
+        "3": "value 3"
+      }, int.parse);
+      expect(map["01"], equals("value 1"));
+      expect(map["02"], equals("value 2"));
+      expect(map["03"], equals("value 3"));
+    });
+
+    test("uses the final value for collisions", () {
+      var map = new CanonicalizedMap.from({
+        "1": "value 1",
+        "01": "value 2",
+        "001": "value 3"
+      }, int.parse);
+      expect(map.length, equals(1));
+      expect(map["0001"], equals("value 3"));
+    });
+  });
+}