author | psandoz |
Wed, 17 Apr 2013 11:34:31 +0200 | |
changeset 17168 | b7d3500f2516 |
parent 16867 | 76499721c6c1 |
child 17939 | bd750ec19d82 |
permissions | -rw-r--r-- |
2 | 1 |
/* |
16867 | 2 |
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. |
2 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 10 |
* |
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
5506 | 21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
2 | 24 |
*/ |
25 |
||
26 |
package java.util; |
|
16867 | 27 |
|
2 | 28 |
import java.io.*; |
16867 | 29 |
import java.util.function.Consumer; |
30 |
import java.util.function.BiFunction; |
|
31 |
import java.util.function.Function; |
|
2 | 32 |
|
33 |
/** |
|
34 |
* Hash table based implementation of the <tt>Map</tt> interface. This |
|
35 |
* implementation provides all of the optional map operations, and permits |
|
36 |
* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt> |
|
37 |
* class is roughly equivalent to <tt>Hashtable</tt>, except that it is |
|
38 |
* unsynchronized and permits nulls.) This class makes no guarantees as to |
|
39 |
* the order of the map; in particular, it does not guarantee that the order |
|
40 |
* will remain constant over time. |
|
41 |
* |
|
42 |
* <p>This implementation provides constant-time performance for the basic |
|
43 |
* operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function |
|
44 |
* disperses the elements properly among the buckets. Iteration over |
|
45 |
* collection views requires time proportional to the "capacity" of the |
|
46 |
* <tt>HashMap</tt> instance (the number of buckets) plus its size (the number |
|
47 |
* of key-value mappings). Thus, it's very important not to set the initial |
|
48 |
* capacity too high (or the load factor too low) if iteration performance is |
|
49 |
* important. |
|
50 |
* |
|
51 |
* <p>An instance of <tt>HashMap</tt> has two parameters that affect its |
|
52 |
* performance: <i>initial capacity</i> and <i>load factor</i>. The |
|
53 |
* <i>capacity</i> is the number of buckets in the hash table, and the initial |
|
54 |
* capacity is simply the capacity at the time the hash table is created. The |
|
55 |
* <i>load factor</i> is a measure of how full the hash table is allowed to |
|
56 |
* get before its capacity is automatically increased. When the number of |
|
57 |
* entries in the hash table exceeds the product of the load factor and the |
|
58 |
* current capacity, the hash table is <i>rehashed</i> (that is, internal data |
|
59 |
* structures are rebuilt) so that the hash table has approximately twice the |
|
60 |
* number of buckets. |
|
61 |
* |
|
62 |
* <p>As a general rule, the default load factor (.75) offers a good tradeoff |
|
63 |
* between time and space costs. Higher values decrease the space overhead |
|
64 |
* but increase the lookup cost (reflected in most of the operations of the |
|
65 |
* <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The |
|
66 |
* expected number of entries in the map and its load factor should be taken |
|
67 |
* into account when setting its initial capacity, so as to minimize the |
|
68 |
* number of rehash operations. If the initial capacity is greater |
|
69 |
* than the maximum number of entries divided by the load factor, no |
|
70 |
* rehash operations will ever occur. |
|
71 |
* |
|
72 |
* <p>If many mappings are to be stored in a <tt>HashMap</tt> instance, |
|
73 |
* creating it with a sufficiently large capacity will allow the mappings to |
|
74 |
* be stored more efficiently than letting it perform automatic rehashing as |
|
75 |
* needed to grow the table. |
|
76 |
* |
|
77 |
* <p><strong>Note that this implementation is not synchronized.</strong> |
|
78 |
* If multiple threads access a hash map concurrently, and at least one of |
|
79 |
* the threads modifies the map structurally, it <i>must</i> be |
|
80 |
* synchronized externally. (A structural modification is any operation |
|
81 |
* that adds or deletes one or more mappings; merely changing the value |
|
82 |
* associated with a key that an instance already contains is not a |
|
83 |
* structural modification.) This is typically accomplished by |
|
84 |
* synchronizing on some object that naturally encapsulates the map. |
|
85 |
* |
|
86 |
* If no such object exists, the map should be "wrapped" using the |
|
87 |
* {@link Collections#synchronizedMap Collections.synchronizedMap} |
|
88 |
* method. This is best done at creation time, to prevent accidental |
|
89 |
* unsynchronized access to the map:<pre> |
|
90 |
* Map m = Collections.synchronizedMap(new HashMap(...));</pre> |
|
91 |
* |
|
92 |
* <p>The iterators returned by all of this class's "collection view methods" |
|
93 |
* are <i>fail-fast</i>: if the map is structurally modified at any time after |
|
94 |
* the iterator is created, in any way except through the iterator's own |
|
95 |
* <tt>remove</tt> method, the iterator will throw a |
|
96 |
* {@link ConcurrentModificationException}. Thus, in the face of concurrent |
|
97 |
* modification, the iterator fails quickly and cleanly, rather than risking |
|
98 |
* arbitrary, non-deterministic behavior at an undetermined time in the |
|
99 |
* future. |
|
100 |
* |
|
101 |
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed |
|
102 |
* as it is, generally speaking, impossible to make any hard guarantees in the |
|
103 |
* presence of unsynchronized concurrent modification. Fail-fast iterators |
|
104 |
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis. |
|
105 |
* Therefore, it would be wrong to write a program that depended on this |
|
106 |
* exception for its correctness: <i>the fail-fast behavior of iterators |
|
107 |
* should be used only to detect bugs.</i> |
|
108 |
* |
|
109 |
* <p>This class is a member of the |
|
110 |
* <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
|
111 |
* Java Collections Framework</a>. |
|
112 |
* |
|
113 |
* @param <K> the type of keys maintained by this map |
|
114 |
* @param <V> the type of mapped values |
|
115 |
* |
|
116 |
* @author Doug Lea |
|
117 |
* @author Josh Bloch |
|
118 |
* @author Arthur van Hoff |
|
119 |
* @author Neal Gafter |
|
120 |
* @see Object#hashCode() |
|
121 |
* @see Collection |
|
122 |
* @see Map |
|
123 |
* @see TreeMap |
|
124 |
* @see Hashtable |
|
125 |
* @since 1.2 |
|
126 |
*/ |
|
127 |
||
128 |
public class HashMap<K,V> |
|
129 |
extends AbstractMap<K,V> |
|
130 |
implements Map<K,V>, Cloneable, Serializable |
|
131 |
{ |
|
132 |
||
133 |
/** |
|
134 |
* The default initial capacity - MUST be a power of two. |
|
135 |
*/ |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
136 |
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 |
2 | 137 |
|
138 |
/** |
|
139 |
* The maximum capacity, used if a higher value is implicitly specified |
|
140 |
* by either of the constructors with arguments. |
|
141 |
* MUST be a power of two <= 1<<30. |
|
142 |
*/ |
|
143 |
static final int MAXIMUM_CAPACITY = 1 << 30; |
|
144 |
||
145 |
/** |
|
146 |
* The load factor used when none specified in constructor. |
|
147 |
*/ |
|
148 |
static final float DEFAULT_LOAD_FACTOR = 0.75f; |
|
149 |
||
150 |
/** |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
151 |
* An empty table instance to share when the table is not inflated. |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
152 |
*/ |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
153 |
static final Entry<?,?>[] EMPTY_TABLE = {}; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
154 |
|
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
155 |
/** |
2 | 156 |
* The table, resized as necessary. Length MUST Always be a power of two. |
157 |
*/ |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
158 |
transient Entry<?,?>[] table = EMPTY_TABLE; |
2 | 159 |
|
160 |
/** |
|
161 |
* The number of key-value mappings contained in this map. |
|
162 |
*/ |
|
163 |
transient int size; |
|
164 |
||
165 |
/** |
|
166 |
* The next size value at which to resize (capacity * load factor). |
|
167 |
* @serial |
|
168 |
*/ |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
169 |
// If table == EMPTY_TABLE then this is the initial capacity at which the |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
170 |
// table will be created when inflated. |
2 | 171 |
int threshold; |
172 |
||
173 |
/** |
|
174 |
* The load factor for the hash table. |
|
175 |
* |
|
176 |
* @serial |
|
177 |
*/ |
|
178 |
final float loadFactor; |
|
179 |
||
180 |
/** |
|
181 |
* The number of times this HashMap has been structurally modified |
|
182 |
* Structural modifications are those that change the number of mappings in |
|
183 |
* the HashMap or otherwise modify its internal structure (e.g., |
|
184 |
* rehash). This field is used to make iterators on Collection-views of |
|
185 |
* the HashMap fail-fast. (See ConcurrentModificationException). |
|
186 |
*/ |
|
65 | 187 |
transient int modCount; |
2 | 188 |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
189 |
private static class Holder { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
190 |
/** |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
191 |
* |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
192 |
*/ |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
193 |
static final sun.misc.Unsafe UNSAFE; |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
194 |
|
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
195 |
/** |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
196 |
* Offset of "final" hashSeed field we must set in |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
197 |
* readObject() method. |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
198 |
*/ |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
199 |
static final long HASHSEED_OFFSET; |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
200 |
|
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
201 |
static { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
202 |
try { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
203 |
UNSAFE = sun.misc.Unsafe.getUnsafe(); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
204 |
HASHSEED_OFFSET = UNSAFE.objectFieldOffset( |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
205 |
HashMap.class.getDeclaredField("hashSeed")); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
206 |
} catch (NoSuchFieldException | SecurityException e) { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
207 |
throw new InternalError("Failed to record hashSeed offset", e); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
208 |
} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
209 |
} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
210 |
} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
211 |
|
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
212 |
/** |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
213 |
* A randomizing value associated with this instance that is applied to |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
214 |
* hash code of keys to make hash collisions harder to find. |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
215 |
*/ |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
216 |
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
217 |
|
2 | 218 |
/** |
219 |
* Constructs an empty <tt>HashMap</tt> with the specified initial |
|
220 |
* capacity and load factor. |
|
221 |
* |
|
222 |
* @param initialCapacity the initial capacity |
|
223 |
* @param loadFactor the load factor |
|
224 |
* @throws IllegalArgumentException if the initial capacity is negative |
|
225 |
* or the load factor is nonpositive |
|
226 |
*/ |
|
227 |
public HashMap(int initialCapacity, float loadFactor) { |
|
228 |
if (initialCapacity < 0) |
|
229 |
throw new IllegalArgumentException("Illegal initial capacity: " + |
|
230 |
initialCapacity); |
|
231 |
if (initialCapacity > MAXIMUM_CAPACITY) |
|
232 |
initialCapacity = MAXIMUM_CAPACITY; |
|
233 |
if (loadFactor <= 0 || Float.isNaN(loadFactor)) |
|
234 |
throw new IllegalArgumentException("Illegal load factor: " + |
|
235 |
loadFactor); |
|
236 |
||
237 |
this.loadFactor = loadFactor; |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
238 |
threshold = initialCapacity; |
2 | 239 |
init(); |
240 |
} |
|
241 |
||
242 |
/** |
|
243 |
* Constructs an empty <tt>HashMap</tt> with the specified initial |
|
244 |
* capacity and the default load factor (0.75). |
|
245 |
* |
|
246 |
* @param initialCapacity the initial capacity. |
|
247 |
* @throws IllegalArgumentException if the initial capacity is negative. |
|
248 |
*/ |
|
249 |
public HashMap(int initialCapacity) { |
|
250 |
this(initialCapacity, DEFAULT_LOAD_FACTOR); |
|
251 |
} |
|
252 |
||
253 |
/** |
|
254 |
* Constructs an empty <tt>HashMap</tt> with the default initial capacity |
|
255 |
* (16) and the default load factor (0.75). |
|
256 |
*/ |
|
257 |
public HashMap() { |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
258 |
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); |
2 | 259 |
} |
260 |
||
261 |
/** |
|
262 |
* Constructs a new <tt>HashMap</tt> with the same mappings as the |
|
263 |
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with |
|
264 |
* default load factor (0.75) and an initial capacity sufficient to |
|
265 |
* hold the mappings in the specified <tt>Map</tt>. |
|
266 |
* |
|
267 |
* @param m the map whose mappings are to be placed in this map |
|
268 |
* @throws NullPointerException if the specified map is null |
|
269 |
*/ |
|
270 |
public HashMap(Map<? extends K, ? extends V> m) { |
|
271 |
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, |
|
272 |
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
273 |
inflateTable(threshold); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
274 |
|
2 | 275 |
putAllForCreate(m); |
276 |
} |
|
277 |
||
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
278 |
private static int roundUpToPowerOf2(int number) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
279 |
// assert number >= 0 : "number must be non-negative"; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
280 |
int rounded = number >= MAXIMUM_CAPACITY |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
281 |
? MAXIMUM_CAPACITY |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
282 |
: (rounded = Integer.highestOneBit(number)) != 0 |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
283 |
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
284 |
: 1; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
285 |
|
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
286 |
return rounded; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
287 |
} |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
288 |
|
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
289 |
/** |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
290 |
* Inflates the table. |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
291 |
*/ |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
292 |
private void inflateTable(int toSize) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
293 |
// Find a power of 2 >= toSize |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
294 |
int capacity = roundUpToPowerOf2(toSize); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
295 |
|
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
296 |
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
297 |
table = new Entry[capacity]; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
298 |
} |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
299 |
|
2 | 300 |
// internal utilities |
301 |
||
302 |
/** |
|
303 |
* Initialization hook for subclasses. This method is called |
|
304 |
* in all constructors and pseudo-constructors (clone, readObject) |
|
305 |
* after HashMap has been initialized but before any entries have |
|
306 |
* been inserted. (In the absence of this method, readObject would |
|
307 |
* require explicit knowledge of subclasses.) |
|
308 |
*/ |
|
309 |
void init() { |
|
310 |
} |
|
311 |
||
312 |
/** |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
313 |
* Retrieve object hash code and applies a supplemental hash function to the |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
314 |
* result hash, which defends against poor quality hash functions. This is |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
315 |
* critical because HashMap uses power-of-two length hash tables, that |
2 | 316 |
* otherwise encounter collisions for hashCodes that do not differ |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
317 |
* in lower bits. |
2 | 318 |
*/ |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
319 |
final int hash(Object k) { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
320 |
if (k instanceof String) { |
13018 | 321 |
return ((String) k).hash32(); |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
322 |
} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
323 |
|
13018 | 324 |
int h = hashSeed ^ k.hashCode(); |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
325 |
|
2 | 326 |
// This function ensures that hashCodes that differ only by |
327 |
// constant multiples at each bit position have a bounded |
|
328 |
// number of collisions (approximately 8 at default load factor). |
|
329 |
h ^= (h >>> 20) ^ (h >>> 12); |
|
330 |
return h ^ (h >>> 7) ^ (h >>> 4); |
|
331 |
} |
|
332 |
||
333 |
/** |
|
334 |
* Returns index for hash code h. |
|
335 |
*/ |
|
336 |
static int indexFor(int h, int length) { |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
337 |
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; |
2 | 338 |
return h & (length-1); |
339 |
} |
|
340 |
||
341 |
/** |
|
342 |
* Returns the number of key-value mappings in this map. |
|
343 |
* |
|
344 |
* @return the number of key-value mappings in this map |
|
345 |
*/ |
|
346 |
public int size() { |
|
347 |
return size; |
|
348 |
} |
|
349 |
||
350 |
/** |
|
351 |
* Returns <tt>true</tt> if this map contains no key-value mappings. |
|
352 |
* |
|
353 |
* @return <tt>true</tt> if this map contains no key-value mappings |
|
354 |
*/ |
|
355 |
public boolean isEmpty() { |
|
356 |
return size == 0; |
|
357 |
} |
|
358 |
||
359 |
/** |
|
360 |
* Returns the value to which the specified key is mapped, |
|
361 |
* or {@code null} if this map contains no mapping for the key. |
|
362 |
* |
|
363 |
* <p>More formally, if this map contains a mapping from a key |
|
364 |
* {@code k} to a value {@code v} such that {@code (key==null ? k==null : |
|
365 |
* key.equals(k))}, then this method returns {@code v}; otherwise |
|
366 |
* it returns {@code null}. (There can be at most one such mapping.) |
|
367 |
* |
|
368 |
* <p>A return value of {@code null} does not <i>necessarily</i> |
|
369 |
* indicate that the map contains no mapping for the key; it's also |
|
370 |
* possible that the map explicitly maps the key to {@code null}. |
|
371 |
* The {@link #containsKey containsKey} operation may be used to |
|
372 |
* distinguish these two cases. |
|
373 |
* |
|
374 |
* @see #put(Object, Object) |
|
375 |
*/ |
|
12448 | 376 |
@SuppressWarnings("unchecked") |
2 | 377 |
public V get(Object key) { |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
378 |
Entry<K,V> entry = getEntry(key); |
2 | 379 |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
380 |
return null == entry ? null : entry.getValue(); |
2 | 381 |
} |
382 |
||
16867 | 383 |
@Override |
384 |
public V getOrDefault(Object key, V defaultValue) { |
|
385 |
Entry<K,V> entry = getEntry(key); |
|
386 |
||
387 |
return (entry == null) ? defaultValue : entry.getValue(); |
|
388 |
} |
|
389 |
||
2 | 390 |
/** |
391 |
* Returns <tt>true</tt> if this map contains a mapping for the |
|
392 |
* specified key. |
|
393 |
* |
|
394 |
* @param key The key whose presence in this map is to be tested |
|
395 |
* @return <tt>true</tt> if this map contains a mapping for the specified |
|
396 |
* key. |
|
397 |
*/ |
|
398 |
public boolean containsKey(Object key) { |
|
399 |
return getEntry(key) != null; |
|
400 |
} |
|
401 |
||
402 |
/** |
|
403 |
* Returns the entry associated with the specified key in the |
|
404 |
* HashMap. Returns null if the HashMap contains no mapping |
|
405 |
* for the key. |
|
406 |
*/ |
|
12448 | 407 |
@SuppressWarnings("unchecked") |
2 | 408 |
final Entry<K,V> getEntry(Object key) { |
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
409 |
if (isEmpty()) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
410 |
return null; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
411 |
} |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
412 |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
413 |
int hash = (key == null) ? 0 : hash(key); |
12448 | 414 |
for (Entry<?,?> e = table[indexFor(hash, table.length)]; |
2 | 415 |
e != null; |
416 |
e = e.next) { |
|
417 |
Object k; |
|
418 |
if (e.hash == hash && |
|
419 |
((k = e.key) == key || (key != null && key.equals(k)))) |
|
12448 | 420 |
return (Entry<K,V>)e; |
2 | 421 |
} |
422 |
return null; |
|
423 |
} |
|
424 |
||
425 |
/** |
|
426 |
* Associates the specified value with the specified key in this map. |
|
427 |
* If the map previously contained a mapping for the key, the old |
|
428 |
* value is replaced. |
|
429 |
* |
|
430 |
* @param key key with which the specified value is to be associated |
|
431 |
* @param value value to be associated with the specified key |
|
432 |
* @return the previous value associated with <tt>key</tt>, or |
|
433 |
* <tt>null</tt> if there was no mapping for <tt>key</tt>. |
|
434 |
* (A <tt>null</tt> return can also indicate that the map |
|
435 |
* previously associated <tt>null</tt> with <tt>key</tt>.) |
|
436 |
*/ |
|
437 |
public V put(K key, V value) { |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
438 |
if (table == EMPTY_TABLE) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
439 |
inflateTable(threshold); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
440 |
} |
2 | 441 |
if (key == null) |
442 |
return putForNullKey(value); |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
443 |
int hash = hash(key); |
2 | 444 |
int i = indexFor(hash, table.length); |
12448 | 445 |
@SuppressWarnings("unchecked") |
446 |
Entry<K,V> e = (Entry<K,V>)table[i]; |
|
447 |
for(; e != null; e = e.next) { |
|
2 | 448 |
Object k; |
449 |
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { |
|
450 |
V oldValue = e.value; |
|
451 |
e.value = value; |
|
452 |
e.recordAccess(this); |
|
453 |
return oldValue; |
|
454 |
} |
|
455 |
} |
|
456 |
||
457 |
modCount++; |
|
458 |
addEntry(hash, key, value, i); |
|
459 |
return null; |
|
460 |
} |
|
461 |
||
462 |
/** |
|
463 |
* Offloaded version of put for null keys |
|
464 |
*/ |
|
465 |
private V putForNullKey(V value) { |
|
12448 | 466 |
@SuppressWarnings("unchecked") |
467 |
Entry<K,V> e = (Entry<K,V>)table[0]; |
|
468 |
for(; e != null; e = e.next) { |
|
2 | 469 |
if (e.key == null) { |
470 |
V oldValue = e.value; |
|
471 |
e.value = value; |
|
472 |
e.recordAccess(this); |
|
473 |
return oldValue; |
|
474 |
} |
|
475 |
} |
|
476 |
modCount++; |
|
477 |
addEntry(0, null, value, 0); |
|
478 |
return null; |
|
479 |
} |
|
480 |
||
481 |
/** |
|
482 |
* This method is used instead of put by constructors and |
|
483 |
* pseudoconstructors (clone, readObject). It does not resize the table, |
|
484 |
* check for comodification, etc. It calls createEntry rather than |
|
485 |
* addEntry. |
|
486 |
*/ |
|
487 |
private void putForCreate(K key, V value) { |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
488 |
int hash = null == key ? 0 : hash(key); |
2 | 489 |
int i = indexFor(hash, table.length); |
490 |
||
491 |
/** |
|
492 |
* Look for preexisting entry for key. This will never happen for |
|
493 |
* clone or deserialize. It will only happen for construction if the |
|
494 |
* input Map is a sorted map whose ordering is inconsistent w/ equals. |
|
495 |
*/ |
|
12448 | 496 |
for (@SuppressWarnings("unchecked") |
497 |
Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) { |
|
2 | 498 |
Object k; |
499 |
if (e.hash == hash && |
|
500 |
((k = e.key) == key || (key != null && key.equals(k)))) { |
|
501 |
e.value = value; |
|
502 |
return; |
|
503 |
} |
|
504 |
} |
|
505 |
||
506 |
createEntry(hash, key, value, i); |
|
507 |
} |
|
508 |
||
509 |
private void putAllForCreate(Map<? extends K, ? extends V> m) { |
|
4110 | 510 |
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) |
2 | 511 |
putForCreate(e.getKey(), e.getValue()); |
512 |
} |
|
513 |
||
514 |
/** |
|
515 |
* Rehashes the contents of this map into a new array with a |
|
516 |
* larger capacity. This method is called automatically when the |
|
517 |
* number of keys in this map reaches its threshold. |
|
518 |
* |
|
519 |
* If current capacity is MAXIMUM_CAPACITY, this method does not |
|
520 |
* resize the map, but sets threshold to Integer.MAX_VALUE. |
|
521 |
* This has the effect of preventing future calls. |
|
522 |
* |
|
523 |
* @param newCapacity the new capacity, MUST be a power of two; |
|
524 |
* must be greater than current capacity unless current |
|
525 |
* capacity is MAXIMUM_CAPACITY (in which case value |
|
526 |
* is irrelevant). |
|
527 |
*/ |
|
528 |
void resize(int newCapacity) { |
|
12448 | 529 |
Entry<?,?>[] oldTable = table; |
2 | 530 |
int oldCapacity = oldTable.length; |
531 |
if (oldCapacity == MAXIMUM_CAPACITY) { |
|
532 |
threshold = Integer.MAX_VALUE; |
|
533 |
return; |
|
534 |
} |
|
535 |
||
12448 | 536 |
Entry<?,?>[] newTable = new Entry<?,?>[newCapacity]; |
2 | 537 |
transfer(newTable); |
538 |
table = newTable; |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
539 |
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); |
2 | 540 |
} |
541 |
||
542 |
/** |
|
543 |
* Transfers all entries from current table to newTable. |
|
544 |
*/ |
|
12448 | 545 |
@SuppressWarnings("unchecked") |
546 |
void transfer(Entry<?,?>[] newTable) { |
|
547 |
Entry<?,?>[] src = table; |
|
2 | 548 |
int newCapacity = newTable.length; |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
549 |
for (int j = 0; j < src.length; j++ ) { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
550 |
Entry<K,V> e = (Entry<K,V>) src[j]; |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
551 |
while(null != e) { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
552 |
Entry<K,V> next = e.next; |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
553 |
int i = indexFor(e.hash, newCapacity); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
554 |
e.next = (Entry<K,V>) newTable[i]; |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
555 |
newTable[i] = e; |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
556 |
e = next; |
2 | 557 |
} |
558 |
} |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
559 |
Arrays.fill(table, null); |
2 | 560 |
} |
561 |
||
562 |
/** |
|
563 |
* Copies all of the mappings from the specified map to this map. |
|
564 |
* These mappings will replace any mappings that this map had for |
|
565 |
* any of the keys currently in the specified map. |
|
566 |
* |
|
567 |
* @param m mappings to be stored in this map |
|
568 |
* @throws NullPointerException if the specified map is null |
|
569 |
*/ |
|
570 |
public void putAll(Map<? extends K, ? extends V> m) { |
|
571 |
int numKeysToBeAdded = m.size(); |
|
572 |
if (numKeysToBeAdded == 0) |
|
573 |
return; |
|
574 |
||
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
575 |
if (table == EMPTY_TABLE) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
576 |
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
577 |
} |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
578 |
|
2 | 579 |
/* |
580 |
* Expand the map if the map if the number of mappings to be added |
|
581 |
* is greater than or equal to threshold. This is conservative; the |
|
582 |
* obvious condition is (m.size() + size) >= threshold, but this |
|
583 |
* condition could result in a map with twice the appropriate capacity, |
|
584 |
* if the keys to be added overlap with the keys already in this map. |
|
585 |
* By using the conservative calculation, we subject ourself |
|
586 |
* to at most one extra resize. |
|
587 |
*/ |
|
588 |
if (numKeysToBeAdded > threshold) { |
|
589 |
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); |
|
590 |
if (targetCapacity > MAXIMUM_CAPACITY) |
|
591 |
targetCapacity = MAXIMUM_CAPACITY; |
|
592 |
int newCapacity = table.length; |
|
593 |
while (newCapacity < targetCapacity) |
|
594 |
newCapacity <<= 1; |
|
595 |
if (newCapacity > table.length) |
|
596 |
resize(newCapacity); |
|
597 |
} |
|
598 |
||
4110 | 599 |
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) |
2 | 600 |
put(e.getKey(), e.getValue()); |
601 |
} |
|
602 |
||
603 |
/** |
|
604 |
* Removes the mapping for the specified key from this map if present. |
|
605 |
* |
|
606 |
* @param key key whose mapping is to be removed from the map |
|
607 |
* @return the previous value associated with <tt>key</tt>, or |
|
608 |
* <tt>null</tt> if there was no mapping for <tt>key</tt>. |
|
609 |
* (A <tt>null</tt> return can also indicate that the map |
|
610 |
* previously associated <tt>null</tt> with <tt>key</tt>.) |
|
611 |
*/ |
|
612 |
public V remove(Object key) { |
|
613 |
Entry<K,V> e = removeEntryForKey(key); |
|
614 |
return (e == null ? null : e.value); |
|
615 |
} |
|
616 |
||
16867 | 617 |
// optimized implementations of default methods in Map |
618 |
||
619 |
@Override |
|
620 |
public V putIfAbsent(K key, V value) { |
|
621 |
if (table == EMPTY_TABLE) { |
|
622 |
inflateTable(threshold); |
|
623 |
} |
|
624 |
int hash = (key == null) ? 0 : hash(key); |
|
625 |
int i = indexFor(hash, table.length); |
|
626 |
@SuppressWarnings("unchecked") |
|
627 |
Entry<K,V> e = (Entry<K,V>)table[i]; |
|
628 |
for(; e != null; e = e.next) { |
|
629 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
630 |
if(e.value != null) { |
|
631 |
return e.value; |
|
632 |
} |
|
633 |
e.value = value; |
|
634 |
modCount++; |
|
635 |
e.recordAccess(this); |
|
636 |
return null; |
|
637 |
} |
|
638 |
} |
|
639 |
||
640 |
modCount++; |
|
641 |
addEntry(hash, key, value, i); |
|
642 |
return null; |
|
643 |
} |
|
644 |
||
645 |
@Override |
|
646 |
public boolean remove(Object key, Object value) { |
|
647 |
if (isEmpty()) { |
|
648 |
return false; |
|
649 |
} |
|
650 |
int hash = (key == null) ? 0 : hash(key); |
|
651 |
int i = indexFor(hash, table.length); |
|
652 |
@SuppressWarnings("unchecked") |
|
653 |
Entry<K,V> prev = (Entry<K,V>)table[i]; |
|
654 |
Entry<K,V> e = prev; |
|
655 |
||
656 |
while (e != null) { |
|
657 |
Entry<K,V> next = e.next; |
|
658 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
659 |
if (!Objects.equals(e.value, value)) { |
|
660 |
return false; |
|
661 |
} |
|
662 |
modCount++; |
|
663 |
size--; |
|
664 |
if (prev == e) |
|
665 |
table[i] = next; |
|
666 |
else |
|
667 |
prev.next = next; |
|
668 |
e.recordRemoval(this); |
|
669 |
return true; |
|
670 |
} |
|
671 |
prev = e; |
|
672 |
e = next; |
|
673 |
} |
|
674 |
||
675 |
return false; |
|
676 |
} |
|
677 |
||
678 |
@Override |
|
679 |
public boolean replace(K key, V oldValue, V newValue) { |
|
680 |
if (isEmpty()) { |
|
681 |
return false; |
|
682 |
} |
|
683 |
int hash = (key == null) ? 0 : hash(key); |
|
684 |
int i = indexFor(hash, table.length); |
|
685 |
@SuppressWarnings("unchecked") |
|
686 |
Entry<K,V> e = (Entry<K,V>)table[i]; |
|
687 |
for (; e != null; e = e.next) { |
|
688 |
if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) { |
|
689 |
e.value = newValue; |
|
690 |
e.recordAccess(this); |
|
691 |
return true; |
|
692 |
} |
|
693 |
} |
|
694 |
||
695 |
return false; |
|
696 |
} |
|
697 |
||
698 |
@Override |
|
699 |
public V replace(K key, V value) { |
|
700 |
if (isEmpty()) { |
|
701 |
return null; |
|
702 |
} |
|
703 |
int hash = (key == null) ? 0 : hash(key); |
|
704 |
int i = indexFor(hash, table.length); |
|
705 |
@SuppressWarnings("unchecked") |
|
706 |
Entry<K,V> e = (Entry<K,V>)table[i]; |
|
707 |
for (; e != null; e = e.next) { |
|
708 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
709 |
V oldValue = e.value; |
|
710 |
e.value = value; |
|
711 |
e.recordAccess(this); |
|
712 |
return oldValue; |
|
713 |
} |
|
714 |
} |
|
715 |
||
716 |
return null; |
|
717 |
} |
|
718 |
||
719 |
@Override |
|
720 |
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { |
|
721 |
if (table == EMPTY_TABLE) { |
|
722 |
inflateTable(threshold); |
|
723 |
} |
|
724 |
int hash = (key == null) ? 0 : hash(key); |
|
725 |
int i = indexFor(hash, table.length); |
|
726 |
@SuppressWarnings("unchecked") |
|
727 |
Entry<K,V> e = (Entry<K,V>)table[i]; |
|
728 |
for (; e != null; e = e.next) { |
|
729 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
730 |
V oldValue = e.value; |
|
731 |
return oldValue == null ? (e.value = mappingFunction.apply(key)) : oldValue; |
|
732 |
} |
|
733 |
} |
|
734 |
||
735 |
V newValue = mappingFunction.apply(key); |
|
736 |
if (newValue != null) { |
|
737 |
modCount++; |
|
738 |
addEntry(hash, key, newValue, i); |
|
739 |
} |
|
740 |
||
741 |
return newValue; |
|
742 |
} |
|
743 |
||
744 |
@Override |
|
745 |
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { |
|
746 |
if (isEmpty()) { |
|
747 |
return null; |
|
748 |
} |
|
749 |
int hash = (key == null) ? 0 : hash(key); |
|
750 |
int i = indexFor(hash, table.length); |
|
751 |
@SuppressWarnings("unchecked") |
|
752 |
Entry<K,V> prev = (Entry<K,V>)table[i]; |
|
753 |
Entry<K,V> e = prev; |
|
754 |
||
755 |
while (e != null) { |
|
756 |
Entry<K,V> next = e.next; |
|
757 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
758 |
V oldValue = e.value; |
|
759 |
if (oldValue == null) |
|
760 |
break; |
|
761 |
V newValue = remappingFunction.apply(key, oldValue); |
|
762 |
modCount++; |
|
763 |
if (newValue == null) { |
|
764 |
size--; |
|
765 |
if (prev == e) |
|
766 |
table[i] = next; |
|
767 |
else |
|
768 |
prev.next = next; |
|
769 |
e.recordRemoval(this); |
|
770 |
} else { |
|
771 |
e.value = newValue; |
|
772 |
e.recordAccess(this); |
|
773 |
} |
|
774 |
return newValue; |
|
775 |
} |
|
776 |
prev = e; |
|
777 |
e = next; |
|
778 |
} |
|
779 |
||
780 |
return null; |
|
781 |
} |
|
782 |
||
783 |
@Override |
|
784 |
public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { |
|
785 |
if (table == EMPTY_TABLE) { |
|
786 |
inflateTable(threshold); |
|
787 |
} |
|
788 |
int hash = (key == null) ? 0 : hash(key); |
|
789 |
int i = indexFor(hash, table.length); |
|
790 |
@SuppressWarnings("unchecked") |
|
791 |
Entry<K,V> prev = (Entry<K,V>)table[i]; |
|
792 |
Entry<K,V> e = prev; |
|
793 |
||
794 |
while (e != null) { |
|
795 |
Entry<K,V> next = e.next; |
|
796 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
797 |
V oldValue = e.value; |
|
798 |
V newValue = remappingFunction.apply(key, oldValue); |
|
799 |
if (newValue != oldValue) { |
|
800 |
modCount++; |
|
801 |
if (newValue == null) { |
|
802 |
size--; |
|
803 |
if (prev == e) |
|
804 |
table[i] = next; |
|
805 |
else |
|
806 |
prev.next = next; |
|
807 |
e.recordRemoval(this); |
|
808 |
} else { |
|
809 |
e.value = newValue; |
|
810 |
e.recordAccess(this); |
|
811 |
} |
|
812 |
} |
|
813 |
return newValue; |
|
814 |
} |
|
815 |
prev = e; |
|
816 |
e = next; |
|
817 |
} |
|
818 |
||
819 |
V newValue = remappingFunction.apply(key, null); |
|
820 |
if (newValue != null) { |
|
821 |
modCount++; |
|
822 |
addEntry(hash, key, newValue, i); |
|
823 |
} |
|
824 |
||
825 |
return newValue; |
|
826 |
} |
|
827 |
||
828 |
@Override |
|
829 |
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { |
|
830 |
if (table == EMPTY_TABLE) { |
|
831 |
inflateTable(threshold); |
|
832 |
} |
|
833 |
int hash = (key == null) ? 0 : hash(key); |
|
834 |
int i = indexFor(hash, table.length); |
|
835 |
@SuppressWarnings("unchecked") |
|
836 |
Entry<K,V> prev = (Entry<K,V>)table[i]; |
|
837 |
Entry<K,V> e = prev; |
|
838 |
||
839 |
while (e != null) { |
|
840 |
Entry<K,V> next = e.next; |
|
841 |
if (e.hash == hash && Objects.equals(e.key, key)) { |
|
842 |
V oldValue = e.value; |
|
843 |
V newValue = remappingFunction.apply(oldValue, value); |
|
844 |
modCount++; |
|
845 |
if (newValue == null) { |
|
846 |
size--; |
|
847 |
if (prev == e) |
|
848 |
table[i] = next; |
|
849 |
else |
|
850 |
prev.next = next; |
|
851 |
e.recordRemoval(this); |
|
852 |
} else { |
|
853 |
e.value = newValue; |
|
854 |
e.recordAccess(this); |
|
855 |
} |
|
856 |
return newValue; |
|
857 |
} |
|
858 |
prev = e; |
|
859 |
e = next; |
|
860 |
} |
|
861 |
||
862 |
if (value != null) { |
|
863 |
modCount++; |
|
864 |
addEntry(hash, key, value, i); |
|
865 |
} |
|
866 |
||
867 |
return value; |
|
868 |
} |
|
869 |
||
870 |
// end of optimized implementations of default methods in Map |
|
871 |
||
2 | 872 |
/** |
873 |
* Removes and returns the entry associated with the specified key |
|
874 |
* in the HashMap. Returns null if the HashMap contains no mapping |
|
875 |
* for this key. |
|
876 |
*/ |
|
877 |
final Entry<K,V> removeEntryForKey(Object key) { |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
878 |
if (isEmpty()) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
879 |
return null; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
880 |
} |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
881 |
int hash = (key == null) ? 0 : hash(key); |
2 | 882 |
int i = indexFor(hash, table.length); |
12448 | 883 |
@SuppressWarnings("unchecked") |
884 |
Entry<K,V> prev = (Entry<K,V>)table[i]; |
|
2 | 885 |
Entry<K,V> e = prev; |
886 |
||
887 |
while (e != null) { |
|
888 |
Entry<K,V> next = e.next; |
|
889 |
Object k; |
|
890 |
if (e.hash == hash && |
|
891 |
((k = e.key) == key || (key != null && key.equals(k)))) { |
|
892 |
modCount++; |
|
893 |
size--; |
|
894 |
if (prev == e) |
|
895 |
table[i] = next; |
|
896 |
else |
|
897 |
prev.next = next; |
|
898 |
e.recordRemoval(this); |
|
899 |
return e; |
|
900 |
} |
|
901 |
prev = e; |
|
902 |
e = next; |
|
903 |
} |
|
904 |
||
905 |
return e; |
|
906 |
} |
|
907 |
||
908 |
/** |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
909 |
* Special version of remove for EntrySet using {@code Map.Entry.equals()} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
910 |
* for matching. |
2 | 911 |
*/ |
912 |
final Entry<K,V> removeMapping(Object o) { |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
913 |
if (isEmpty() || !(o instanceof Map.Entry)) |
2 | 914 |
return null; |
915 |
||
12448 | 916 |
Map.Entry<?,?> entry = (Map.Entry<?,?>) o; |
2 | 917 |
Object key = entry.getKey(); |
12883
0553a7aa3404
7174736: JCK test api/java_util/HashMap/index_EntrySet failing
mduigou
parents:
12863
diff
changeset
|
918 |
int hash = (key == null) ? 0 : hash(key); |
2 | 919 |
int i = indexFor(hash, table.length); |
12448 | 920 |
@SuppressWarnings("unchecked") |
921 |
Entry<K,V> prev = (Entry<K,V>)table[i]; |
|
2 | 922 |
Entry<K,V> e = prev; |
923 |
||
924 |
while (e != null) { |
|
925 |
Entry<K,V> next = e.next; |
|
926 |
if (e.hash == hash && e.equals(entry)) { |
|
927 |
modCount++; |
|
928 |
size--; |
|
929 |
if (prev == e) |
|
930 |
table[i] = next; |
|
931 |
else |
|
932 |
prev.next = next; |
|
933 |
e.recordRemoval(this); |
|
934 |
return e; |
|
935 |
} |
|
936 |
prev = e; |
|
937 |
e = next; |
|
938 |
} |
|
939 |
||
940 |
return e; |
|
941 |
} |
|
942 |
||
943 |
/** |
|
944 |
* Removes all of the mappings from this map. |
|
945 |
* The map will be empty after this call returns. |
|
946 |
*/ |
|
947 |
public void clear() { |
|
948 |
modCount++; |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
949 |
Arrays.fill(table, null); |
2 | 950 |
size = 0; |
951 |
} |
|
952 |
||
953 |
/** |
|
954 |
* Returns <tt>true</tt> if this map maps one or more keys to the |
|
955 |
* specified value. |
|
956 |
* |
|
957 |
* @param value value whose presence in this map is to be tested |
|
958 |
* @return <tt>true</tt> if this map maps one or more keys to the |
|
959 |
* specified value |
|
960 |
*/ |
|
961 |
public boolean containsValue(Object value) { |
|
962 |
if (value == null) |
|
963 |
return containsNullValue(); |
|
964 |
||
12448 | 965 |
Entry<?,?>[] tab = table; |
16867 | 966 |
for (int i = 0; i < tab.length; i++) |
967 |
for (Entry<?,?> e = tab[i]; e != null; e = e.next) |
|
2 | 968 |
if (value.equals(e.value)) |
969 |
return true; |
|
970 |
return false; |
|
971 |
} |
|
972 |
||
973 |
/** |
|
974 |
* Special-case code for containsValue with null argument |
|
975 |
*/ |
|
976 |
private boolean containsNullValue() { |
|
12448 | 977 |
Entry<?,?>[] tab = table; |
16867 | 978 |
for (int i = 0; i < tab.length; i++) |
979 |
for (Entry<?,?> e = tab[i]; e != null; e = e.next) |
|
2 | 980 |
if (e.value == null) |
981 |
return true; |
|
982 |
return false; |
|
983 |
} |
|
984 |
||
985 |
/** |
|
986 |
* Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and |
|
987 |
* values themselves are not cloned. |
|
988 |
* |
|
989 |
* @return a shallow copy of this map |
|
990 |
*/ |
|
12448 | 991 |
@SuppressWarnings("unchecked") |
2 | 992 |
public Object clone() { |
993 |
HashMap<K,V> result = null; |
|
994 |
try { |
|
995 |
result = (HashMap<K,V>)super.clone(); |
|
996 |
} catch (CloneNotSupportedException e) { |
|
997 |
// assert false; |
|
998 |
} |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
999 |
if (result.table != EMPTY_TABLE) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1000 |
result.inflateTable(Math.min( |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1001 |
(int) Math.min( |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1002 |
size * Math.min(1 / loadFactor, 4.0f), |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1003 |
// we have limits... |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1004 |
HashMap.MAXIMUM_CAPACITY), |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1005 |
table.length)); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1006 |
} |
2 | 1007 |
result.entrySet = null; |
1008 |
result.modCount = 0; |
|
1009 |
result.size = 0; |
|
1010 |
result.init(); |
|
1011 |
result.putAllForCreate(this); |
|
1012 |
||
1013 |
return result; |
|
1014 |
} |
|
1015 |
||
1016 |
static class Entry<K,V> implements Map.Entry<K,V> { |
|
1017 |
final K key; |
|
1018 |
V value; |
|
1019 |
Entry<K,V> next; |
|
1020 |
final int hash; |
|
1021 |
||
1022 |
/** |
|
1023 |
* Creates new entry. |
|
1024 |
*/ |
|
1025 |
Entry(int h, K k, V v, Entry<K,V> n) { |
|
1026 |
value = v; |
|
1027 |
next = n; |
|
1028 |
key = k; |
|
1029 |
hash = h; |
|
1030 |
} |
|
1031 |
||
1032 |
public final K getKey() { |
|
1033 |
return key; |
|
1034 |
} |
|
1035 |
||
1036 |
public final V getValue() { |
|
1037 |
return value; |
|
1038 |
} |
|
1039 |
||
1040 |
public final V setValue(V newValue) { |
|
1041 |
V oldValue = value; |
|
1042 |
value = newValue; |
|
1043 |
return oldValue; |
|
1044 |
} |
|
1045 |
||
1046 |
public final boolean equals(Object o) { |
|
1047 |
if (!(o instanceof Map.Entry)) |
|
1048 |
return false; |
|
12448 | 1049 |
Map.Entry<?,?> e = (Map.Entry<?,?>)o; |
2 | 1050 |
Object k1 = getKey(); |
1051 |
Object k2 = e.getKey(); |
|
1052 |
if (k1 == k2 || (k1 != null && k1.equals(k2))) { |
|
1053 |
Object v1 = getValue(); |
|
1054 |
Object v2 = e.getValue(); |
|
1055 |
if (v1 == v2 || (v1 != null && v1.equals(v2))) |
|
1056 |
return true; |
|
1057 |
} |
|
1058 |
return false; |
|
1059 |
} |
|
1060 |
||
1061 |
public final int hashCode() { |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1062 |
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); |
2 | 1063 |
} |
1064 |
||
1065 |
public final String toString() { |
|
1066 |
return getKey() + "=" + getValue(); |
|
1067 |
} |
|
1068 |
||
1069 |
/** |
|
1070 |
* This method is invoked whenever the value in an entry is |
|
1071 |
* overwritten by an invocation of put(k,v) for a key k that's already |
|
1072 |
* in the HashMap. |
|
1073 |
*/ |
|
1074 |
void recordAccess(HashMap<K,V> m) { |
|
1075 |
} |
|
1076 |
||
1077 |
/** |
|
1078 |
* This method is invoked whenever the entry is |
|
1079 |
* removed from the table. |
|
1080 |
*/ |
|
1081 |
void recordRemoval(HashMap<K,V> m) { |
|
1082 |
} |
|
1083 |
} |
|
1084 |
||
1085 |
/** |
|
1086 |
* Adds a new entry with the specified key, value and hash code to |
|
1087 |
* the specified bucket. It is the responsibility of this |
|
1088 |
* method to resize the table if appropriate. |
|
1089 |
* |
|
1090 |
* Subclass overrides this to alter the behavior of put method. |
|
1091 |
*/ |
|
1092 |
void addEntry(int hash, K key, V value, int bucketIndex) { |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1093 |
if ((size >= threshold) && (null != table[bucketIndex])) { |
2 | 1094 |
resize(2 * table.length); |
12863 | 1095 |
hash = (null != key) ? hash(key) : 0; |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1096 |
bucketIndex = indexFor(hash, table.length); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1097 |
} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1098 |
|
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1099 |
createEntry(hash, key, value, bucketIndex); |
2 | 1100 |
} |
1101 |
||
1102 |
/** |
|
1103 |
* Like addEntry except that this version is used when creating entries |
|
1104 |
* as part of Map construction or "pseudo-construction" (cloning, |
|
1105 |
* deserialization). This version needn't worry about resizing the table. |
|
1106 |
* |
|
1107 |
* Subclass overrides this to alter the behavior of HashMap(Map), |
|
1108 |
* clone, and readObject. |
|
1109 |
*/ |
|
1110 |
void createEntry(int hash, K key, V value, int bucketIndex) { |
|
12448 | 1111 |
@SuppressWarnings("unchecked") |
1112 |
Entry<K,V> e = (Entry<K,V>)table[bucketIndex]; |
|
7803
56bc97d69d93
6880112: Project Coin: Port JDK core library code to use diamond operator
smarks
parents:
5506
diff
changeset
|
1113 |
table[bucketIndex] = new Entry<>(hash, key, value, e); |
2 | 1114 |
size++; |
1115 |
} |
|
1116 |
||
1117 |
private abstract class HashIterator<E> implements Iterator<E> { |
|
12448 | 1118 |
Entry<?,?> next; // next entry to return |
2 | 1119 |
int expectedModCount; // For fast-fail |
1120 |
int index; // current slot |
|
12448 | 1121 |
Entry<?,?> current; // current entry |
2 | 1122 |
|
1123 |
HashIterator() { |
|
1124 |
expectedModCount = modCount; |
|
1125 |
if (size > 0) { // advance to first entry |
|
12448 | 1126 |
Entry<?,?>[] t = table; |
2 | 1127 |
while (index < t.length && (next = t[index++]) == null) |
1128 |
; |
|
1129 |
} |
|
1130 |
} |
|
1131 |
||
1132 |
public final boolean hasNext() { |
|
1133 |
return next != null; |
|
1134 |
} |
|
1135 |
||
12448 | 1136 |
@SuppressWarnings("unchecked") |
2 | 1137 |
final Entry<K,V> nextEntry() { |
1138 |
if (modCount != expectedModCount) |
|
1139 |
throw new ConcurrentModificationException(); |
|
12448 | 1140 |
Entry<?,?> e = next; |
2 | 1141 |
if (e == null) |
1142 |
throw new NoSuchElementException(); |
|
1143 |
||
1144 |
if ((next = e.next) == null) { |
|
12448 | 1145 |
Entry<?,?>[] t = table; |
2 | 1146 |
while (index < t.length && (next = t[index++]) == null) |
1147 |
; |
|
1148 |
} |
|
1149 |
current = e; |
|
12448 | 1150 |
return (Entry<K,V>)e; |
2 | 1151 |
} |
1152 |
||
1153 |
public void remove() { |
|
1154 |
if (current == null) |
|
1155 |
throw new IllegalStateException(); |
|
1156 |
if (modCount != expectedModCount) |
|
1157 |
throw new ConcurrentModificationException(); |
|
1158 |
Object k = current.key; |
|
1159 |
current = null; |
|
1160 |
HashMap.this.removeEntryForKey(k); |
|
1161 |
expectedModCount = modCount; |
|
1162 |
} |
|
1163 |
} |
|
1164 |
||
1165 |
private final class ValueIterator extends HashIterator<V> { |
|
1166 |
public V next() { |
|
1167 |
return nextEntry().value; |
|
1168 |
} |
|
1169 |
} |
|
1170 |
||
1171 |
private final class KeyIterator extends HashIterator<K> { |
|
1172 |
public K next() { |
|
1173 |
return nextEntry().getKey(); |
|
1174 |
} |
|
1175 |
} |
|
1176 |
||
1177 |
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { |
|
1178 |
public Map.Entry<K,V> next() { |
|
1179 |
return nextEntry(); |
|
1180 |
} |
|
1181 |
} |
|
1182 |
||
1183 |
// Subclass overrides these to alter behavior of views' iterator() method |
|
1184 |
Iterator<K> newKeyIterator() { |
|
1185 |
return new KeyIterator(); |
|
1186 |
} |
|
1187 |
Iterator<V> newValueIterator() { |
|
1188 |
return new ValueIterator(); |
|
1189 |
} |
|
1190 |
Iterator<Map.Entry<K,V>> newEntryIterator() { |
|
1191 |
return new EntryIterator(); |
|
1192 |
} |
|
1193 |
||
1194 |
||
1195 |
// Views |
|
1196 |
||
1197 |
private transient Set<Map.Entry<K,V>> entrySet = null; |
|
1198 |
||
1199 |
/** |
|
1200 |
* Returns a {@link Set} view of the keys contained in this map. |
|
1201 |
* The set is backed by the map, so changes to the map are |
|
1202 |
* reflected in the set, and vice-versa. If the map is modified |
|
1203 |
* while an iteration over the set is in progress (except through |
|
1204 |
* the iterator's own <tt>remove</tt> operation), the results of |
|
1205 |
* the iteration are undefined. The set supports element removal, |
|
1206 |
* which removes the corresponding mapping from the map, via the |
|
1207 |
* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, |
|
1208 |
* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> |
|
1209 |
* operations. It does not support the <tt>add</tt> or <tt>addAll</tt> |
|
1210 |
* operations. |
|
1211 |
*/ |
|
1212 |
public Set<K> keySet() { |
|
1213 |
Set<K> ks = keySet; |
|
1214 |
return (ks != null ? ks : (keySet = new KeySet())); |
|
1215 |
} |
|
1216 |
||
1217 |
private final class KeySet extends AbstractSet<K> { |
|
1218 |
public Iterator<K> iterator() { |
|
1219 |
return newKeyIterator(); |
|
1220 |
} |
|
1221 |
public int size() { |
|
1222 |
return size; |
|
1223 |
} |
|
1224 |
public boolean contains(Object o) { |
|
1225 |
return containsKey(o); |
|
1226 |
} |
|
1227 |
public boolean remove(Object o) { |
|
1228 |
return HashMap.this.removeEntryForKey(o) != null; |
|
1229 |
} |
|
1230 |
public void clear() { |
|
1231 |
HashMap.this.clear(); |
|
1232 |
} |
|
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1233 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1234 |
public Spliterator<K> spliterator() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1235 |
if (HashMap.this.getClass() == HashMap.class) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1236 |
return new KeySpliterator<K,V>(HashMap.this, 0, -1, 0, 0); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1237 |
else |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1238 |
return Spliterators.spliterator |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1239 |
(this, Spliterator.SIZED | Spliterator.DISTINCT); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1240 |
} |
2 | 1241 |
} |
1242 |
||
1243 |
/** |
|
1244 |
* Returns a {@link Collection} view of the values contained in this map. |
|
1245 |
* The collection is backed by the map, so changes to the map are |
|
1246 |
* reflected in the collection, and vice-versa. If the map is |
|
1247 |
* modified while an iteration over the collection is in progress |
|
1248 |
* (except through the iterator's own <tt>remove</tt> operation), |
|
1249 |
* the results of the iteration are undefined. The collection |
|
1250 |
* supports element removal, which removes the corresponding |
|
1251 |
* mapping from the map, via the <tt>Iterator.remove</tt>, |
|
1252 |
* <tt>Collection.remove</tt>, <tt>removeAll</tt>, |
|
1253 |
* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not |
|
1254 |
* support the <tt>add</tt> or <tt>addAll</tt> operations. |
|
1255 |
*/ |
|
1256 |
public Collection<V> values() { |
|
1257 |
Collection<V> vs = values; |
|
1258 |
return (vs != null ? vs : (values = new Values())); |
|
1259 |
} |
|
1260 |
||
1261 |
private final class Values extends AbstractCollection<V> { |
|
1262 |
public Iterator<V> iterator() { |
|
1263 |
return newValueIterator(); |
|
1264 |
} |
|
1265 |
public int size() { |
|
1266 |
return size; |
|
1267 |
} |
|
1268 |
public boolean contains(Object o) { |
|
1269 |
return containsValue(o); |
|
1270 |
} |
|
1271 |
public void clear() { |
|
1272 |
HashMap.this.clear(); |
|
1273 |
} |
|
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1274 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1275 |
public Spliterator<V> spliterator() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1276 |
if (HashMap.this.getClass() == HashMap.class) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1277 |
return new ValueSpliterator<K,V>(HashMap.this, 0, -1, 0, 0); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1278 |
else |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1279 |
return Spliterators.spliterator |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1280 |
(this, Spliterator.SIZED); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1281 |
} |
2 | 1282 |
} |
1283 |
||
1284 |
/** |
|
1285 |
* Returns a {@link Set} view of the mappings contained in this map. |
|
1286 |
* The set is backed by the map, so changes to the map are |
|
1287 |
* reflected in the set, and vice-versa. If the map is modified |
|
1288 |
* while an iteration over the set is in progress (except through |
|
1289 |
* the iterator's own <tt>remove</tt> operation, or through the |
|
1290 |
* <tt>setValue</tt> operation on a map entry returned by the |
|
1291 |
* iterator) the results of the iteration are undefined. The set |
|
1292 |
* supports element removal, which removes the corresponding |
|
1293 |
* mapping from the map, via the <tt>Iterator.remove</tt>, |
|
1294 |
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and |
|
1295 |
* <tt>clear</tt> operations. It does not support the |
|
1296 |
* <tt>add</tt> or <tt>addAll</tt> operations. |
|
1297 |
* |
|
1298 |
* @return a set view of the mappings contained in this map |
|
1299 |
*/ |
|
1300 |
public Set<Map.Entry<K,V>> entrySet() { |
|
1301 |
return entrySet0(); |
|
1302 |
} |
|
1303 |
||
1304 |
private Set<Map.Entry<K,V>> entrySet0() { |
|
1305 |
Set<Map.Entry<K,V>> es = entrySet; |
|
1306 |
return es != null ? es : (entrySet = new EntrySet()); |
|
1307 |
} |
|
1308 |
||
1309 |
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { |
|
1310 |
public Iterator<Map.Entry<K,V>> iterator() { |
|
1311 |
return newEntryIterator(); |
|
1312 |
} |
|
1313 |
public boolean contains(Object o) { |
|
1314 |
if (!(o instanceof Map.Entry)) |
|
1315 |
return false; |
|
12448 | 1316 |
Map.Entry<?,?> e = (Map.Entry<?,?>) o; |
2 | 1317 |
Entry<K,V> candidate = getEntry(e.getKey()); |
1318 |
return candidate != null && candidate.equals(e); |
|
1319 |
} |
|
1320 |
public boolean remove(Object o) { |
|
1321 |
return removeMapping(o) != null; |
|
1322 |
} |
|
1323 |
public int size() { |
|
1324 |
return size; |
|
1325 |
} |
|
1326 |
public void clear() { |
|
1327 |
HashMap.this.clear(); |
|
1328 |
} |
|
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1329 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1330 |
public Spliterator<Map.Entry<K,V>> spliterator() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1331 |
if (HashMap.this.getClass() == HashMap.class) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1332 |
return new EntrySpliterator<K,V>(HashMap.this, 0, -1, 0, 0); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1333 |
else |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1334 |
return Spliterators.spliterator |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1335 |
(this, Spliterator.SIZED | Spliterator.DISTINCT); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1336 |
} |
2 | 1337 |
} |
1338 |
||
1339 |
/** |
|
1340 |
* Save the state of the <tt>HashMap</tt> instance to a stream (i.e., |
|
1341 |
* serialize it). |
|
1342 |
* |
|
1343 |
* @serialData The <i>capacity</i> of the HashMap (the length of the |
|
16725
9e7cfcc4ff6a
8011199: Backout changeset JDK-7143928 (2b34a1eb3153)
mduigou
parents:
16723
diff
changeset
|
1344 |
* bucket array) is emitted (int), followed by the |
2 | 1345 |
* <i>size</i> (an int, the number of key-value |
1346 |
* mappings), followed by the key (Object) and value (Object) |
|
1347 |
* for each key-value mapping. The key-value mappings are |
|
1348 |
* emitted in no particular order. |
|
1349 |
*/ |
|
1350 |
private void writeObject(java.io.ObjectOutputStream s) |
|
1351 |
throws IOException |
|
1352 |
{ |
|
1353 |
// Write out the threshold, loadfactor, and any hidden stuff |
|
1354 |
s.defaultWriteObject(); |
|
1355 |
||
1356 |
// Write out number of buckets |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1357 |
if (table==EMPTY_TABLE) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1358 |
s.writeInt(roundUpToPowerOf2(threshold)); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1359 |
} else { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1360 |
s.writeInt(table.length); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1361 |
} |
2 | 1362 |
|
1363 |
// Write out size (number of Mappings) |
|
1364 |
s.writeInt(size); |
|
1365 |
||
1366 |
// Write out keys and values (alternating) |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1367 |
if (size > 0) { |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1368 |
for(Map.Entry<K,V> e : entrySet0()) { |
2 | 1369 |
s.writeObject(e.getKey()); |
1370 |
s.writeObject(e.getValue()); |
|
1371 |
} |
|
1372 |
} |
|
1373 |
} |
|
1374 |
||
1375 |
private static final long serialVersionUID = 362498820763181265L; |
|
1376 |
||
1377 |
/** |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1378 |
* Reconstitute the {@code HashMap} instance from a stream (i.e., |
2 | 1379 |
* deserialize it). |
1380 |
*/ |
|
1381 |
private void readObject(java.io.ObjectInputStream s) |
|
1382 |
throws IOException, ClassNotFoundException |
|
1383 |
{ |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1384 |
// Read in the threshold (ignored), loadfactor, and any hidden stuff |
2 | 1385 |
s.defaultReadObject(); |
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1386 |
if (loadFactor <= 0 || Float.isNaN(loadFactor)) { |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1387 |
throw new InvalidObjectException("Illegal load factor: " + |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1388 |
loadFactor); |
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1389 |
} |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1390 |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1391 |
// set other fields that need values |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1392 |
Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1393 |
sun.misc.Hashing.randomHashSeed(this)); |
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1394 |
table = EMPTY_TABLE; |
2 | 1395 |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1396 |
// Read in number of buckets |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1397 |
s.readInt(); // ignored. |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1398 |
|
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1399 |
// Read number of mappings |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1400 |
int mappings = s.readInt(); |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1401 |
if (mappings < 0) |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1402 |
throw new InvalidObjectException("Illegal mappings count: " + |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1403 |
mappings); |
2 | 1404 |
|
16855
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1405 |
// capacity chosen by number of mappings and desired load (if >= 0.25) |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1406 |
int capacity = (int) Math.min( |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1407 |
mappings * Math.min(1 / loadFactor, 4.0f), |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1408 |
// we have limits... |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1409 |
HashMap.MAXIMUM_CAPACITY); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1410 |
|
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1411 |
// allocate the bucket array; |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1412 |
if (mappings > 0) { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1413 |
inflateTable(capacity); |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1414 |
} else { |
106eaf391fbc
8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents:
16725
diff
changeset
|
1415 |
threshold = capacity; |
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1416 |
} |
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1417 |
|
2 | 1418 |
init(); // Give subclass a chance to do its thing. |
1419 |
||
1420 |
// Read the keys and values, and put the mappings in the HashMap |
|
12859
c44b88bb9b5e
7126277: Alternative String hashing implementation
mduigou
parents:
12448
diff
changeset
|
1421 |
for (int i=0; i<mappings; i++) { |
12448 | 1422 |
@SuppressWarnings("unchecked") |
1423 |
K key = (K) s.readObject(); |
|
1424 |
@SuppressWarnings("unchecked") |
|
1425 |
V value = (V) s.readObject(); |
|
2 | 1426 |
putForCreate(key, value); |
1427 |
} |
|
1428 |
} |
|
1429 |
||
1430 |
// These methods are used when serializing HashSets |
|
1431 |
int capacity() { return table.length; } |
|
1432 |
float loadFactor() { return loadFactor; } |
|
17168
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1433 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1434 |
/** |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1435 |
* Standin until HM overhaul; based loosely on Weak and Identity HM. |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1436 |
*/ |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1437 |
static class HashMapSpliterator<K,V> { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1438 |
final HashMap<K,V> map; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1439 |
HashMap.Entry<K,V> current; // current node |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1440 |
int index; // current index, modified on advance/split |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1441 |
int fence; // one past last index |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1442 |
int est; // size estimate |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1443 |
int expectedModCount; // for comodification checks |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1444 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1445 |
HashMapSpliterator(HashMap<K,V> m, int origin, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1446 |
int fence, int est, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1447 |
int expectedModCount) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1448 |
this.map = m; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1449 |
this.index = origin; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1450 |
this.fence = fence; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1451 |
this.est = est; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1452 |
this.expectedModCount = expectedModCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1453 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1454 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1455 |
final int getFence() { // initialize fence and size on first use |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1456 |
int hi; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1457 |
if ((hi = fence) < 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1458 |
HashMap<K,V> m = map; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1459 |
est = m.size; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1460 |
expectedModCount = m.modCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1461 |
hi = fence = m.table.length; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1462 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1463 |
return hi; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1464 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1465 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1466 |
public final long estimateSize() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1467 |
getFence(); // force init |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1468 |
return (long) est; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1469 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1470 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1471 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1472 |
static final class KeySpliterator<K,V> |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1473 |
extends HashMapSpliterator<K,V> |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1474 |
implements Spliterator<K> { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1475 |
KeySpliterator(HashMap<K,V> m, int origin, int fence, int est, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1476 |
int expectedModCount) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1477 |
super(m, origin, fence, est, expectedModCount); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1478 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1479 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1480 |
public KeySpliterator<K,V> trySplit() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1481 |
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1482 |
return (lo >= mid || current != null) ? null : |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1483 |
new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1484 |
expectedModCount); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1485 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1486 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1487 |
@SuppressWarnings("unchecked") |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1488 |
public void forEachRemaining(Consumer<? super K> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1489 |
int i, hi, mc; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1490 |
if (action == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1491 |
throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1492 |
HashMap<K,V> m = map; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1493 |
HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1494 |
if ((hi = fence) < 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1495 |
mc = expectedModCount = m.modCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1496 |
hi = fence = tab.length; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1497 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1498 |
else |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1499 |
mc = expectedModCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1500 |
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1501 |
HashMap.Entry<K,V> p = current; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1502 |
do { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1503 |
if (p == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1504 |
p = tab[i++]; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1505 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1506 |
action.accept(p.getKey()); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1507 |
p = p.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1508 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1509 |
} while (p != null || i < hi); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1510 |
if (m.modCount != mc) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1511 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1512 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1513 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1514 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1515 |
@SuppressWarnings("unchecked") |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1516 |
public boolean tryAdvance(Consumer<? super K> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1517 |
int hi; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1518 |
if (action == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1519 |
throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1520 |
HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1521 |
if (tab.length >= (hi = getFence()) && index >= 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1522 |
while (current != null || index < hi) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1523 |
if (current == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1524 |
current = tab[index++]; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1525 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1526 |
K k = current.getKey(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1527 |
current = current.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1528 |
action.accept(k); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1529 |
if (map.modCount != expectedModCount) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1530 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1531 |
return true; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1532 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1533 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1534 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1535 |
return false; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1536 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1537 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1538 |
public int characteristics() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1539 |
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1540 |
Spliterator.DISTINCT; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1541 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1542 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1543 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1544 |
static final class ValueSpliterator<K,V> |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1545 |
extends HashMapSpliterator<K,V> |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1546 |
implements Spliterator<V> { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1547 |
ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1548 |
int expectedModCount) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1549 |
super(m, origin, fence, est, expectedModCount); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1550 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1551 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1552 |
public ValueSpliterator<K,V> trySplit() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1553 |
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1554 |
return (lo >= mid || current != null) ? null : |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1555 |
new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1556 |
expectedModCount); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1557 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1558 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1559 |
@SuppressWarnings("unchecked") |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1560 |
public void forEachRemaining(Consumer<? super V> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1561 |
int i, hi, mc; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1562 |
if (action == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1563 |
throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1564 |
HashMap<K,V> m = map; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1565 |
HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1566 |
if ((hi = fence) < 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1567 |
mc = expectedModCount = m.modCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1568 |
hi = fence = tab.length; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1569 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1570 |
else |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1571 |
mc = expectedModCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1572 |
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1573 |
HashMap.Entry<K,V> p = current; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1574 |
do { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1575 |
if (p == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1576 |
p = tab[i++]; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1577 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1578 |
action.accept(p.getValue()); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1579 |
p = p.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1580 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1581 |
} while (p != null || i < hi); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1582 |
if (m.modCount != mc) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1583 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1584 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1585 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1586 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1587 |
@SuppressWarnings("unchecked") |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1588 |
public boolean tryAdvance(Consumer<? super V> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1589 |
int hi; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1590 |
if (action == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1591 |
throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1592 |
HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1593 |
if (tab.length >= (hi = getFence()) && index >= 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1594 |
while (current != null || index < hi) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1595 |
if (current == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1596 |
current = tab[index++]; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1597 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1598 |
V v = current.getValue(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1599 |
current = current.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1600 |
action.accept(v); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1601 |
if (map.modCount != expectedModCount) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1602 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1603 |
return true; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1604 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1605 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1606 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1607 |
return false; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1608 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1609 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1610 |
public int characteristics() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1611 |
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1612 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1613 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1614 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1615 |
static final class EntrySpliterator<K,V> |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1616 |
extends HashMapSpliterator<K,V> |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1617 |
implements Spliterator<Map.Entry<K,V>> { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1618 |
EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1619 |
int expectedModCount) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1620 |
super(m, origin, fence, est, expectedModCount); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1621 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1622 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1623 |
public EntrySpliterator<K,V> trySplit() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1624 |
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1625 |
return (lo >= mid || current != null) ? null : |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1626 |
new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1, |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1627 |
expectedModCount); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1628 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1629 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1630 |
@SuppressWarnings("unchecked") |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1631 |
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1632 |
int i, hi, mc; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1633 |
if (action == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1634 |
throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1635 |
HashMap<K,V> m = map; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1636 |
HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1637 |
if ((hi = fence) < 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1638 |
mc = expectedModCount = m.modCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1639 |
hi = fence = tab.length; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1640 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1641 |
else |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1642 |
mc = expectedModCount; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1643 |
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1644 |
HashMap.Entry<K,V> p = current; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1645 |
do { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1646 |
if (p == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1647 |
p = tab[i++]; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1648 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1649 |
action.accept(p); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1650 |
p = p.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1651 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1652 |
} while (p != null || i < hi); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1653 |
if (m.modCount != mc) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1654 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1655 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1656 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1657 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1658 |
@SuppressWarnings("unchecked") |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1659 |
public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1660 |
int hi; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1661 |
if (action == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1662 |
throw new NullPointerException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1663 |
HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1664 |
if (tab.length >= (hi = getFence()) && index >= 0) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1665 |
while (current != null || index < hi) { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1666 |
if (current == null) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1667 |
current = tab[index++]; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1668 |
else { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1669 |
HashMap.Entry<K,V> e = current; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1670 |
current = current.next; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1671 |
action.accept(e); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1672 |
if (map.modCount != expectedModCount) |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1673 |
throw new ConcurrentModificationException(); |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1674 |
return true; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1675 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1676 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1677 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1678 |
return false; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1679 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1680 |
|
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1681 |
public int characteristics() { |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1682 |
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1683 |
Spliterator.DISTINCT; |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1684 |
} |
b7d3500f2516
8011426: java.util collection Spliterator implementations
psandoz
parents:
16867
diff
changeset
|
1685 |
} |
2 | 1686 |
} |