OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 // Hash map implementation with open addressing and quadratic probing. | 5 // Hash map implementation with open addressing and quadratic probing. |
6 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> { | 6 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> { |
7 | 7 |
8 // The [keys_] list contains the keys inserted in the map. | 8 // The [_keys] list contains the keys inserted in the map. |
9 // The [keys_] list must be a raw list because it | 9 // The [_keys] list must be a raw list because it |
10 // will contain both elements of type K, and the [deletedKey_] of type | 10 // will contain both elements of type K, and the [_deletedKey] of type |
11 // Object. | 11 // Object. |
12 // The alternative of declaring the [keys_] list as of type Object | 12 // The alternative of declaring the [_keys] list as of type Object |
13 // does not work, because the HashSetIterator constructor would fail: | 13 // does not work, because the HashSetIterator constructor would fail: |
14 // HashSetIterator(HashSet<E> set_) | 14 // HashSetIterator(HashSet<E> set) |
15 // : _nextValidIndex = -1, | 15 // : _nextValidIndex = -1, |
16 // _entries = set_._backingMap._keys { | 16 // _entries = set_._backingMap._keys { |
17 // _advance(); | 17 // _advance(); |
18 // } | 18 // } |
19 // With K being type int, for example, it would fail because | 19 // With K being type int, for example, it would fail because |
20 // ObjectArray<Object> is not assignable to type List<int> of entries_. | 20 // List<Object> is not assignable to type List<int> of entries. |
21 List _keys; | 21 List _keys; |
22 | 22 |
23 // The values_ inserted in the map. For a filled entry index in this | 23 // The values inserted in the map. For a filled entry index in this |
24 // list, there is always the corresponding key in the [keys_] list | 24 // list, there is always the corresponding key in the [keys_] list |
25 // at the same entry index. | 25 // at the same entry index. |
26 List<V> _values; | 26 List<V> _values; |
27 | 27 |
28 // The load limit is the number of entries we allow until we double | 28 // The load limit is the number of entries we allow until we double |
29 // the size of the lists. | 29 // the size of the lists. |
30 int _loadLimit; | 30 int _loadLimit; |
31 | 31 |
32 // The current number of entries in the map. Will never be greater | 32 // The current number of entries in the map. Will never be greater |
33 // than [_loadLimit]. | 33 // than [_loadLimit]. |
(...skipping 383 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
417 } | 417 } |
418 | 418 |
419 // The entries in the set. May contain null or the sentinel value. | 419 // The entries in the set. May contain null or the sentinel value. |
420 List<E> _entries; | 420 List<E> _entries; |
421 | 421 |
422 // The next valid index in [_entries] or the length of [entries_]. | 422 // The next valid index in [_entries] or the length of [entries_]. |
423 // If it is the length of [_entries], calling [hasNext] on the | 423 // If it is the length of [_entries], calling [hasNext] on the |
424 // iterator will return false. | 424 // iterator will return false. |
425 int _nextValidIndex; | 425 int _nextValidIndex; |
426 } | 426 } |
OLD | NEW |