New implementation of {,Linked}Hash{Set,Map}.

sdk/lib/collection/hash_map.dart

Index: sdk/lib/collection/hash_map.dart
diff --git a/sdk/lib/collection/hash_map.dart b/sdk/lib/collection/hash_map.dart
new file mode 100644
index 0000000000000000000000000000000000000000..0f610f5fde04e230c3e52c8eb8fab949be9f7c3f
--- /dev/null
+++ b/sdk/lib/collection/hash_map.dart
@@ -0,0 +1,112 @@
+part of dart.collection;
+
+class HashMap<K, V> extends _HashTable<K> implements Map<K, V> {
+  static const int _INITIAL_CAPACITY = 8;
+  static const int _VALUE_INDEX = 1;
+
+  HashMap() : super(_INITIAL_CAPACITY);
+
+  factory HashMap.from(Map<K, V> other) {
+    return new HashMap<K, V>()..addAll(other);
+  }
+
+  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) {

[floitsch, 2013/02/06 10:43:58]

Add comment that this is just to be more efficient. The base function is good
enough.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Base function has been reduced to not copying anything extra.

+    _setValue(toOffset, fromTable[fromOffset + _VALUE_INDEX]);

[floitsch, 2013/02/06 10:43:58]

Don't use '_setValue' it makes it confusing.
_table[toOffset + VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX]

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Done.

+  }
+
+  bool containsKey(K key) {
+    return _get(key) >= 0;
+  }
+
+  bool containsValue(V value) {
+    for (int offset = 0; offset < _table.length; offset += _entrySize) {
+      if (!_isFree(_table[offset]) && _value(offset) == value) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  void addAll(Map<K, V> other) {
+    _ensureCapacity(other.length);
+    other.forEach((K key, V value) {
+      int offset = _put(key);
+      _setValue(offset, value);
+      _modificationCount++;

[erikcorry, 2013/02/05 16:25:05]

You probably want to mask this with something so it does not get too big.

[Lasse Reichstein Nielsen, 2013/02/05 19:47:40]

That could be wrong, if you keep an iterator alive until the counter overflows..
If you overflow a 31-bit smi by incrementing, you're asking for it.
That said, if you keep an iterator alive while doing that, you're definitely
asking for something too.

[floitsch, 2013/02/06 10:43:58]

It's 30 bits (1 for tagging, 1 for the sign). That could realistically happen
(add/remove -> 2 operations).
If you are having an iterator alive for all that time you are doing it on
purpose...
So I would prefer a 30-bit mask too.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Done.

+    });
+  }
+
+  V operator [](K key) {
+    int offset = _get(key);
+    if (offset >= 0) return _value(offset);
+    return null;
+  }
+
+  void operator []=(K key, V value) {
+    _ensureCapacity(1);
+    int offset = _put(key);
+    _setValue(offset, value);

[erikcorry, 2013/02/05 16:25:05]

Seems inconsistent that you don't increment the modification count here, when
you increment it in addAll

[Lasse Reichstein Nielsen, 2013/02/05 19:47:40]

The modification count is only for modifications that break iteration. Changing
the value associated to a key don't do that if the key exists already, and if it
doesn't exist, the count is incremented in _put.

But you are right that I shouldn't increment in addAll either.

[erikcorry, 2013/02/06 10:57:56]

You already called _ensureCapacity, which may have reordered all the elements,
but does not increment the counter, so it's a bad idea to rely on _setValue to
do it _only_ if a new key is introduced!

You need more tests.

[floitsch, 2013/02/06 11:45:46]

I would not make it dependent on the actual outcome. If you do an operation that
could change the map, the iterator should throw.
However. We should provide an "update" method that throws if the element doesn't
exist yet.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

I prefer to consider only operations that change the key-set of the map as
modifications. Iteration of a map is usually iteration of the key-set anyway
(Map itself is not Iterable).

[erikcorry, 2013/02/11 10:18:29]

If that is the contract with the user, then you need to make sure that it is
reliable.  At the moment if you set an entry using a key that was already there
you won't get a concurrent modification exception _unless_ the fullness of the
table was just below some limit, in which case the table will be expanded and
rebuilt and you will get the exception. 

[Lasse Reichstein Nielsen, 2013/02/11 14:07:37]

Gah! 
Ok. I think I can do something for non-linked sets so that growing won't cause
iteration to fail (basically; caching the table in the iterator). It will be
able to provide stale values then (but that's ok).

[erikcorry, 2013/02/11 14:42:05]

So if you update the values for preexisting keys while iterating do you get the
new values or the old values?  The answer would seem to depend on whether you
are close to the capacity limit.

[Lasse Reichstein Nielsen, 2013/02/12 10:34:47]

Yes, That's acceptable. You always get the elements that were in the table
during the entire iteration. Elements added or remove during iteration may or
may not be included as well, and they may be included after they were removed.

In any case, I didn't go for this solution, and instead checks for growing after
adding instead of before. Updating an existing key will not change the
parameters used to determine if it should grow, so it won't.

+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    _ensureCapacity(1);
+    int offset = _probeForAdd(_hashCodeOf(key), key);
+    Object prevKey = _key(offset);
+    if (_isFree(prevKey)) {
+      V value = ifAbsent();
+      _setKey(offset, key);
+      _setValue(offset, value);
+      if (prevKey == null) {
+        _entryCount++;
+      } else {
+        assert(identical(prevKey, _TOMBSTONE));
+        _deletedCount--;
+      }
+      _modificationCount++;
+      return value;
+    }
+    return _value(offset);
+  }
+
+  V remove(K key) {
+    int offset = _remove(key);
+    if (offset < 0) return null;
+    V oldValue = _value(offset);
+    _setValue(offset, null);
+    return oldValue;
+  }
+
+  void clear() {
+    _clear();
+  }
+
+  void forEach(void action (K key, V value)) {
+    int modCount = _modificationCount;
+    for (int offset = 0; offset < _table.length; offset += 2) {

[erikcorry, 2013/02/05 16:25:05]

+= _entrySize?

[Lasse Reichstein Nielsen, 2013/02/05 19:47:40]

Yes, it's probably more readable, even if we know it's 2 here.

+      if (modCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      Object entry = _key(offset);
+      if (!_isFree(entry)) {
+        K key = entry;
+        V value = _value(offset);
+        action(key, value);
+      }
+    }
+  }
+
+  Iterable<K> get keys => new _HashTableKeyIterable<K>(this);
+  Iterable<V> get values =>
+      new _HashTableValueIterable<V>(this, _VALUE_INDEX);
+
+  int get length => _elementCount;
+
+  bool get isEmpty => _elementCount == 0;
+
+  String toString() => Maps.mapToString(this);
+}