diff --git a/pkg/pkg.status b/pkg/pkg.status
index 9933564..cdaed72 100644
--- a/pkg/pkg.status
+++ b/pkg/pkg.status
@@ -52,6 +52,9 @@
 intl/test/find_default_locale_browser_test: Skip
 intl/test/date_time_format_http_request_test: Skip
 
+# Fails to recognize HashMap as an instance of Map.
+analyzer-experimental/test/generated/ast_test: Fail
+
 [ $runtime == vm && $system == windows ]
 intl/test/find_default_locale_standalone_test: Fail # Issue 8110
 
diff --git a/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart b/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart
index e60f8c9..9f8155d 100644
--- a/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart
+++ b/sdk/lib/_internal/compiler/implementation/js_backend/backend.dart
@@ -306,7 +306,7 @@
     // TODO(sgjesse): Handle field types for classes with more than one
     // constructor.
     if (ctors.length == 2) {
-      optimizedFunctions.forEach((Element field, _) {
+      optimizedFunctions.keys.toList().forEach((Element field) {
         if (identical(field.enclosingElement, cls)) {
           scheduleRecompilation(field);
         }
@@ -347,12 +347,12 @@
     // TODO(sgjesse): Take the type of the setter into account.
     if (setterSelectorsUsed.contains(setter.name)) return;
     setterSelectorsUsed.add(setter.name);
-    optimizedStaticFunctions.forEach((Element field, _) {
+    optimizedStaticFunctions.keys.toList().forEach((Element field) {
       if (field.name == setter.name) {
         scheduleRecompilation(field);
       }
     });
-    optimizedFunctions.forEach((Element field, _) {
+    optimizedFunctions.keys.toList().forEach((Element field) {
       if (field.name == setter.name) {
         scheduleRecompilation(field);
       }
@@ -622,14 +622,14 @@
   CodeEmitterTask emitter;
 
   /**
-   * The generated code as a js AST for compiled methods. 
+   * The generated code as a js AST for compiled methods.
    */
   Map<Element, js.Expression> get generatedCode {
     return compiler.enqueuer.codegen.generatedCode;
   }
 
   /**
-   * The generated code as a js AST for compiled bailout methods. 
+   * The generated code as a js AST for compiled bailout methods.
    */
   final Map<Element, js.Expression> generatedBailoutCode =
       new Map<Element, js.Expression>();
@@ -908,7 +908,7 @@
       // The backend will use a literal list to initialize the entries
       // of the map.
       if (enqueuer.isResolutionQueue) {
-        enqueuer.registerInstantiatedClass(compiler.listClass); 
+        enqueuer.registerInstantiatedClass(compiler.listClass);
         enqueuer.registerInstantiatedClass(compiler.mapLiteralClass);
       }
     }
diff --git a/sdk/lib/_internal/compiler/implementation/native_handler.dart b/sdk/lib/_internal/compiler/implementation/native_handler.dart
index 894a605..adce296 100644
--- a/sdk/lib/_internal/compiler/implementation/native_handler.dart
+++ b/sdk/lib/_internal/compiler/implementation/native_handler.dart
@@ -362,7 +362,7 @@
                                cause,
                                [String reason]) {
     Iterable matches = unusedClasses.where(predicate);
-    matches.forEach((c) => enqueueClass(c, cause));
+    matches.toList().forEach((c) => enqueueClass(c, cause));
   }
 
   onFirstNativeClass() {
diff --git a/sdk/lib/_internal/compiler/implementation/source_map_builder.dart b/sdk/lib/_internal/compiler/implementation/source_map_builder.dart
index a2cd6fc..80960d3 100644
--- a/sdk/lib/_internal/compiler/implementation/source_map_builder.dart
+++ b/sdk/lib/_internal/compiler/implementation/source_map_builder.dart
@@ -134,7 +134,6 @@
   int indexOf(List<String> list, String value, Map<String, int> map) {
     return map.putIfAbsent(value, () {
       int index = list.length;
-      map[value] = index;
       list.add(value);
       return index;
     });
diff --git a/sdk/lib/collection/collection.dart b/sdk/lib/collection/collection.dart
index b1a8353..88c1ada 100644
--- a/sdk/lib/collection/collection.dart
+++ b/sdk/lib/collection/collection.dart
@@ -9,8 +9,12 @@
 part 'arrays.dart';
 part 'collections.dart';
 part 'iterator.dart';
-part 'map.dart';
 part 'maps.dart';
 part 'queue.dart';
-part 'set.dart';
 part 'splay_tree.dart';
+part 'hash_table.dart';
+part 'hash_set.dart';
+part 'hash_map.dart';
+part 'linked_hash_table.dart';
+part 'linked_hash_set.dart';
+part 'linked_hash_map.dart';
diff --git a/sdk/lib/collection/collection_sources.gypi b/sdk/lib/collection/collection_sources.gypi
index b262c10..37d67be 100644
--- a/sdk/lib/collection/collection_sources.gypi
+++ b/sdk/lib/collection/collection_sources.gypi
@@ -7,11 +7,15 @@
   'sources': [
     'arrays.dart',
     'collections.dart',
+    'hash_map.dart',
+    'hash_set.dart',
+    'hash_table.dart',
     'iterator.dart',
-    'map.dart',
+    'linked_hash_map.dart',
+    'linked_hash_set.dart',
+    'linked_hash_table.dart',
     'maps.dart',
     'queue.dart',
-    'set.dart',
     'splay_tree.dart',
   ],
 }
diff --git a/sdk/lib/collection/hash_map.dart b/sdk/lib/collection/hash_map.dart
new file mode 100644
index 0000000..d90b4b9
--- /dev/null
+++ b/sdk/lib/collection/hash_map.dart
@@ -0,0 +1,136 @@
+// Copyright (c) 2013, 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.
+
+part of dart.collection;
+
+class _HashMapTable<K, V> extends _HashTable<K> {
+  static const int _INITIAL_CAPACITY = 8;
+  static const int _VALUE_INDEX = 1;
+
+  _HashMapTable() : super(_INITIAL_CAPACITY);
+
+  int get _entrySize => 2;
+
+  V _value(int offset) => _table[offset + _VALUE_INDEX];
+  void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; }
+
+  _copyEntry(List fromTable, int fromOffset, int toOffset) {
+    _table[toOffset + _VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX];
+  }
+}
+
+class HashMap<K, V> implements Map<K, V> {
+  final _HashMapTable<K, V> _hashTable;
+
+  HashMap() : _hashTable = new _HashMapTable<K, V>() {
+    _hashTable._container = this;
+  }
+
+  factory HashMap.from(Map<K, V> other) {
+    return new HashMap<K, V>()..addAll(other);
+  }
+
+  bool containsKey(K key) {
+    return _hashTable._get(key) >= 0;
+  }
+
+  bool containsValue(V value) {
+    List table = _hashTable._table;
+    int entrySize = _hashTable._entrySize;
+    for (int offset = 0; offset < table.length; offset += entrySize) {
+      if (!_hashTable._isFree(table[offset]) &&
+          _hashTable._value(offset) == value) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  void addAll(Map<K, V> other) {
+    other.forEach((K key, V value) {
+      int offset = _hashTable._put(key);
+      _hashTable._setValue(offset, value);
+      _hashTable._checkCapacity();
+    });
+  }
+
+  V operator [](K key) {
+    int offset = _hashTable._get(key);
+    if (offset >= 0) return _hashTable._value(offset);
+    return null;
+  }
+
+  void operator []=(K key, V value) {
+    int offset = _hashTable._put(key);
+    _hashTable._setValue(offset, value);
+    _hashTable._checkCapacity();
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key);
+    Object entry = _hashTable._table[offset];
+    if (!_hashTable._isFree(entry)) {
+      return _hashTable._value(offset);
+    }
+    int modificationCount = _hashTable._modificationCount;
+    V value = ifAbsent();
+    if (modificationCount == _hashTable._modificationCount) {
+      _hashTable._setKey(offset, key);
+      _hashTable._setValue(offset, value);
+      if (entry == null) {
+        _hashTable._entryCount++;
+        _hashTable._checkCapacity();
+      } else {
+        assert(identical(entry, _TOMBSTONE));
+        _hashTable._deletedCount--;
+      }
+      _hashTable._recordModification();
+    } else {
+      // The table might have changed, so we can't trust [offset] any more.
+      // Do another lookup before setting the value.
+      offset = _hashTable._put(key);
+      _hashTable._setValue(offset, value);
+      _hashTable._checkCapacity();
+    }
+    return value;
+  }
+
+  V remove(K key) {
+    int offset = _hashTable._remove(key);
+    if (offset < 0) return null;
+    V oldValue = _hashTable._value(offset);
+    _hashTable._setValue(offset, null);
+    _hashTable._checkCapacity();
+    return oldValue;
+  }
+
+  void clear() {
+    _hashTable._clear();
+  }
+
+  void forEach(void action (K key, V value)) {
+    int modificationCount = _hashTable._modificationCount;
+    List table = _hashTable._table;
+    int entrySize = _hashTable._entrySize;
+    for (int offset = 0; offset < table.length; offset += entrySize) {
+      Object entry = table[offset];
+      if (!_hashTable._isFree(entry)) {
+        K key = entry;
+        V value = _hashTable._value(offset);
+        action(key, value);
+        _hashTable._checkModification(modificationCount);
+      }
+    }
+  }
+
+  Iterable<K> get keys => new _HashTableKeyIterable<K>(_hashTable);
+  Iterable<V> get values =>
+      new _HashTableValueIterable<V>(_hashTable, _HashMapTable._VALUE_INDEX);
+
+  int get length => _hashTable._elementCount;
+
+  bool get isEmpty => _hashTable._elementCount == 0;
+
+  String toString() => Maps.mapToString(this);
+}
diff --git a/sdk/lib/collection/hash_set.dart b/sdk/lib/collection/hash_set.dart
new file mode 100644
index 0000000..22fb38f
--- /dev/null
+++ b/sdk/lib/collection/hash_set.dart
@@ -0,0 +1,115 @@
+// Copyright (c) 2013, 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.
+
+part of dart.collection;
+
+class HashSet<E> extends Collection<E> implements Set<E> {
+  static const int _INITIAL_CAPACITY = 8;
+  final _HashTable<E> _table;
+
+  HashSet() : _table = new _HashTable(_INITIAL_CAPACITY) {
+    _table._container = this;
+  }
+
+  factory HashSet.from(Iterable<E> iterable) {
+    return new HashSet<E>()..addAll(iterable);
+  }
+
+  // Iterable.
+  Iterator<E> get iterator => new _HashTableKeyIterator<E>(_table);
+
+  bool get isEmpty => _table._elementCount == 0;
+
+  bool contains(Object object) => _table._get(object) >= 0;
+
+  // Collection.
+  void add(E element) {
+    _table._put(element);
+    _table._checkCapacity();
+  }
+
+  void addAll(Iterable<E> objects) {
+    for (E object in objects) {
+      _table._put(object);
+      _table._checkCapacity();
+    }
+  }
+
+  bool remove(Object object) {
+    int offset = _table._remove(object);
+    _table._checkCapacity();
+    return offset >= 0;
+  }
+
+  void removeAll(Iterable objectsToRemove) {
+    for (Object object in objectsToRemove) {
+      _table._remove(object);
+      _table._checkCapacity();
+    }
+  }
+
+  void retainAll(Iterable objectsToRetain) {
+    IterableMixinWorkaround.retainAll(this, objectsToRetain);
+  }
+
+  void _filterMatching(bool test(E element), bool removeMatching) {
+    int entrySize = _table._entrySize;
+    int length = _table._table.length;
+    for (int offset =  0; offset < length; offset += entrySize) {
+      Object entry = _table._table[offset];
+      if (!_table._isFree(entry)) {
+        E key = identical(entry, _NULL) ? null : entry;
+        int modificationCount = _table._modificationCount;
+        bool shouldRemove = (removeMatching == test(key));
+        _table._checkModification(modificationCount);
+        if (shouldRemove) {
+          _table._deleteEntry(offset);
+        }
+      }
+    }
+    _table._checkCapacity();
+  }
+
+  void removeMatching(bool test(E element)) {
+    _filterMatching(test, true);
+  }
+
+  void retainMatching(bool test(E element)) {
+    _filterMatching(test, false);
+  }
+
+  void clear() {
+    _table._clear();
+  }
+
+  // Set.
+  bool isSubsetOf(Collection<E> collection) {
+    Set otherSet;
+    if (collection is Set) {
+      otherSet = collection;
+    } else {
+      otherSet = collection.toSet();
+    }
+    return otherSet.containsAll(this);
+  }
+
+  bool containsAll(Collection<E> collection) {
+    for (E element in collection) {
+      if (!this.contains(element)) return false;
+    }
+    return true;
+  }
+
+  Set<E> intersection(Collection<E> other) {
+    Set<E> result = new HashSet<E>();
+    for (E element in other) {
+      if (this.contains(element)) {
+        result.add(element);
+      }
+    }
+    return result;
+  }
+
+  String toString() =>  Collections.collectionToString(this);
+}
diff --git a/sdk/lib/collection/hash_table.dart b/sdk/lib/collection/hash_table.dart
new file mode 100644
index 0000000..7ab52cb
--- /dev/null
+++ b/sdk/lib/collection/hash_table.dart
@@ -0,0 +1,404 @@
+// Copyright (c) 2013, 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.
+
+part of dart.collection;
+
+class _DeadEntry {
+  const _DeadEntry();
+}
+
+class _NullKey {
+  const _NullKey();
+  int get hashCode => null.hashCode;
+}
+
+const _TOMBSTONE = const _DeadEntry();
+const _NULL = const _NullKey();
+
+class _HashTable<K> {
+  /**
+   * Table of entries with [_entrySize] slots per entry.
+   *
+   * Capacity in entries must be factor of two.
+   */
+  List _table;
+  /** Current capacity. Always equal to [:_table.length ~/ _entrySize:]. */
+  int _capacity;
+  /** Count of occupied entries, including deleted ones. */
+  int _entryCount = 0;
+  /** Count of deleted entries. */
+  int _deletedCount = 0;
+  /** Counter incremented when table is modified. */
+  int _modificationCount = 0;
+  /** If set, used as the source object for [ConcurrentModificationError]s. */
+  Object _container;
+
+  _HashTable(int initialCapacity) : _capacity = initialCapacity {
+    _table = _createTable(initialCapacity);
+  }
+
+  /** Reads key from table. Converts _NULL marker to null. */
+  Object _key(offset) {
+    assert(!_isFree(_table[offset]));
+    Object key = _table[offset];
+    if (!identical(key, _NULL)) return key;
+    return null;
+  }
+
+  /** Writes key to table. Converts null to _NULL marker. */
+  void _setKey(int offset, Object key) {
+    if (key == null) key = _NULL;
+    _table[offset] = key;
+  }
+
+  int get _elementCount => _entryCount - _deletedCount;
+
+  /** Size of each entry. */
+  int get _entrySize => 1;
+
+  void _checkModification(int expectedModificationCount) {
+    if (_modificationCount != expectedModificationCount) {
+      throw new ConcurrentModificationError(_container);
+    }
+  }
+
+  void _recordModification() {
+    // Value cycles after 2^30 modifications. If you keep hold of an
+    // iterator for that long, you might miss a modification detection,
+    // and iteration can go sour. Don't do that.
+    _modificationCount = (_modificationCount + 1) & (0x3FFFFFFF);
+  }
+
+  /**
+   * Create an empty table.
+   */
+  List _createTable(int capacity) {
+    List table = new List.fixedLength(capacity * _entrySize);
+    return table;
+  }
+
+  /** First table probe. */
+  int _firstProbe(int hashCode, int capacity) {
+    return hashCode & (capacity - 1);
+  }
+
+  /** Following table probes. */
+  int _nextProbe(int previousIndex, int probeCount, int capacity) {
+    // When capacity is a power of 2, this probing algorithm (the triangular
+    // number sequence modulo capacity) is guaranteed to hit all indices exactly
+    // once before repeating.
+    return (previousIndex + probeCount) & (capacity - 1);
+  }
+
+  /** Whether an object is a free-marker (either tombstone or free). */
+  bool _isFree(Object marker) =>
+      marker == null || identical(marker, _TOMBSTONE);
+
+  /**
+   * Look up the offset for an object in the table.
+   *
+   * Finds the offset of the object in the table, if it is there,
+   * or the first free offset for its hashCode.
+   */
+  int _probeForAdd(int hashCode, Object object) {
+    int entrySize = _entrySize;
+    int index = _firstProbe(hashCode, _capacity);
+    int firstTombstone = -1;
+    int probeCount = 0;
+    while (true) {
+      int offset = index * entrySize;
+      Object entry = _table[offset];
+      if (identical(entry, _TOMBSTONE)) {
+        if (firstTombstone < 0) firstTombstone = offset;
+      } else if (entry == null) {
+        if (firstTombstone < 0) return offset;
+        return firstTombstone;
+      } else if (identical(_NULL, entry) ? _equals(null, object)
+                                         : _equals(entry, object)) {
+        return offset;
+      }
+      // The _nextProbe is designed so that it hits
+      // every index eventually.
+      index = _nextProbe(index, ++probeCount, _capacity);
+    }
+  }
+
+  /**
+   * Look up the offset for an object in the table.
+   *
+   * If the object is in the table, its offset is returned.
+   *
+   * If the object is not in the table, Otherwise a negative value is returned.
+   */
+  int _probeForLookup(int hashCode, Object object) {
+    int entrySize = _entrySize;
+    int index = _firstProbe(hashCode, _capacity);
+    int probeCount = 0;
+    while (true) {
+      int offset = index * entrySize;
+      Object entry = _table[offset];
+      if (entry == null) {
+        return -1;
+      } else if (!identical(_TOMBSTONE, entry)) {
+        if (identical(_NULL, entry) ? _equals(null, object)
+                                    : _equals(entry, object)) {
+          return offset;
+        }
+      }
+      // The _nextProbe is designed so that it hits
+      // every index eventually.
+      index = _nextProbe(index, ++probeCount, _capacity);
+    }
+  }
+
+  // Override the following two to change equality/hashCode computations
+
+  /**
+   * Compare two object for equality.
+   *
+   * The first object is the one already in the table,
+   * and the second is the one being searched for.
+   */
+  bool _equals(Object element, Object other) {
+    return element == other;
+  }
+
+  /**
+   * Compute hash-code for an object.
+   */
+  int _hashCodeOf(Object object) => object.hashCode;
+
+  /**
+   * Ensure that the table isn't too full for its own good.
+   *
+   * Call this after adding an element.
+   */
+  int _checkCapacity() {
+    // Compute everything in multiples of entrySize to avoid division.
+    int freeCount = _capacity - _entryCount;
+    if (freeCount * 4 < _capacity ||
+        freeCount < _deletedCount) {
+      // Less than 25% free or more deleted entries than free entries.
+      _grow(_entryCount - _deletedCount);
+    }
+  }
+
+  void _grow(int contentCount) {
+    int capacity = _capacity;
+    // Don't grow to less than twice the needed capacity.
+    int minCapacity = contentCount * 2;
+    while (capacity < minCapacity) {
+      capacity *= 2;
+    }
+    // Reset to another table and add all existing elements.
+    List oldTable = _table;
+    _table = _createTable(capacity);
+    _capacity = capacity;
+    _entryCount = 0;
+    _deletedCount = 0;
+    _addAllEntries(oldTable);
+    _recordModification();
+  }
+
+  /**
+   * Copies all non-free entries from the old table to the new empty table.
+   */
+  void _addAllEntries(List oldTable) {
+    for (int i = 0; i < oldTable.length; i += _entrySize) {
+      Object object = oldTable[i];
+      if (!_isFree(object)) {
+        int toOffset = _put(object);
+        _copyEntry(oldTable, i, toOffset);
+      }
+    }
+  }
+
+  /**
+   * Copies everything but the key element from one entry to another.
+   *
+   * Called while growing the base array.
+   *
+   * Override this if any non-key fields need copying.
+   */
+  void _copyEntry(List fromTable, int fromOffset, int toOffset) {}
+
+  // The following three methods are for simple get/set/remove operations.
+  // They only affect the key of an entry. The remaining fields must be
+  // filled by the caller.
+
+  /**
+   * Returns the offset of a key in [_table], or negative if it's not there.
+   */
+  int _get(K key) {
+    return _probeForLookup(_hashCodeOf(key), key);
+  }
+
+  /**
+   * Puts the key into the table and returns its offset into [_table].
+   *
+   * If [_entrySize] is greater than 1, the caller should fill the
+   * remaining fields.
+   *
+   * Remember to call [_checkCapacity] after using this method.
+   */
+  int _put(K key) {
+    int offset = _probeForAdd(_hashCodeOf(key), key);
+    Object oldEntry = _table[offset];
+    if (oldEntry == null) {
+      _entryCount++;
+    } else if (identical(oldEntry, _TOMBSTONE)) {
+      _deletedCount--;
+    } else {
+      return offset;
+    }
+    _setKey(offset, key);
+    _recordModification();
+    return offset;
+  }
+
+  /**
+   * Removes a key from the table and returns its offset into [_table].
+   *
+   * Returns null if the key was not in the table.
+   * If [_entrySize] is greater than 1, the caller should clean up the
+   * remaining fields.
+   */
+  int _remove(K key) {
+    int offset = _probeForLookup(_hashCodeOf(key), key);
+    if (offset >= 0) {
+      _deleteEntry(offset);
+    }
+    return offset;
+  }
+
+  /** Clears the table completely, leaving it empty. */
+  void _clear() {
+    if (_elementCount == 0) return;
+    for (int i = 0; i < _table.length; i++) {
+      _table[i] = null;
+    }
+    _entryCount = _deletedCount = 0;
+    _recordModification();
+  }
+
+  /** Clears an entry in the table. */
+  void _deleteEntry(int offset) {
+    assert(!_isFree(_table[offset]));
+    _setKey(offset, _TOMBSTONE);
+    _deletedCount++;
+    _recordModification();
+  }
+}
+
+/**
+ * Generic iterable based on a [_HashTable].
+ */
+abstract class _HashTableIterable<E> extends Iterable<E> {
+  final _HashTable _hashTable;
+  _HashTableIterable(this._hashTable);
+
+  Iterator<E> get iterator;
+
+  /**
+   * Return the iterated value for a given entry.
+   */
+  E _valueAt(int offset, Object key);
+
+  int get length => _hashTable._elementCount;
+
+  bool get isEmpty => _hashTable._elementCount == 0;
+
+  void forEach(void action(E element)) {
+    int entrySize = _hashTable._entrySize;
+    List table = _hashTable._table;
+    int modificationCount = _hashTable._modificationCount;
+    for (int offset = 0; offset < table.length; offset += entrySize) {
+      Object entry = table[offset];
+      if (!_hashTable._isFree(entry)) {
+        E value = _valueAt(offset, entry);
+        action(value);
+      }
+      _hashTable._checkModification(modificationCount);
+    }
+  }
+}
+
+abstract class _HashTableIterator<E> implements Iterator<E> {
+  final _HashTable _hashTable;
+  final int _modificationCount;
+  /** Location right after last found element. */
+  int _offset = 0;
+  E _current = null;
+
+  _HashTableIterator(_HashTable hashTable)
+      : _hashTable = hashTable,
+        _modificationCount = hashTable._modificationCount;
+
+  bool moveNext() {
+    _hashTable._checkModification(_modificationCount);
+
+    List table = _hashTable._table;
+    int entrySize = _hashTable._entrySize;
+
+    while (_offset < table.length) {
+      int currentOffset = _offset;
+      Object entry = table[currentOffset];
+      _offset = currentOffset + entrySize;
+      if (!_hashTable._isFree(entry)) {
+        _current = _valueAt(currentOffset, entry);
+        return true;
+      }
+    }
+    _current = null;
+    return false;
+  }
+
+  E get current => _current;
+
+  E _valueAt(int offset, Object key);
+}
+
+class _HashTableKeyIterable<K> extends _HashTableIterable<K> {
+  _HashTableKeyIterable(_HashTable<K> hashTable) : super(hashTable);
+
+  Iterator<K> get iterator => new _HashTableKeyIterator<K>(_hashTable);
+
+  K _valueAt(int offset, Object key) {
+    if (identical(key, _NULL)) return null;
+    return key;
+  }
+
+  bool contains(Object value) => _hashTable._get(value) >= 0;
+}
+
+class _HashTableKeyIterator<K> extends _HashTableIterator<K> {
+  _HashTableKeyIterator(_HashTable hashTable) : super(hashTable);
+
+  K _valueAt(int offset, Object key) {
+    if (identical(key, _NULL)) return null;
+    return key;
+  }
+}
+
+class _HashTableValueIterable<V> extends _HashTableIterable<V> {
+  final int _entryIndex;
+
+  _HashTableValueIterable(_HashTable hashTable, this._entryIndex)
+      : super(hashTable);
+
+  Iterator<V> get iterator {
+    return new _HashTableValueIterator<V>(_hashTable, _entryIndex);
+  }
+
+  V _valueAt(int offset, Object key) => _hashTable._table[offset + _entryIndex];
+}
+
+class _HashTableValueIterator<V> extends _HashTableIterator<V> {
+  final int _entryIndex;
+
+  _HashTableValueIterator(_HashTable hashTable, this._entryIndex)
+      : super(hashTable);
+
+  V _valueAt(int offset, Object key) => _hashTable._table[offset + _entryIndex];
+}
diff --git a/sdk/lib/collection/linked_hash_map.dart b/sdk/lib/collection/linked_hash_map.dart
new file mode 100644
index 0000000..4dcbc060
--- /dev/null
+++ b/sdk/lib/collection/linked_hash_map.dart
@@ -0,0 +1,138 @@
+// Copyright (c) 2013, 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.
+
+part of dart.collection;
+
+class _LinkedHashMapTable<K, V> extends _LinkedHashTable<K> {
+  static const int _INITIAL_CAPACITY = 8;
+  static const int _VALUE_INDEX = 3;
+
+  int get _entrySize => 4;
+
+  _LinkedHashMapTable() : super(_INITIAL_CAPACITY);
+
+  V _value(int offset) => _table[offset + _VALUE_INDEX];
+  void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; }
+
+  _copyEntry(List oldTable, int fromOffset, int toOffset) {
+    _table[toOffset + _VALUE_INDEX] = oldTable[fromOffset + _VALUE_INDEX];
+  }
+}
+
+/**
+ * A hash-based map that iterates keys and values in key insertion order.
+ */
+class LinkedHashMap<K, V> implements Map<K, V> {
+  final _LinkedHashMapTable _hashTable;
+
+  LinkedHashMap() : _hashTable = new _LinkedHashMapTable<K, V>() {
+    _hashTable._container = this;
+  }
+
+  factory LinkedHashMap.from(Map<K, V> other) {
+    return new LinkedHashMap<K, V>()..addAll(other);
+  }
+
+  bool containsKey(K key) {
+    return _hashTable._get(key) >= 0;
+  }
+
+  bool containsValue(V value) {
+    int modificationCount = _hashTable._modificationCount;
+    for (int offset = _hashTable._next(_LinkedHashTable._HEAD_OFFSET);
+         offset != _LinkedHashTable._HEAD_OFFSET;
+         offset = _hashTable._next(offset)) {
+      if (_hashTable._value(offset) == value) {
+        return true;
+      }
+      // The == call may modify the table.
+      _hashTable._checkModification(modificationCount);
+    }
+    return false;
+  }
+
+  void addAll(Map<K, V> other) {
+    other.forEach((K key, V value) {
+      int offset = _hashTable._put(key);
+      _hashTable._setValue(offset, value);
+      _hashTable._checkCapacity();
+    });
+  }
+
+  V operator [](K key) {
+    int offset = _hashTable._get(key);
+    if (offset >= 0) return _hashTable._value(offset);
+    return null;
+  }
+
+  void operator []=(K key, V value) {
+    int offset = _hashTable._put(key);
+    _hashTable._setValue(offset, value);
+    _hashTable._checkCapacity();
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key);
+    Object entry = _hashTable._table[offset];
+    if (!_hashTable._isFree(entry)) {
+      return _hashTable._value(offset);
+    }
+    int modificationCount = _hashTable._modificationCount;
+    V value = ifAbsent();
+    if (modificationCount == _hashTable._modificationCount) {
+      _hashTable._setKey(offset, key);
+      _hashTable._setValue(offset, value);
+      _hashTable._linkLast(offset);
+      if (entry == null) {
+        _hashTable._entryCount++;
+        _hashTable._checkCapacity();
+      } else {
+        assert(identical(entry, _TOMBSTONE));
+        _hashTable._deletedCount--;
+      }
+      _hashTable._recordModification();
+    } else {
+      // The table might have changed, so we can't trust [offset] any more.
+      // Do another lookup before setting the value.
+      offset = _hashTable._put(key);
+      _hashTable._setValue(offset, value);
+      _hashTable._checkCapacity();
+    }
+    return value;
+  }
+
+  V remove(K key) {
+    int offset = _hashTable._remove(key);
+    if (offset < 0) return null;
+    Object oldValue = _hashTable._value(offset);
+    _hashTable._setValue(offset, null);
+    _hashTable._checkCapacity();
+    return oldValue;
+  }
+
+  void clear() {
+    _hashTable._clear();
+  }
+
+  void forEach(void action (K key, V value)) {
+    int modificationCount = _hashTable._modificationCount;
+    for (int offset = _hashTable._next(_LinkedHashTable._HEAD_OFFSET);
+         offset != _LinkedHashTable._HEAD_OFFSET;
+         offset = _hashTable._next(offset)) {
+      action(_hashTable._key(offset), _hashTable._value(offset));
+      _hashTable._checkModification(modificationCount);
+    }
+  }
+
+  Iterable<K> get keys => new _LinkedHashTableKeyIterable<K>(_hashTable);
+  Iterable<V> get values =>
+      new _LinkedHashTableValueIterable<V>(_hashTable,
+                                           _LinkedHashMapTable._VALUE_INDEX);
+
+  int get length => _hashTable._elementCount;
+
+  bool get isEmpty => _hashTable._elementCount == 0;
+
+  String toString() => Maps.mapToString(this);
+}
diff --git a/sdk/lib/collection/linked_hash_set.dart b/sdk/lib/collection/linked_hash_set.dart
new file mode 100644
index 0000000..e72493a
--- /dev/null
+++ b/sdk/lib/collection/linked_hash_set.dart
@@ -0,0 +1,157 @@
+// Copyright (c) 2013, 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.
+
+part of dart.collection;
+
+class LinkedHashSet<E> extends Collection<E> implements Set<E> {
+  static const int _INITIAL_CAPACITY = 8;
+  _LinkedHashTable<E> _table;
+
+  LinkedHashSet() : _table = new _LinkedHashTable(_INITIAL_CAPACITY) {
+    _table._container = this;
+  }
+
+  factory LinkedHashSet.from(Iterable<E> iterable) {
+    return new LinkedHashSet<E>()..addAll(iterable);
+  }
+
+  // Iterable.
+  Iterator<E> get iterator => new _LinkedHashTableKeyIterator<E>(_table);
+
+  void forEach(void action(E element)) {
+    int offset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    int modificationCount = _table._modificationCount;
+    while (offset != _LinkedHashTable._HEAD_OFFSET) {
+      E key = _table._key(offset);
+      action(key);
+      _table._checkModification(modificationCount);
+      offset = _table._next(offset);
+    }
+  }
+
+  bool get isEmpty => _table._elementCount == 0;
+
+  bool contains(Object object) => _table._get(object) >= 0;
+
+  E get first {
+    int firstOffset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    if (firstOffset == _LinkedHashTable._HEAD_OFFSET) {
+      throw new StateError("No elements");
+    }
+    return _table._key(firstOffset);
+  }
+
+  E get last {
+    int lastOffset = _table._prev(_LinkedHashTable._HEAD_OFFSET);
+    if (lastOffset == _LinkedHashTable._HEAD_OFFSET) {
+      throw new StateError("No elements");
+    }
+    return _table._key(lastOffset);
+  }
+
+  E get single {
+    int firstOffset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    if (firstOffset == _LinkedHashTable._HEAD_OFFSET) {
+      throw new StateError("No elements");
+    }
+    int lastOffset = _table._prev(_LinkedHashTable._HEAD_OFFSET);
+    if (lastOffset != firstOffset) {
+      throw new StateError("Too many elements");
+    }
+    return _table._key(firstOffset);
+  }
+
+  // Collection.
+  void add(E element) {
+    _table._put(element);
+    _table._checkCapacity();
+  }
+
+  void addAll(Iterable<E> objects) {
+    for (E object in objects) {
+      _table._put(object);
+      _table._checkCapacity();
+    }
+  }
+
+  bool remove(Object object) {
+    int offset = _table._remove(object);
+    if (offset >= 0) {
+      _table._checkCapacity();
+      return true;
+    }
+    return false;
+  }
+
+  void removeAll(Iterable objectsToRemove) {
+    for (Object object in objectsToRemove) {
+      _table._remove(object);
+      _table._checkCapacity();
+    }
+  }
+
+  void retainAll(Iterable objectsToRemove) {
+    IterableMixinWorkaround.retainAll(this, objectsToRemove);
+  }
+
+  void _filterMatching(bool test(E element), bool removeMatching) {
+    int entrySize = _table._entrySize;
+    int length = _table._table.length;
+    int offset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    while (offset != _LinkedHashTable._HEAD_OFFSET) {
+      E key = _table._key(offset);
+      int nextOffset = _table._next(offset);
+      int modificationCount = _table._modificationCount;
+      bool shouldRemove = (removeMatching == test(key));
+      _table._checkModification(modificationCount);
+      if (shouldRemove) {
+        _table._deleteEntry(offset);
+      }
+      offset = nextOffset;
+    }
+    _table._checkCapacity();
+  }
+
+  void removeMatching(bool test(E element)) {
+    _filterMatching(test, true);
+  }
+
+  void retainMatching(bool test(E element)) {
+    _filterMatching(test, false);
+  }
+
+  void clear() {
+    _table._clear();
+  }
+
+  // Set.
+  bool isSubsetOf(Collection<E> collection) {
+    Set otherSet;
+    if (collection is Set) {
+      otherSet = collection;
+    } else {
+      otherSet = collection.toSet();
+    }
+    return otherSet.containsAll(this);
+  }
+
+  bool containsAll(Collection<E> collection) {
+    for (E element in collection) {
+      if (!this.contains(element)) return false;
+    }
+    return true;
+  }
+
+  Set<E> intersection(Collection<E> other) {
+    Set<E> result = new LinkedHashSet<E>();
+    for (E element in other) {
+      if (this.contains(element)) {
+        result.add(element);
+      }
+    }
+    return result;
+  }
+
+  String toString() => Collections.collectionToString(this);
+}
diff --git a/sdk/lib/collection/linked_hash_table.dart b/sdk/lib/collection/linked_hash_table.dart
new file mode 100644
index 0000000..fbf6172
--- /dev/null
+++ b/sdk/lib/collection/linked_hash_table.dart
@@ -0,0 +1,165 @@
+// Copyright (c) 2013, 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.
+
+part of dart.collection;
+
+/** Unique marker object for the head of a linked list of entries. */
+class _LinkedHashTableHeadMarker {
+  const _LinkedHashTableHeadMarker();
+}
+
+const _LinkedHashTableHeadMarker _HEAD_MARKER =
+    const _LinkedHashTableHeadMarker();
+
+class _LinkedHashTable<K> extends _HashTable<K> {
+  static const _NEXT_INDEX = 1;
+  static const _PREV_INDEX = 2;
+  static const _HEAD_OFFSET = 0;
+
+  _LinkedHashTable(int initialCapacity) : super(initialCapacity);
+
+  int get _entrySize => 3;
+
+  List _createTable(int capacity) {
+    List result = new List.fixedLength(capacity * _entrySize);
+    result[_HEAD_OFFSET] = _HEAD_MARKER;
+    result[_HEAD_OFFSET + _NEXT_INDEX] = _HEAD_OFFSET;
+    result[_HEAD_OFFSET + _PREV_INDEX] = _HEAD_OFFSET;
+    return result;
+  }
+
+  int _next(int offset) => _table[offset + _NEXT_INDEX];
+  void _setNext(int offset, int to) { _table[offset + _NEXT_INDEX] = to; }
+
+  int _prev(int offset) => _table[offset + _PREV_INDEX];
+  void _setPrev(int offset, int to) { _table[offset + _PREV_INDEX] = to; }
+
+  void _linkLast(int offset) {
+    // Add entry at offset at end of double-linked list.
+    int last = _prev(_HEAD_OFFSET);
+    _setNext(offset, _HEAD_OFFSET);
+    _setPrev(offset, last);
+    _setNext(last, offset);
+    _setPrev(_HEAD_OFFSET, offset);
+  }
+
+  void _unlink(int offset) {
+    assert(offset != _HEAD_OFFSET);
+    int next = _next(offset);
+    int prev = _prev(offset);
+    _setNext(offset, null);
+    _setPrev(offset, null);
+    _setNext(prev, next);
+    _setPrev(next, prev);
+  }
+
+  /**
+   * Copies all non-free entries from the old table to the new empty table.
+   */
+  void _addAllEntries(List oldTable) {
+    int offset = oldTable[_HEAD_OFFSET + _NEXT_INDEX];
+    while (offset != _HEAD_OFFSET) {
+      Object object = oldTable[offset];
+      int nextOffset = oldTable[offset + _NEXT_INDEX];
+      int toOffset = _put(object);
+      _copyEntry(oldTable, offset, toOffset);
+      offset = nextOffset;
+    }
+  }
+
+  void _clear() {
+    if (_elementCount == 0) return;
+    _setNext(_HEAD_OFFSET, _HEAD_OFFSET);
+    _setPrev(_HEAD_OFFSET, _HEAD_OFFSET);
+    for (int i = _entrySize; i < _table.length; i++) {
+      _table[i] = null;
+    }
+    _entryCount = _deletedCount = 0;
+    _recordModification();
+  }
+
+  int _put(K key) {
+    int offset = _probeForAdd(_hashCodeOf(key), key);
+    Object oldEntry = _table[offset];
+    if (identical(oldEntry, _TOMBSTONE)) {
+      _deletedCount--;
+    } else if (oldEntry == null) {
+      _entryCount++;
+    } else {
+      return offset;
+    }
+    _recordModification();
+    _setKey(offset, key);
+    _linkLast(offset);
+    return offset;
+  }
+
+  void _deleteEntry(int offset) {
+    _unlink(offset);
+    _setKey(offset, _TOMBSTONE);
+    _deletedCount++;
+    _recordModification();
+  }
+}
+
+class _LinkedHashTableKeyIterable<K> extends Iterable<K> {
+  final _LinkedHashTable<K> _table;
+  _LinkedHashTableKeyIterable(this._table);
+  Iterator<K> get iterator => new _LinkedHashTableKeyIterator<K>(_table);
+
+  bool contains(Object value) => _table._get(value) >= 0;
+
+  int get length => _table._elementCount;
+}
+
+class _LinkedHashTableKeyIterator<K> extends _LinkedHashTableIterator<K> {
+  _LinkedHashTableKeyIterator(_LinkedHashTable<K> hashTable): super(hashTable);
+
+  K _getCurrent(int offset) => _hashTable._key(offset);
+}
+
+class _LinkedHashTableValueIterable<V> extends Iterable<V> {
+  final _LinkedHashTable _hashTable;
+  final int _valueIndex;
+  _LinkedHashTableValueIterable(this._hashTable, this._valueIndex);
+  Iterator<V> get iterator =>
+      new _LinkedHashTableValueIterator<V>(_hashTable, _valueIndex);
+  int get length => _hashTable._elementCount;
+}
+
+class _LinkedHashTableValueIterator<V> extends _LinkedHashTableIterator<V> {
+  final int _valueIndex;
+
+  _LinkedHashTableValueIterator(_LinkedHashTable hashTable, this._valueIndex)
+      : super(hashTable);
+
+  V _getCurrent(int offset) => _hashTable._table[offset + _valueIndex];
+}
+
+abstract class _LinkedHashTableIterator<T> implements Iterator<T> {
+  final _LinkedHashTable _hashTable;
+  final int _modificationCount;
+  int _offset;
+  T _current;
+
+  _LinkedHashTableIterator(_LinkedHashTable table)
+      : _hashTable = table,
+        _modificationCount = table._modificationCount,
+        _offset = table._next(_LinkedHashTable._HEAD_OFFSET);
+
+  bool moveNext() {
+    _hashTable._checkModification(_modificationCount);
+    if (_offset == _LinkedHashTable._HEAD_OFFSET) {
+      _current = null;
+      return false;
+    }
+    _current = _getCurrent(_offset);
+    _offset = _hashTable._next(_offset);
+    return true;
+  }
+
+  T _getCurrent(int offset);
+
+  T get current => _current;
+}
diff --git a/sdk/lib/collection/map.dart b/sdk/lib/collection/map.dart
deleted file mode 100644
index 1beaf2b..0000000
--- a/sdk/lib/collection/map.dart
+++ /dev/null
@@ -1,474 +0,0 @@
-// Copyright (c) 2013, 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.
-
-part of dart.collection;
-
-
-/**
- * Hash map version of the [Map] interface. A [HashMap] does not
- * provide any guarantees on the order of keys and values in [keys]
- * and [values].
- */
-abstract class HashMap<K, V> extends Map<K, V> {
-  /**
-   * Creates a map with the default implementation.
-   */
-  factory HashMap() => new _HashMapImpl<K, V>();
-
-  /**
-   * Creates a [HashMap] that contains all key value pairs of [other].
-   */
-  factory HashMap.from(Map<K, V> other) => new _HashMapImpl<K, V>.from(other);
-}
-
-/**
- * Hash map version of the [Map] interface that preserves insertion
- * order.
- */
-abstract class LinkedHashMap<K, V> extends HashMap<K, V> {
-  /**
-   * Creates a map with the default implementation.
-   */
-  factory LinkedHashMap() => new _LinkedHashMapImpl<K, V>();
-
-  /**
-   * Creates a [LinkedHashMap] that contains all key value pairs of [other].
-   */
-  factory LinkedHashMap.from(Map<K, V> other)
-    => new _LinkedHashMapImpl<K, V>.from(other);
-}
-
-
-// Hash map implementation with open addressing and quadratic probing.
-class _HashMapImpl<K, V> implements HashMap<K, V> {
-
-  // The [_keys] list contains the keys inserted in the map.
-  // The [_keys] list must be a raw list because it
-  // will contain both elements of type K, and the [_DELETED_KEY] of type
-  // [_DeletedKeySentinel].
-  // The alternative of declaring the [_keys] list as of type Object
-  // does not work, because the HashSetIterator constructor would fail:
-  //  HashSetIterator(HashSet<E> set)
-  //    : _nextValidIndex = -1,
-  //      _entries = set_._backingMap._keys {
-  //    _advance();
-  //  }
-  // With K being type int, for example, it would fail because
-  // List<Object> is not assignable to type List<int> of entries.
-  List _keys;
-
-  // The values inserted in the map. For a filled entry index in this
-  // list, there is always the corresponding key in the [keys_] list
-  // at the same entry index.
-  List<V> _values;
-
-  // The load limit is the number of entries we allow until we double
-  // the size of the lists.
-  int _loadLimit;
-
-  // The current number of entries in the map. Will never be greater
-  // than [_loadLimit].
-  int _numberOfEntries;
-
-  // The current number of deleted entries in the map.
-  int _numberOfDeleted;
-
-  // The sentinel when a key is deleted from the map.
-  static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel();
-
-  // The initial capacity of a hash map.
-  static const int _INITIAL_CAPACITY = 8;  // must be power of 2
-
-  _HashMapImpl() {
-    _numberOfEntries = 0;
-    _numberOfDeleted = 0;
-    _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY);
-    _keys = new List.fixedLength(_INITIAL_CAPACITY);
-    _values = new List<V>.fixedLength(_INITIAL_CAPACITY);
-  }
-
-  factory _HashMapImpl.from(Map<K, V> other) {
-    Map<K, V> result = new _HashMapImpl<K, V>();
-    other.forEach((K key, V value) { result[key] = value; });
-    return result;
-  }
-
-  static int _computeLoadLimit(int capacity) {
-    return (capacity * 3) ~/ 4;
-  }
-
-  static int _firstProbe(int hashCode, int length) {
-    return hashCode & (length - 1);
-  }
-
-  static int _nextProbe(int currentProbe, int numberOfProbes, int length) {
-    return (currentProbe + numberOfProbes) & (length - 1);
-  }
-
-  int _probeForAdding(K key) {
-    if (key == null) throw new ArgumentError(null);
-    int hash = _firstProbe(key.hashCode, _keys.length);
-    int numberOfProbes = 1;
-    int initialHash = hash;
-    // insertionIndex points to a slot where a key was deleted.
-    int insertionIndex = -1;
-    while (true) {
-      // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
-      Object existingKey = _keys[hash];
-      if (existingKey == null) {
-        // We are sure the key is not already in the set.
-        // If the current slot is empty and we didn't find any
-        // insertion slot before, return this slot.
-        if (insertionIndex < 0) return hash;
-        // If we did find an insertion slot before, return it.
-        return insertionIndex;
-      } else if (existingKey == key) {
-        // The key is already in the map. Return its slot.
-        return hash;
-      } else if ((insertionIndex < 0) &&
-                 (identical(existingKey, _DELETED_KEY))) {
-        // The slot contains a deleted element. Because previous calls to this
-        // method may not have had this slot deleted, we must continue iterate
-        // to find if there is a slot with the given key.
-        insertionIndex = hash;
-      }
-
-      // We did not find an insertion slot. Look at the next one.
-      hash = _nextProbe(hash, numberOfProbes++, _keys.length);
-      // _ensureCapacity has guaranteed the following cannot happen.
-      // assert(hash != initialHash);
-    }
-  }
-
-  int _probeForLookup(K key) {
-    if (key == null) throw new ArgumentError(null);
-    int hash = _firstProbe(key.hashCode, _keys.length);
-    int numberOfProbes = 1;
-    int initialHash = hash;
-    while (true) {
-      // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
-      Object existingKey = _keys[hash];
-      // If the slot does not contain anything (in particular, it does not
-      // contain a deleted key), we know the key is not in the map.
-      if (existingKey == null) return -1;
-      // The key is in the map, return its index.
-      if (existingKey == key) return hash;
-      // Go to the next probe.
-      hash = _nextProbe(hash, numberOfProbes++, _keys.length);
-      // _ensureCapacity has guaranteed the following cannot happen.
-      // assert(hash != initialHash);
-    }
-  }
-
-  void _ensureCapacity() {
-    int newNumberOfEntries = _numberOfEntries + 1;
-    // Test if adding an element will reach the load limit.
-    if (newNumberOfEntries >= _loadLimit) {
-      _grow(_keys.length * 2);
-      return;
-    }
-
-    // Make sure that we don't have poor performance when a map
-    // contains lots of deleted entries: we _grow if
-    // there are more deleted entried than free entries.
-    int capacity = _keys.length;
-    int numberOfFreeOrDeleted = capacity - newNumberOfEntries;
-    int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted;
-    // assert(numberOfFree > 0);
-    if (_numberOfDeleted > numberOfFree) {
-      _grow(_keys.length);
-    }
-  }
-
-  static bool _isPowerOfTwo(int x) {
-    return ((x & (x - 1)) == 0);
-  }
-
-  void _grow(int newCapacity) {
-    assert(_isPowerOfTwo(newCapacity));
-    int capacity = _keys.length;
-    _loadLimit = _computeLoadLimit(newCapacity);
-    List oldKeys = _keys;
-    List<V> oldValues = _values;
-    _keys = new List.fixedLength(newCapacity);
-    _values = new List<V>.fixedLength(newCapacity);
-    for (int i = 0; i < capacity; i++) {
-      // [key] can be either of type [K] or [_DeletedKeySentinel].
-      Object key = oldKeys[i];
-      // If there is no key, we don't need to deal with the current slot.
-      if (key == null || identical(key, _DELETED_KEY)) {
-        continue;
-      }
-      V value = oldValues[i];
-      // Insert the {key, value} pair in their new slot.
-      int newIndex = _probeForAdding(key);
-      _keys[newIndex] = key;
-      _values[newIndex] = value;
-    }
-    _numberOfDeleted = 0;
-  }
-
-  void clear() {
-    _numberOfEntries = 0;
-    _numberOfDeleted = 0;
-    int length = _keys.length;
-    for (int i = 0; i < length; i++) {
-      _keys[i] = null;
-      _values[i] = null;
-    }
-  }
-
-  void operator []=(K key, V value) {
-    _ensureCapacity();
-    int index = _probeForAdding(key);
-    if ((_keys[index] == null) || (identical(_keys[index], _DELETED_KEY))) {
-      _numberOfEntries++;
-    }
-    _keys[index] = key;
-    _values[index] = value;
-  }
-
-  V operator [](K key) {
-    int index = _probeForLookup(key);
-    if (index < 0) return null;
-    return _values[index];
-  }
-
-  V putIfAbsent(K key, V ifAbsent()) {
-    int index = _probeForLookup(key);
-    if (index >= 0) return _values[index];
-
-    V value = ifAbsent();
-    this[key] = value;
-    return value;
-  }
-
-  V remove(K key) {
-    int index = _probeForLookup(key);
-    if (index >= 0) {
-      _numberOfEntries--;
-      V value = _values[index];
-      _values[index] = null;
-      // Set the key to the sentinel to not break the probing chain.
-      _keys[index] = _DELETED_KEY;
-      _numberOfDeleted++;
-      return value;
-    }
-    return null;
-  }
-
-  bool get isEmpty {
-    return _numberOfEntries == 0;
-  }
-
-  int get length {
-    return _numberOfEntries;
-  }
-
-  void forEach(void f(K key, V value)) {
-    Iterator<int> it = new _HashMapImplIndexIterator(this);
-    while (it.moveNext()) {
-      f(_keys[it.current], _values[it.current]);
-    }
-  }
-
-  Iterable<K> get keys => new _HashMapImplKeyIterable<K>(this);
-
-  Iterable<V> get values => new _HashMapImplValueIterable<V>(this);
-
-  bool containsKey(K key) {
-    return (_probeForLookup(key) != -1);
-  }
-
-  bool containsValue(V value) => values.contains(value);
-
-  String toString() {
-    return Maps.mapToString(this);
-  }
-}
-
-class _HashMapImplKeyIterable<E> extends Iterable<E> {
-  final _HashMapImpl _map;
-  _HashMapImplKeyIterable(this._map);
-
-  Iterator<E> get iterator => new _HashMapImplKeyIterator<E>(_map);
-}
-
-class _HashMapImplValueIterable<E> extends Iterable<E> {
-  final _HashMapImpl _map;
-  _HashMapImplValueIterable(this._map);
-
-  Iterator<E> get iterator => new _HashMapImplValueIterator<E>(_map);
-}
-
-abstract class _HashMapImplIterator<E> implements Iterator<E> {
-  final _HashMapImpl _map;
-  int _index = -1;
-  E _current;
-
-  _HashMapImplIterator(this._map);
-
-  E _computeCurrentFromIndex(int index, List keys, List values);
-
-  bool moveNext() {
-    int length = _map._keys.length;
-    int newIndex = _index + 1;
-    while (newIndex < length) {
-      var key = _map._keys[newIndex];
-      if ((key != null) && (!identical(key, _HashMapImpl._DELETED_KEY))) {
-        _current = _computeCurrentFromIndex(newIndex, _map._keys, _map._values);
-        _index = newIndex;
-        return true;
-      }
-      newIndex++;
-    }
-    _index = length;
-    _current = null;
-    return false;
-  }
-
-  E get current => _current;
-}
-
-class _HashMapImplKeyIterator<E> extends _HashMapImplIterator<E> {
-  _HashMapImplKeyIterator(_HashMapImpl map) : super(map);
-
-  E _computeCurrentFromIndex(int index, List keys, List values) {
-    return keys[index];
-  }
-}
-
-class _HashMapImplValueIterator<E> extends _HashMapImplIterator<E> {
-  _HashMapImplValueIterator(_HashMapImpl map) : super(map);
-
-  E _computeCurrentFromIndex(int index, List keys, List values) {
-    return values[index];
-  }
-}
-
-class _HashMapImplIndexIterator extends _HashMapImplIterator<int> {
-  _HashMapImplIndexIterator(_HashMapImpl map) : super(map);
-
-  int _computeCurrentFromIndex(int index, List keys, List values) {
-    return index;
-  }
-}
-
-/**
- * A singleton sentinel used to represent when a key is deleted from the map.
- * We can't use [: const Object() :] as a sentinel because it would end up
- * canonicalized and then we cannot distinguish the deleted key from the
- * canonicalized [: Object() :].
- */
-class _DeletedKeySentinel {
-  const _DeletedKeySentinel();
-}
-
-
-/**
- * This class represents a pair of two objects, used by LinkedHashMap
- * to store a {key, value} in a list.
- */
-class _KeyValuePair<K, V> {
-  _KeyValuePair(this.key, this.value) {}
-
-  final K key;
-  V value;
-}
-
-/**
- * A LinkedHashMap is a hash map that preserves the insertion order
- * when iterating over the keys or the values. Updating the value of a
- * key does not change the order.
- */
-class _LinkedHashMapImpl<K, V> implements LinkedHashMap<K, V> {
-  DoubleLinkedQueue<_KeyValuePair<K, V>> _list;
-  HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>> _map;
-
-  _LinkedHashMapImpl() {
-    _map = new HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>>();
-    _list = new DoubleLinkedQueue<_KeyValuePair<K, V>>();
-  }
-
-  factory _LinkedHashMapImpl.from(Map<K, V> other) {
-    Map<K, V> result = new _LinkedHashMapImpl<K, V>();
-    other.forEach((K key, V value) { result[key] = value; });
-    return result;
-  }
-
-  void operator []=(K key, V value) {
-    if (_map.containsKey(key)) {
-      _map[key].element.value = value;
-    } else {
-      _list.addLast(new _KeyValuePair<K, V>(key, value));
-      _map[key] = _list.lastEntry();
-    }
-  }
-
-  V operator [](K key) {
-    DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key];
-    if (entry == null) return null;
-    return entry.element.value;
-  }
-
-  V remove(K key) {
-    DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key);
-    if (entry == null) return null;
-    entry.remove();
-    return entry.element.value;
-  }
-
-  V putIfAbsent(K key, V ifAbsent()) {
-    V value = this[key];
-    if ((this[key] == null) && !(containsKey(key))) {
-      value = ifAbsent();
-      this[key] = value;
-    }
-    return value;
-  }
-
-  Iterable<K> get keys {
-    return new MappedIterable<_KeyValuePair<K, V>, K>(
-        _list, (_KeyValuePair<K, V> entry) => entry.key);
-  }
-
-
-  Iterable<V> get values {
-    return new MappedIterable<_KeyValuePair<K, V>, V>(
-        _list, (_KeyValuePair<K, V> entry) => entry.value);
-  }
-
-  void forEach(void f(K key, V value)) {
-    _list.forEach((_KeyValuePair<K, V> entry) {
-      f(entry.key, entry.value);
-    });
-  }
-
-  bool containsKey(K key) {
-    return _map.containsKey(key);
-  }
-
-  bool containsValue(V value) {
-    return _list.any((_KeyValuePair<K, V> entry) {
-      return (entry.value == value);
-    });
-  }
-
-  int get length {
-    return _map.length;
-  }
-
-  bool get isEmpty {
-    return length == 0;
-  }
-
-  void clear() {
-    _map.clear();
-    _list.clear();
-  }
-
-  String toString() {
-    return Maps.mapToString(this);
-  }
-}
diff --git a/sdk/lib/collection/set.dart b/sdk/lib/collection/set.dart
deleted file mode 100644
index 9363676..0000000
--- a/sdk/lib/collection/set.dart
+++ /dev/null
@@ -1,110 +0,0 @@
-// Copyright (c) 2013, 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.
-
-part of dart.collection;
-
-
-
-class HashSet<E> extends Collection<E> implements Set<E> {
-  // The map backing this set. The associations in this map are all
-  // of the form element -> element. If a value is not in the map,
-  // then it is not in the set.
-  final _HashMapImpl<E, E> _backingMap;
-
-  HashSet() : _backingMap = new _HashMapImpl<E, E>();
-
-  /**
-   * Creates a [Set] that contains all elements of [other].
-   */
-  factory HashSet.from(Iterable<E> other) {
-    Set<E> set = new HashSet<E>();
-    for (final e in other) {
-      set.add(e);
-    }
-    return set;
-  }
-
-  void clear() {
-    _backingMap.clear();
-  }
-
-  void add(E value) {
-    _backingMap[value] = value;
-  }
-
-  bool remove(Object value) {
-    if (!_backingMap.containsKey(value)) return false;
-    _backingMap.remove(value);
-    return true;
-  }
-
-  bool contains(E value) {
-    return _backingMap.containsKey(value);
-  }
-
-  Set<E> intersection(Collection<E> collection) {
-    Set<E> result = new Set<E>();
-    collection.forEach((E value) {
-      if (contains(value)) result.add(value);
-    });
-    return result;
-  }
-
-  bool isSubsetOf(Collection<E> other) {
-    return new Set<E>.from(other).containsAll(this);
-  }
-
-  bool containsAll(Collection<E> collection) {
-    return collection.every((E value) {
-      return contains(value);
-    });
-  }
-
-  void forEach(void f(E element)) {
-    _backingMap.forEach((E key, E value) {
-      f(key);
-    });
-  }
-
-  bool get isEmpty {
-    return _backingMap.isEmpty;
-  }
-
-  int get length {
-    return _backingMap.length;
-  }
-
-  Iterator<E> get iterator => new _HashSetIterator<E>(this);
-
-  String toString() {
-    return Collections.collectionToString(this);
-  }
-}
-
-class _HashSetIterator<E> implements Iterator<E> {
-
-  _HashSetIterator(HashSet<E> set)
-    : _keysIterator = set._backingMap._keys.iterator;
-
-  E get current {
-    var result = _keysIterator.current;
-    if (identical(result, _HashMapImpl._DELETED_KEY)) {
-      // TODO(floitsch): improve the error reporting.
-      throw new StateError("Concurrent modification.");
-    }
-    return result;
-  }
-
-  bool moveNext() {
-    bool result;
-    do {
-      result = _keysIterator.moveNext();
-    } while (result &&
-             (_keysIterator.current == null ||
-              identical(_keysIterator.current, _HashMapImpl._DELETED_KEY)));
-    return result;
-  }
-
-  Iterator _keysIterator;
-}
diff --git a/sdk/lib/collection/splay_tree.dart b/sdk/lib/collection/splay_tree.dart
index d9eca77..31be011 100644
--- a/sdk/lib/collection/splay_tree.dart
+++ b/sdk/lib/collection/splay_tree.dart
@@ -9,12 +9,12 @@
  * and right children in the tree.
  */
 class SplayTreeNode<K, V> {
-  SplayTreeNode(K this.key, V this.value);
-
-  K key;
+  final K key;
   V value;
   SplayTreeNode<K, V> left;
   SplayTreeNode<K, V> right;
+
+  SplayTreeNode(K this.key, V this.value);
 }
 
 /**
@@ -40,10 +40,23 @@
   // Number of elements in the splay tree.
   int _count;
 
-  SplayTreeMap() {
-    _dummy = new SplayTreeNode<K, V>(null, null);
+  /**
+   * Counter incremented whenever the keys in the map changes.
+   *
+   * Used to detect concurrent modifications.
+   */
+  int _modificationCount = 0;
+  /**
+   * Counter incremented whenever the tree structure changes.
+   *
+   * Used to detect that an in-place traversal cannot use
+   * cached information that relies on the tree structure.
+   */
+  int _splayCount = 0;
+
+  SplayTreeMap() :
+    _dummy = new SplayTreeNode<K, V>(null, null),
     _count = 0;
-  }
 
   /**
    * Perform the splay operation for the given key. Moves the node with
@@ -51,9 +64,12 @@
    * key, the last node on the search path is moved to the top of the
    * tree. This is the simplified top-down splaying algorithm from:
    * "Self-adjusting Binary Search Trees" by Sleator and Tarjan.
+   *
+   * Returns the result of comparing the new root of the tree to [key].
+   * Returns -1 if the table is empty.
    */
-  void splay_(K key) {
-    if (isEmpty) return;
+  int _splay(K key) {
+    if (_root == null) return -1;
 
     // The right child of the dummy node will hold
     // the L tree of the algorithm.  The left child of the dummy node
@@ -62,11 +78,13 @@
     SplayTreeNode<K, V> left = _dummy;
     SplayTreeNode<K, V> right = _dummy;
     SplayTreeNode<K, V> current = _root;
+    int comp;
     while (true) {
-      int comp = key.compareTo(current.key);
-      if (comp < 0) {
+      comp = current.key.compareTo(key);
+      if (comp > 0) {
         if (current.left == null) break;
-        if (key.compareTo(current.left.key) < 0) {
+        comp = current.left.key.compareTo(key);
+        if (comp > 0) {
           // Rotate right.
           SplayTreeNode<K, V> tmp = current.left;
           current.left = tmp.right;
@@ -78,9 +96,10 @@
         right.left = current;
         right = current;
         current = current.left;
-      } else if (comp > 0) {
+      } else if (comp < 0) {
         if (current.right == null) break;
-        if (key.compareTo(current.right.key) > 0) {
+        comp = current.right.key.compareTo(key);
+        if (comp < 0) {
           // Rotate left.
           SplayTreeNode<K, V> tmp = current.right;
           current.right = tmp.left;
@@ -105,20 +124,22 @@
 
     _dummy.right = null;
     _dummy.left = null;
+    _splayCount++;
+    return comp;
   }
 
   V operator [](K key) {
-    if (!isEmpty) {
-      splay_(key);
-      if (_root.key.compareTo(key) == 0) return _root.value;
+    if (_root != null) {
+      int comp = _splay(key);
+      if (comp == 0) return _root.value;
     }
     return null;
   }
 
   V remove(K key) {
-    if (isEmpty) return null;
-    splay_(key);
-    if (_root.key.compareTo(key) != 0) return null;
+    if (_root == null) return null;
+    int comp = _splay(key);
+    if (comp != 0) return null;
     V value = _root.value;
 
     _count--;
@@ -129,31 +150,43 @@
       SplayTreeNode<K, V> right = _root.right;
       _root = _root.left;
       // Splay to make sure that the new root has an empty right child.
-      splay_(key);
+      _splay(key);
       // Insert the original right child as the right child of the new
       // root.
       _root.right = right;
     }
+    _modificationCount++;
     return value;
   }
 
   void operator []=(K key, V value) {
-    if (isEmpty) {
+    if (_root == null) {
       _count++;
       _root = new SplayTreeNode(key, value);
+      _modificationCount++;
       return;
     }
     // Splay on the key to move the last node on the search path for
     // the key to the root of the tree.
-    splay_(key);
-    if (_root.key.compareTo(key) == 0) {
+    int comp = _splay(key);
+    if (comp == 0) {
       _root.value = value;
       return;
     }
+    _addNewRoot(key, value, comp);
+  }
+
+  /**
+   * Adds a new root node with the given [key] or [value].
+   *
+   * The [comp] value is the result of comparing the existing root's key
+   * with key.
+   */
+  void _addNewRoot(K key, V value, int comp) {
     SplayTreeNode<K, V> node = new SplayTreeNode(key, value);
     // assert(_count >= 0);
     _count++;
-    if (key.compareTo(_root.key) > 0) {
+    if (comp < 0) {
       node.left = _root;
       node.right = _root.right;
       _root.right = null;
@@ -163,12 +196,34 @@
       _root.left = null;
     }
     _root = node;
+    _modificationCount++;
   }
 
   V putIfAbsent(K key, V ifAbsent()) {
-    if (containsKey(key)) return this[key];
+    if (_root == null) {
+      V value = ifAbsent();
+      if (_root != null) {
+        throw new ConcurrentModificationError(this);
+      }
+      _root = new SplayTreeNode(key, value);
+      _count++;
+      _modificationCount++;
+      return value;
+    }
+    int comp = _splay(key);
+    if (comp == 0) return _root.value;
+    int modificationCount = _modificationCount;
+    int splayCount = _splayCount;
     V value = ifAbsent();
-    this[key] = value;
+    if (modificationCount != _modificationCount) {
+      throw new ConcurrentModificationError(this);
+    }
+    if (splayCount != _splayCount) {
+      comp = _splay(key);
+      // Key is still not there, otherwise _modificationCount would be changed.
+      assert(comp != 0);
+    }
+    _addNewRoot(key, value, comp);
     return value;
   }
 
@@ -179,21 +234,11 @@
   }
 
   void forEach(void f(K key, V value)) {
-    List<SplayTreeNode<K, V>> list = new List<SplayTreeNode<K, V>>();
-    SplayTreeNode<K, V> current = _root;
-    while (current != null) {
-      if (current.left != null) {
-        list.add(current);
-        current = current.left;
-      } else {
-        f(current.key, current.value);
-        while (current.right == null) {
-          if (list.isEmpty) return;
-          current = list.removeLast();
-          f(current.key, current.value);
-        }
-        current = current.right;
-      }
+    Iterator<SplayTreeNode<K, V>> nodes =
+        new _SplayTreeNodeIterator<K, V>(this);
+    while (nodes.moveNext()) {
+      SplayTreeNode<K, V> node = nodes.current;
+      f(node.key, node.value);
     }
   }
 
@@ -207,11 +252,7 @@
   }
 
   bool containsKey(K key) {
-    if (!isEmpty) {
-      splay_(key);
-      if (_root.key.compareTo(key) == 0) return true;
-    }
-    return false;
+    return _splay(key) == 0;
   }
 
   bool containsValue(V value) {
@@ -219,22 +260,16 @@
     bool visit(SplayTreeNode node) {
       if (node == null) return false;
       if (node.value == value) return true;
+      // TODO(lrn): Do we want to handle the case where node.value.operator==
+      // modifies the map?
       return visit(node.left) || visit(node.right);
     }
     return visit(_root);
   }
 
-  Collection<K> get keys {
-    List<K> list = new List<K>();
-    forEach((K k, V v) { list.add(k); });
-    return list;
-  }
+  Iterable<K> get keys => new _SplayTreeKeyIterable(this);
 
-  Collection<V> get values {
-    List<V> list = new List<V>();
-    forEach((K k, V v) { list.add(v); });
-    return list;
-  }
+  Iterable<V> get values => new _SplayTreeValueIterable(this);
 
   String toString() {
     return Maps.mapToString(this);
@@ -251,7 +286,7 @@
     }
     // Maybe implement a splay-method that can splay the minimum without
     // performing comparisons.
-    splay_(node.key);
+    _splay(node.key);
     return node.key;
   }
 
@@ -266,7 +301,7 @@
     }
     // Maybe implement a splay-method that can splay the maximum without
     // performing comparisons.
-    splay_(node.key);
+    _splay(node.key);
     return node.key;
   }
 
@@ -275,17 +310,15 @@
    * [null] if no key was not found.
    */
   K lastKeyBefore(K key) {
-    splay_(key);
-    K visit(SplayTreeNode node, K ifEmpty) {
-      if (node == null) return ifEmpty;
-      if (node.key.compareTo(key) >= 0) {
-        return visit(node.left, ifEmpty);
-      }
-      if (node.key.compareTo(key) < 0) {
-        return visit(node.right, node.key);
-      }
+    if (_root == null) return null;
+    int comp = _splay(key);
+    if (comp < 0) return _root.key;
+    SplayTreeNode<K, V> node = _root.left;
+    if (node == null) return null;
+    while (node.right != null) {
+      node = node.right;
     }
-    return visit(_root, null);
+    return node.key;
   }
 
   /**
@@ -293,16 +326,138 @@
    * [null] if no key was not found.
    */
   K firstKeyAfter(K key) {
-    splay_(key);
-    K visit(SplayTreeNode node, K ifEmpty) {
-      if (node == null) return ifEmpty;
-      if (node.key.compareTo(key) > 0) {
-        return visit(node.left, node.key);
-      }
-      if (node.key.compareTo(key) <= 0) {
-        return visit(node.right, ifEmpty);
-      }
+    if (_root == null) return null;
+    int comp = _splay(key);
+    if (comp > 0) return _root.key;
+    SplayTreeNode<K, V> node = _root.right;
+    if (node == null) return null;
+    while (node.left != null) {
+      node = node.left;
     }
-    return visit(_root, null);
+    return node.key;
   }
 }
+
+abstract class _SplayTreeIterator<T> implements Iterator<T> {
+  final SplayTreeMap _map;
+  /**
+   * Worklist of nodes to visit.
+   *
+   * These nodes have been passed over on the way down in a
+   * depth-first left-to-right traversal. Visiting each node,
+   * and their right subtrees will visit the remainder of
+   * the nodes of a full traversal.
+   *
+   * Only valid as long as the original tree map isn't reordered.
+   */
+  final List<SplayTreeNode> _workList = <SplayTreeNode>[];
+
+  /**
+   * Original modification counter of [_map].
+   *
+   * Incremented on [_map] when a key is added or removed.
+   * If it changes, iteration is aborted.
+   */
+  final int _modificationCount;
+
+  /**
+   * Count of splay operations on [_map] when [_workList] was built.
+   *
+   * If the splay count on [_map] increases, [_workList] becomes invalid.
+   */
+  int _splayCount;
+
+  /** Current node. */
+  SplayTreeNode _currentNode;
+
+  _SplayTreeIterator(SplayTreeMap map)
+      : _map = map,
+        _modificationCount = map._modificationCount,
+        _splayCount = map._splayCount {
+    _findLeftMostDescendent(map._root);
+  }
+
+  T get current {
+    if (_currentNode == null) return null;
+    return _getValue(_currentNode);
+  }
+
+  void _findLeftMostDescendent(SplayTreeNode node) {
+    while (node != null) {
+      _workList.add(node);
+      node = node.left;
+    }
+  }
+
+  /**
+   * Called when the tree structure of the map has changed.
+   *
+   * This can be caused by a splay operation.
+   * If the key-set changes, iteration is aborted before getting
+   * here, so we know that the keys are the same as before, it's
+   * only the tree that has been reordered.
+   */
+  void _rebuildWorkList(SplayTreeNode currentNode) {
+    assert(!_workList.isEmpty);
+    _workList.clear();
+    if (currentNode == null) {
+      _findLeftMostDescendent(_map._root);
+    } else {
+      _map._splay(currentNode.key);
+      _findLeftMostDescendent(_map._root.right);
+      assert(!_workList.isEmpty);
+    }
+  }
+
+  bool moveNext() {
+    if (_modificationCount != _map._modificationCount) {
+      throw new ConcurrentModificationError(_map);
+    }
+    // Picks the next element in the worklist as current.
+    // Updates the worklist with the left-most path of the current node's
+    // right-hand child.
+    // If the worklist is no longer valid (after a splay), it is rebuild
+    // from scratch.
+    if (_workList.isEmpty) {
+      _currentNode = null;
+      return false;
+    }
+    if (_map._splayCount != _splayCount) {
+      _rebuildWorkList(_currentNode);
+    }
+    _currentNode = _workList.removeLast();
+    _findLeftMostDescendent(_currentNode.right);
+    return true;
+  }
+
+  T _getValue(SplayTreeNode node);
+}
+
+
+class _SplayTreeKeyIterable<K, V> extends Iterable<K> {
+  SplayTreeMap<K, V> _map;
+  _SplayTreeKeyIterable(this._map);
+  Iterator<K> get iterator => new _SplayTreeKeyIterator<K, V>(_map);
+}
+
+class _SplayTreeValueIterable<K, V> extends Iterable<V> {
+  SplayTreeMap<K, V> _map;
+  _SplayTreeValueIterable(this._map) ;
+  Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map);
+}
+
+class _SplayTreeKeyIterator<K, V> extends _SplayTreeIterator<K> {
+  _SplayTreeKeyIterator(SplayTreeMap<K, V> map): super(map);
+  K _getValue(SplayTreeNode node) => node.key;
+}
+
+class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> {
+  _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map);
+  V _getValue(SplayTreeNode node) => node.value;
+}
+
+class _SplayTreeNodeIterator<K, V>
+    extends _SplayTreeIterator<SplayTreeNode<K, V>> {
+  _SplayTreeNodeIterator(SplayTreeMap<K, V> map): super(map);
+  SplayTreeNode<K, V> _getValue(SplayTreeNode node) => node;
+}
diff --git a/sdk/lib/core/map.dart b/sdk/lib/core/map.dart
index 8b27b3e..de3807f 100644
--- a/sdk/lib/core/map.dart
+++ b/sdk/lib/core/map.dart
@@ -47,6 +47,9 @@
    * If [key] is not associated to a value, calls [ifAbsent] and
    * updates the map by mapping [key] to the value returned by
    * [ifAbsent]. Returns the value in the map.
+   *
+   * It is an error to add or remove keys from map during the call to
+   * [ifAbsent].
    */
   V putIfAbsent(K key, V ifAbsent());
 
@@ -65,6 +68,8 @@
 
   /**
    * Applies [f] to each {key, value} pair of the map.
+   *
+   * It is an error to add or remove keys from the map during iteration.
    */
   void forEach(void f(K key, V value));
 
diff --git a/sdk/lib/io/http_impl.dart b/sdk/lib/io/http_impl.dart
index 224c1e7..70c6c53 100644
--- a/sdk/lib/io/http_impl.dart
+++ b/sdk/lib/io/http_impl.dart
@@ -1917,14 +1917,15 @@
 
   void shutdown({bool force: false}) {
     if (force) _closeQueue.shutdown();
-    _openSockets.forEach((String key, Queue<_SocketConnection> connections) {
+    new Map.from(_openSockets).forEach(
+        (String key, Queue<_SocketConnection> connections) {
       while (!connections.isEmpty) {
         _SocketConnection socketConn = connections.removeFirst();
         socketConn._socket.close();
       }
     });
     if (force) {
-      _activeSockets.forEach((_SocketConnection socketConn) {
+      _activeSockets.toList().forEach((_SocketConnection socketConn) {
         socketConn._httpClientConnection._onClientShutdown();
         socketConn._close();
       });
diff --git a/tests/co19/co19-dart2dart.status b/tests/co19/co19-dart2dart.status
index 21a8cce..fc61890 100644
--- a/tests/co19/co19-dart2dart.status
+++ b/tests/co19/co19-dart2dart.status
@@ -657,3 +657,20 @@
 LibTest/core/Queue/removeLast_A02_t01: Fail # Moved collection classes from core to collection. co19 issue 371.
 LibTest/core/Set/Set.from_A01_t01: Fail # Moved collection classes from core to collection. co19 issue 371.
 Language/14_Types/4_Interface_Types_A08_t06: Fail # Moved collection classes from core to collection. co19 issue 371.
+
+# Doesn't expect null to be allowed in Set or Map keys (issue 377).
+LibTest/core/Map/containsKey_A01_t02: Fail
+LibTest/core/Map/operator_subscript_A01_t02: Fail
+LibTest/core/Map/operator_subscripted_assignment_A01_t02: Fail
+LibTest/core/Map/remove_A01_t02: Fail
+LibTest/core/Set/add_A01_t02: Fail
+LibTest/core/Set/addAll_A01_t02: Fail
+LibTest/core/Set/contains_A01_t02: Fail
+LibTest/core/Set/containsAll_A01_t02: Fail
+LibTest/core/Set/intersection_A03_t01: Fail
+LibTest/core/Set/isSubsetOf_A01_t02: Fail
+LibTest/core/Set/remove_A01_t02: Fail
+LibTest/core/Set/removeAll_A01_t02: Fail
+
+# Doesn't expect concurrent modification error (issue 376).
+LibTest/core/Map/forEach_A01_t07: Fail
diff --git a/tests/co19/co19-dart2js.status b/tests/co19/co19-dart2js.status
index a54182d..8da7c21 100644
--- a/tests/co19/co19-dart2js.status
+++ b/tests/co19/co19-dart2js.status
@@ -787,3 +787,20 @@
 Language/14_Types/5_Function_Types_A03_t06: Fail # dartbug.com/7342
 Language/14_Types/5_Function_Types_A03_t10: Fail # dartbug.com/7342
 Language/14_Types/5_Function_Types_A03_t11: Fail # dartbug.com/7342
+
+# Doesn't expect null to be allowed in Set or Map keys (issue 377).
+LibTest/core/Map/containsKey_A01_t02: Fail
+LibTest/core/Map/operator_subscript_A01_t02: Fail
+LibTest/core/Map/operator_subscripted_assignment_A01_t02: Fail
+LibTest/core/Map/remove_A01_t02: Fail
+LibTest/core/Set/add_A01_t02: Fail
+LibTest/core/Set/addAll_A01_t02: Fail
+LibTest/core/Set/contains_A01_t02: Fail
+LibTest/core/Set/containsAll_A01_t02: Fail
+LibTest/core/Set/intersection_A03_t01: Fail
+LibTest/core/Set/isSubsetOf_A01_t02: Fail
+LibTest/core/Set/remove_A01_t02: Fail
+LibTest/core/Set/removeAll_A01_t02: Fail
+
+# Doesn't expect concurrent modification error (issue 376).
+LibTest/core/Map/forEach_A01_t07: Fail
diff --git a/tests/co19/co19-runtime.status b/tests/co19/co19-runtime.status
index 09f39d0..6a312f5 100644
--- a/tests/co19/co19-runtime.status
+++ b/tests/co19/co19-runtime.status
@@ -504,6 +504,23 @@
 LibTest/core/Queue/removeLast_A02_t01: Fail # Moved collection classes from core to collection. co19 issue 371.
 LibTest/core/Set/Set.from_A01_t01: Fail # Moved collection classes from core to collection. co19 issue 371.
 
+# Doesn't expect null to be allowed in Set or Map keys (issue 377).
+LibTest/core/Map/containsKey_A01_t02: Fail
+LibTest/core/Map/operator_subscript_A01_t02: Fail
+LibTest/core/Map/operator_subscripted_assignment_A01_t02: Fail
+LibTest/core/Map/remove_A01_t02: Fail
+LibTest/core/Set/add_A01_t02: Fail
+LibTest/core/Set/addAll_A01_t02: Fail
+LibTest/core/Set/contains_A01_t02: Fail
+LibTest/core/Set/containsAll_A01_t02: Fail
+LibTest/core/Set/intersection_A03_t01: Fail
+LibTest/core/Set/isSubsetOf_A01_t02: Fail
+LibTest/core/Set/remove_A01_t02: Fail
+LibTest/core/Set/removeAll_A01_t02: Fail
+
+# Doesn't expect concurrent modification error (issue 376).
+LibTest/core/Map/forEach_A01_t07: Fail
+
 [ $compiler == none && $runtime == vm && $unchecked ]
 LibTest/core/Future/chain_A02_t05: Fail # Future is in async library. co19 issue 367
 LibTest/core/Future/transform_A02_t04: Fail # Future is in async library. co19 issue 367
diff --git a/tests/corelib/hash_map2_test.dart b/tests/corelib/hash_map2_test.dart
new file mode 100644
index 0000000..9f81c9f
--- /dev/null
+++ b/tests/corelib/hash_map2_test.dart
@@ -0,0 +1,289 @@
+// Copyright (c) 2013, 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.
+
+// Tests of hash map behavior, with focus in iteration and concurrent
+// modification errors.
+
+library hash_map2_test;
+import 'dart:collection';
+
+testMap(Map newMap(), Map newMapFrom(Map map)) {
+  Map gen(int from, int to) {
+    Map map = new LinkedHashMap();
+    for (int i = from; i < to; i++) map[i] = i;
+    return map;
+  }
+
+  bool odd(int n) => (n & 1) == 1;
+  bool even(int n) => (n & 1) == 0;
+  void addAll(Map toMap, Map fromMap) {
+    fromMap.forEach((k, v) { toMap[k] = v; });
+  }
+
+  {  // Test growing to largish capacity.
+    Map map = newMap();
+
+    for (int i = 0; i < 256; i++) {
+      map[i] = i;
+    }
+    addAll(map, gen(256, 512));
+    addAll(map, newMapFrom(gen(512, 1000)));
+    Expect.equals(1000, map.length);
+
+    // Remove half.
+    for (int i = 0; i < 1000; i += 2) map.remove(i);
+    Expect.equals(500, map.length);
+    Expect.isFalse(map.keys.any(even));
+    Expect.isTrue(map.keys.every(odd));
+
+    // Re-add all.
+    addAll(map, gen(0, 1000));
+    Expect.equals(1000, map.length);
+  }
+
+  {  // Test having many deleted elements.
+    Map map = newMap();
+    map[0] = 0;
+    for (int i = 0; i < 1000; i++) {
+      map[i + 1] = i + 1;
+      map.remove(i);
+      Expect.equals(1, map.length);
+    }
+  }
+
+  {  // Test having many elements with same hashCode
+    Map map = newMap();
+    for (int i = 0; i < 1000; i++) {
+      map[new BadHashCode()] = 0;
+    }
+    Expect.equals(1000, map.length);
+  }
+
+  {  // Check concurrent modification
+    Map map = newMap()..[0] = 0..[1] = 1;
+
+    {  // Test adding before a moveNext.
+      Iterator iter = map.keys.iterator;
+      iter.moveNext();
+      map[1] = 9;  // Updating existing key isn't a modification.
+      iter.moveNext();
+      map[2] = 2;
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test adding after last element.
+      Iterator iter = map.keys.iterator;
+      Expect.equals(3, map.length);
+      iter.moveNext();
+      iter.moveNext();
+      iter.moveNext();
+      map[3] = 3;
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test removing during iteration.
+      Iterator iter = map.keys.iterator;
+      iter.moveNext();
+      map.remove(1000);  // Not a modification if it's not there.
+      iter.moveNext();
+      int n = iter.current;
+      map.remove(n);
+      // Removing doesn't change current.
+      Expect.equals(n, iter.current);
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test removing after last element.
+      Iterator iter = map.keys.iterator;
+      Expect.equals(3, map.length);
+      iter.moveNext();
+      iter.moveNext();
+      iter.moveNext();
+      int n = iter.current;
+      map.remove(n);
+      // Removing doesn't change current.
+      Expect.equals(n, iter.current);
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test that updating value of existing key doesn't cause concurrent
+       // modification error.
+      Iterator iter = map.keys.iterator;
+      Expect.equals(2, map.length);
+      iter.moveNext();
+      int n = iter.current;
+      map[n] = n * 2;
+      iter.moveNext();
+      Expect.equals(map[iter.current], iter.current);
+    }
+
+    {  // Test that modification during putIfAbsent is not an error.
+      map.putIfAbsent(4, () {
+        map[5] = 5;
+        map[4] = -1;
+        return 4;
+      });
+      Expect.equals(4, map[4]);
+      Expect.equals(5, map[5]);
+    }
+
+    {  // Check adding many existing keys isn't considered modification.
+      Map map2 = newMap();
+      for (var key in map.keys) {
+        map2[key] = map[key] + 1;
+      }
+      Iterator iter = map.keys.iterator;
+      addAll(map, map2);
+      // Shouldn't throw.
+      iter.moveNext();
+    }
+  }
+
+  {  // Regression test for bug in putIfAbsent where adding an element
+     // that make the table grow, can be lost.
+    Map map = newMap();
+    map.putIfAbsent("S", () => 0);
+    map.putIfAbsent("T", () => 0);
+    map.putIfAbsent("U", () => 0);
+    map.putIfAbsent("C", () => 0);
+    map.putIfAbsent("a", () => 0);
+    map.putIfAbsent("b", () => 0);
+    map.putIfAbsent("n", () => 0);
+    Expect.isTrue(map.containsKey("n"));
+  }
+
+  {  // Check that putIfAbsent works just as well as put.
+    Map map = newMap();
+    for (int i = 0; i < 128; i++) {
+      map.putIfAbsent(i, () => i);
+      Expect.isTrue(map.containsKey(i));
+      map.putIfAbsent(i >> 1, () => -1);  // Never triggers.
+    }
+    for (int i = 0; i < 128; i++) {
+      Expect.equals(i, map[i]);
+    }
+  }
+
+  {  // Check that updating existing elements is not a modification.
+     // This must be the case even if the underlying data structure is
+     // nearly full.
+     for (int i = 1; i < 128; i++) {
+        // Create maps of different sizes, some of which should be
+        // at a limit of the underlying data structure.
+        Map map = newMapFrom(gen(0, i));
+
+        // ForEach-iteration.
+        map.forEach((key, v) {
+          Expect.equals(key, map[key]);
+          map[key] = key + 1;
+          map.remove(1000);  // Removing something not there.
+          map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));
+          // Doesn't cause ConcurrentModificationError.
+        });
+
+        // for-in iteration.
+        for (int key in map.keys) {
+          Expect.equals(key + 1, map[key]);
+          map[key] = map[key] + 1;
+          map.remove(1000);  // Removing something not there.
+          map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));
+          // Doesn't cause ConcurrentModificationError.
+        }
+
+        // Raw iterator.
+        Iterator iter = map.keys.iterator;
+        for (int key = 0; key < i; key++) {
+          Expect.equals(key + 2, map[key]);
+          map[key] = key + 3;
+          map.remove(1000);  // Removing something not there.
+          map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT"));
+          // Doesn't cause ConcurrentModificationError on the moveNext.
+        }
+        iter.moveNext();  // Should not throw.
+
+        // Remove a lot of elements, which can cause a re-tabulation.
+        for (int key = 1; key < i; key++) {
+          Expect.equals(key + 3, map[key]);
+          map.remove(key);
+        }
+        iter = map.keys.iterator;
+        map[0] = 2;
+        iter.moveNext();  // Should not throw.
+     }
+  }
+
+
+  {  // Check that null can be in the map.
+    Map map = newMap();
+    map[null] = 0;
+    Expect.equals(1, map.length);
+    Expect.isTrue(map.containsKey(null));
+    Expect.isNull(map.keys.first);
+    Expect.isNull(map.keys.last);
+    map[null] = 1;
+    Expect.equals(1, map.length);
+    Expect.isTrue(map.containsKey(null));
+    map.remove(null);
+    Expect.isTrue(map.isEmpty);
+    Expect.isFalse(map.containsKey(null));
+
+    // Created using map.from.
+    map = newMapFrom(new Map()..[null] = 0);
+    Expect.equals(1, map.length);
+    Expect.isTrue(map.containsKey(null));
+    Expect.isNull(map.keys.first);
+    Expect.isNull(map.keys.last);
+    map[null] = 1;
+    Expect.equals(1, map.length);
+    Expect.isTrue(map.containsKey(null));
+    map.remove(null);
+    Expect.isTrue(map.isEmpty);
+    Expect.isFalse(map.containsKey(null));
+
+    Map fromMap = new Map();
+    fromMap[1] = 0;
+    fromMap[2] = 0;
+    fromMap[3] = 0;
+    fromMap[null] = 0;
+    fromMap[4] = 0;
+    fromMap[5] = 0;
+    fromMap[6] = 0;
+    Expect.equals(7, fromMap.length);
+
+    // map that grows with null in it.
+    map = newMapFrom(fromMap);
+    Expect.equals(7, map.length);
+    for (int i = 7; i < 128; i++) {
+      map[i] = 0;
+    }
+    Expect.equals(128, map.length);
+    Expect.isTrue(map.containsKey(null));
+    map[null] = 1;
+    Expect.equals(128, map.length);
+    Expect.isTrue(map.containsKey(null));
+    map.remove(null);
+    Expect.equals(127, map.length);
+    Expect.isFalse(map.containsKey(null));
+  }
+}
+
+void main() {
+  Expect.isTrue(new HashMap<int, String>() is Map<int, String>);
+  Expect.isTrue(new LinkedHashMap<int, String>() is Map<int, String>);
+  Expect.isTrue(new HashMap<String, int>.from({}) is Map<String, int>);
+  Expect.isTrue(new LinkedHashMap<String, int>.from({}) is Map<String, int>);
+  Expect.isTrue(<String, int>{} is Map<String, int>);
+  Expect.isTrue(const <String, int>{} is Map<String, int>);
+
+  testMap(() => new HashMap(), (m) => new HashMap.from(m));
+  testMap(() => new LinkedHashMap(), (m) => new LinkedHashMap.from(m));
+}
+
+
+class BadHashCode {
+  static int idCounter = 0;
+  final int id;
+  BadHashCode() : id = idCounter++;
+  int get hashCode => 42;
+}
diff --git a/tests/corelib/hash_set_test.dart b/tests/corelib/hash_set_test.dart
new file mode 100644
index 0000000..68a0844
--- /dev/null
+++ b/tests/corelib/hash_set_test.dart
@@ -0,0 +1,206 @@
+// Copyright (c) 2013, 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.
+
+// Tests of hash set behavior, with focus in iteration and concurrent
+// modification errors.
+
+library hash_map2_test;
+import 'dart:collection';
+
+testSet(Set newSet(), Set newSetFrom(Set from)) {
+  Set gen(int from, int to) =>
+      new Set.from(new Iterable.generate(to - from, (n) => n + from));
+
+  bool odd(int n) => (n & 1) == 1;
+  bool even(int n) => (n & 1) == 0;
+
+  {  // Test growing to largish capacity.
+    Set set = newSet();
+
+    for (int i = 0; i < 256; i++) {
+      set.add(i);
+    }
+    set.addAll(gen(256, 512));
+    set.addAll(newSetFrom(gen(512, 1000)));
+    Expect.equals(1000, set.length);
+
+    // Remove half.
+    for (int i = 0; i < 1000; i += 2) set.remove(i);
+    Expect.equals(500, set.length);
+    Expect.isFalse(set.any(even));
+    Expect.isTrue(set.every(odd));
+
+    // Re-add all.
+    set.addAll(gen(0, 1000));
+    Expect.equals(1000, set.length);
+  }
+
+  {  // Test having many deleted elements.
+    Set set = newSet();
+    set.add(0);
+    for (int i = 0; i < 1000; i++) {
+      set.add(i + 1);
+      set.remove(i);
+      Expect.equals(1, set.length);
+    }
+  }
+
+  {  // Test having many elements with same hashCode
+    Set set = newSet();
+    for (int i = 0; i < 1000; i++) {
+      set.add(new BadHashCode());
+    }
+    Expect.equals(1000, set.length);
+  }
+
+  {  // Check concurrent modification
+    Set set = newSet()..add(0)..add(1);
+
+    {  // Test adding before a moveNext.
+      Iterator iter = set.iterator;
+      iter.moveNext();
+      set.add(1);  // Updating existing key isn't a modification.
+      iter.moveNext();
+      set.add(2);
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test adding after last element.
+      Iterator iter = set.iterator;
+      Expect.equals(3, set.length);
+      iter.moveNext();
+      iter.moveNext();
+      iter.moveNext();
+      set.add(3);
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test removing during iteration.
+      Iterator iter = set.iterator;
+      iter.moveNext();
+      set.remove(1000);  // Not a modification if it's not there.
+      iter.moveNext();
+      int n = iter.current;
+      set.remove(n);
+      // Removing doesn't change current.
+      Expect.equals(n, iter.current);
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test removing after last element.
+      Iterator iter = set.iterator;
+      Expect.equals(3, set.length);
+      iter.moveNext();
+      iter.moveNext();
+      iter.moveNext();
+      int n = iter.current;
+      set.remove(n);
+      // Removing doesn't change current.
+      Expect.equals(n, iter.current);
+      Expect.throws(iter.moveNext, (e) => e is Error);
+    }
+
+    {  // Test that updating value doesn't cause error.
+      Iterator iter = set.iterator;
+      Expect.equals(2, set.length);
+      iter.moveNext();
+      int n = iter.current;
+      set.add(n);
+      iter.moveNext();
+      Expect.isTrue(set.contains(iter.current));
+    }
+
+    {  // Check adding many existing values isn't considered modification.
+      Set set2 = newSet();
+      for (var value in set) {
+        set2.add(value);
+      }
+      Iterator iter = set.iterator;
+      set.addAll(set2);
+      // Shouldn't throw.
+      iter.moveNext();
+    }
+  }
+
+  {  // Check that updating existing elements is not a modification.
+     // This must be the case even if the underlying data structure is
+     // nearly full.
+     for (int i = 1; i < 128; i++) {
+        // Create maps of different sizes, some of which should be
+        // at a limit of the underlying data structure.
+        Set set = newSetFrom(gen(0, i));
+        Iterator iter = set.iterator;
+        for (int j = 0; j < i; j++) {
+          set.add(j);
+        }
+        iter.moveNext();  // Should not throw.
+
+        for (int j = 1; j < i; j++) {
+          set.remove(j);
+        }
+        iter = set.iterator;
+        set.add(0);
+        iter.moveNext();  // Should not throw.
+     }
+  }
+
+  {  // Check that null can be in the set.
+    Set set = newSet();
+    set.add(null);
+    Expect.equals(1, set.length);
+    Expect.isTrue(set.contains(null));
+    Expect.isNull(set.first);
+    Expect.isNull(set.last);
+    set.add(null);
+    Expect.equals(1, set.length);
+    Expect.isTrue(set.contains(null));
+    set.remove(null);
+    Expect.isTrue(set.isEmpty);
+    Expect.isFalse(set.contains(null));
+
+    // Created using Set.from.
+    set = newSetFrom([null]);
+    Expect.equals(1, set.length);
+    Expect.isTrue(set.contains(null));
+    Expect.isNull(set.first);
+    Expect.isNull(set.last);
+    set.add(null);
+    Expect.equals(1, set.length);
+    Expect.isTrue(set.contains(null));
+    set.remove(null);
+    Expect.isTrue(set.isEmpty);
+    Expect.isFalse(set.contains(null));
+
+    // Set that grows with null in it.
+    set = newSetFrom([1, 2, 3, null, 4, 5, 6]);
+    Expect.equals(7, set.length);
+    for (int i = 7; i < 128; i++) {
+      set.add(i);
+    }
+    Expect.equals(128, set.length);
+    Expect.isTrue(set.contains(null));
+    set.add(null);
+    Expect.equals(128, set.length);
+    Expect.isTrue(set.contains(null));
+    set.remove(null);
+    Expect.equals(127, set.length);
+    Expect.isFalse(set.contains(null));
+  }
+}
+
+void main() {
+  testSet(() => new HashSet(), (m) => new HashSet.from(m));
+  testSet(() => new LinkedHashSet(), (m) => new LinkedHashSet.from(m));
+}
+
+
+class BadHashCode {
+  static int idCounter = 0;
+  final int id;
+  BadHashCode() : id = idCounter++;
+  int get hashCode => 42;
+  // operator == is identity.
+  // Can't make a bad compareTo that isn't invalid.
+  int compareTo(BadHashCode other) => id - other.id;
+}
diff --git a/tests/corelib/map_from_test.dart b/tests/corelib/map_from_test.dart
index bc47e9d..b43a45d 100644
--- a/tests/corelib/map_from_test.dart
+++ b/tests/corelib/map_from_test.dart
@@ -71,7 +71,7 @@
   var map = const { 'b': 1, 'a': 2, 'c': 3 };
   var otherMap = new LinkedHashMap.from(map);
   Expect.isTrue(otherMap is Map);
-  Expect.isTrue(otherMap is HashMap);
+  Expect.isTrue(otherMap is! HashMap);
   Expect.isTrue(otherMap is LinkedHashMap);
   var i = 1;
   for (var val in map.values) {
diff --git a/tests/standalone/standalone.status b/tests/standalone/standalone.status
index 9652300..cbaa158 100644
--- a/tests/standalone/standalone.status
+++ b/tests/standalone/standalone.status
@@ -45,6 +45,7 @@
 
 [ $runtime == vm && $system == windows ]
 io/file_system_links_test: Skip  # No links on Windows.
+io/socket_stream_close_test: Fail, Pass # Issue 8556.
 
 [ $compiler == none && $runtime == drt ]
 io/*: Skip # Don't run tests using dart:io in the browser
diff --git a/tools/VERSION b/tools/VERSION
index 57771f2..8b85f04 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -1,4 +1,4 @@
 MAJOR 0
 MINOR 3
 BUILD 7
-PATCH 2
+PATCH 3
diff --git a/utils/pub/pub.dart b/utils/pub/pub.dart
index 569c63c..00abe4c 100644
--- a/utils/pub/pub.dart
+++ b/utils/pub/pub.dart
@@ -42,7 +42,7 @@
     'uploader': new UploaderCommand(),
     'version': new VersionCommand()
   };
-  for (var command in commands.values) {
+  for (var command in commands.values.toList()) {
     for (var alias in command.aliases) {
       commands[alias] = command;
     }