OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, 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, V> implements HashMap<K, V> { | 6 class HashMapImplementation<K, 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 [_DELETED_KEY] of type | 10 // will contain both elements of type K, and the [_DELETED_KEY] of type |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
63 static int _firstProbe(int hashCode, int length) { | 63 static int _firstProbe(int hashCode, int length) { |
64 return hashCode & (length - 1); | 64 return hashCode & (length - 1); |
65 } | 65 } |
66 | 66 |
67 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { | 67 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { |
68 return (currentProbe + numberOfProbes) & (length - 1); | 68 return (currentProbe + numberOfProbes) & (length - 1); |
69 } | 69 } |
70 | 70 |
71 int _probeForAdding(K key) { | 71 int _probeForAdding(K key) { |
72 if (key == null) throw const NullPointerException(); | 72 if (key == null) throw const NullPointerException(); |
73 int hash = _firstProbe(key.hashCode(), _keys.length); | 73 int hash = _firstProbe(key.hashCode, _keys.length); |
74 int numberOfProbes = 1; | 74 int numberOfProbes = 1; |
75 int initialHash = hash; | 75 int initialHash = hash; |
76 // insertionIndex points to a slot where a key was deleted. | 76 // insertionIndex points to a slot where a key was deleted. |
77 int insertionIndex = -1; | 77 int insertionIndex = -1; |
78 while (true) { | 78 while (true) { |
79 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 79 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
80 Object existingKey = _keys[hash]; | 80 Object existingKey = _keys[hash]; |
81 if (existingKey === null) { | 81 if (existingKey === null) { |
82 // We are sure the key is not already in the set. | 82 // We are sure the key is not already in the set. |
83 // If the current slot is empty and we didn't find any | 83 // If the current slot is empty and we didn't find any |
(...skipping 13 matching lines...) Expand all Loading... |
97 | 97 |
98 // We did not find an insertion slot. Look at the next one. | 98 // We did not find an insertion slot. Look at the next one. |
99 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | 99 hash = _nextProbe(hash, numberOfProbes++, _keys.length); |
100 // _ensureCapacity has guaranteed the following cannot happen. | 100 // _ensureCapacity has guaranteed the following cannot happen. |
101 // assert(hash != initialHash); | 101 // assert(hash != initialHash); |
102 } | 102 } |
103 } | 103 } |
104 | 104 |
105 int _probeForLookup(K key) { | 105 int _probeForLookup(K key) { |
106 if (key == null) throw const NullPointerException(); | 106 if (key == null) throw const NullPointerException(); |
107 int hash = _firstProbe(key.hashCode(), _keys.length); | 107 int hash = _firstProbe(key.hashCode, _keys.length); |
108 int numberOfProbes = 1; | 108 int numberOfProbes = 1; |
109 int initialHash = hash; | 109 int initialHash = hash; |
110 while (true) { | 110 while (true) { |
111 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 111 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
112 Object existingKey = _keys[hash]; | 112 Object existingKey = _keys[hash]; |
113 // If the slot does not contain anything (in particular, it does not | 113 // If the slot does not contain anything (in particular, it does not |
114 // contain a deleted key), we know the key is not in the map. | 114 // contain a deleted key), we know the key is not in the map. |
115 if (existingKey === null) return -1; | 115 if (existingKey === null) return -1; |
116 // The key is in the map, return its index. | 116 // The key is in the map, return its index. |
117 if (existingKey == key) return hash; | 117 if (existingKey == key) return hash; |
(...skipping 329 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
447 | 447 |
448 /** | 448 /** |
449 * A singleton sentinel used to represent when a key is deleted from the map. | 449 * A singleton sentinel used to represent when a key is deleted from the map. |
450 * We can't use [: const Object() :] as a sentinel because it would end up | 450 * We can't use [: const Object() :] as a sentinel because it would end up |
451 * canonicalized and then we cannot distinguish the deleted key from the | 451 * canonicalized and then we cannot distinguish the deleted key from the |
452 * canonicalized [: Object() :]. | 452 * canonicalized [: Object() :]. |
453 */ | 453 */ |
454 class _DeletedKeySentinel { | 454 class _DeletedKeySentinel { |
455 const _DeletedKeySentinel(); | 455 const _DeletedKeySentinel(); |
456 } | 456 } |
OLD | NEW |