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 *
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.
24 */
25
26 package java.util;
27
28 import java.io.*;
29 import java.lang.reflect.ParameterizedType;
30 import java.lang.reflect.Type;
31 import java.util.concurrent.ThreadLocalRandom;
32 import java.util.function.Consumer;
33 import java.util.function.BiFunction;
34 import java.util.function.Function;
35
36 /**
37 * Hash table based implementation of the <tt>Map</tt> interface. This
38 * implementation provides all of the optional map operations, and permits
39 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
40 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
41 * unsynchronized and permits nulls.) This class makes no guarantees as to
42 * the order of the map; in particular, it does not guarantee that the order
43 * will remain constant over time.
44 *
45 * <p>This implementation provides constant-time performance for the basic
46 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
47 * disperses the elements properly among the buckets. Iteration over
48 * collection views requires time proportional to the "capacity" of the
49 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
50 * of key-value mappings). Thus, it's very important not to set the initial
51 * capacity too high (or the load factor too low) if iteration performance is
1284 resize(table.length * 2);
1285 }
1286
1287 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1288 put(e.getKey(), e.getValue());
1289 }
1290
1291 /**
1292 * Removes the mapping for the specified key from this map if present.
1293 *
1294 * @param key key whose mapping is to be removed from the map
1295 * @return the previous value associated with <tt>key</tt>, or
1296 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1297 * (A <tt>null</tt> return can also indicate that the map
1298 * previously associated <tt>null</tt> with <tt>key</tt>.)
1299 */
1300 public V remove(Object key) {
1301 Entry<K,V> e = removeEntryForKey(key);
1302 return (e == null ? null : e.value);
1303 }
1304
1305 // optimized implementations of default methods in Map
1306
1307 @Override
1308 public V putIfAbsent(K key, V value) {
1309 if (table == EMPTY_TABLE) {
1310 inflateTable(threshold);
1311 }
1312 if (key == null) {
1313 if (nullKeyEntry == null || nullKeyEntry.value == null) {
1314 putForNullKey(value);
1315 return null;
1316 } else {
1317 return nullKeyEntry.value;
1318 }
1319 }
1320 int hash = hash(key);
1321 int i = indexFor(hash, table.length);
1322 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1323
1324 if (table[i] instanceof Entry) {
1325 int listSize = 0;
1326 Entry<K,V> e = (Entry<K,V>) table[i];
1327 for (; e != null; e = (Entry<K,V>)e.next) {
2280 findNextBin();
2281 }
2282 }
2283 }
2284
2285 public final boolean hasNext() {
2286 return next != null;
2287 }
2288
2289 @SuppressWarnings("unchecked")
2290 final Entry<K,V> nextEntry() {
2291 if (modCount != expectedModCount) {
2292 throw new ConcurrentModificationException();
2293 }
2294 Object e = next;
2295 Entry<K,V> retVal;
2296
2297 if (e == null)
2298 throw new NoSuchElementException();
2299
2300 if (e instanceof Entry) {
2301 retVal = (Entry<K,V>)e;
2302 next = ((Entry<K,V>)e).next;
2303 } else { // TreeBin
2304 retVal = (Entry<K,V>)((TreeNode)e).entry;
2305 next = retVal.next;
2306 }
2307
2308 if (next == null) { // Move to next bin
2309 findNextBin();
2310 }
2311 current = e;
2312 return retVal;
2313 }
2314
2315 public void remove() {
2316 if (current == null)
2317 throw new IllegalStateException();
2318 if (modCount != expectedModCount)
2319 throw new ConcurrentModificationException();
2320 K k;
2321
2322 if (current instanceof Entry) {
2323 k = ((Entry<K,V>)current).key;
2324 } else {
2325 k = ((Entry<K,V>)((TreeNode)current).entry).key;
|
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 *
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.
24 */
25
26 package java.util;
27
28 import java.io.*;
29 import java.lang.reflect.ParameterizedType;
30 import java.lang.reflect.Type;
31 import java.util.concurrent.ThreadLocalRandom;
32 import java.util.function.BiConsumer;
33 import java.util.function.Consumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Function;
36
37 /**
38 * Hash table based implementation of the <tt>Map</tt> interface. This
39 * implementation provides all of the optional map operations, and permits
40 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
41 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
42 * unsynchronized and permits nulls.) This class makes no guarantees as to
43 * the order of the map; in particular, it does not guarantee that the order
44 * will remain constant over time.
45 *
46 * <p>This implementation provides constant-time performance for the basic
47 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
48 * disperses the elements properly among the buckets. Iteration over
49 * collection views requires time proportional to the "capacity" of the
50 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
51 * of key-value mappings). Thus, it's very important not to set the initial
52 * capacity too high (or the load factor too low) if iteration performance is
1285 resize(table.length * 2);
1286 }
1287
1288 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1289 put(e.getKey(), e.getValue());
1290 }
1291
1292 /**
1293 * Removes the mapping for the specified key from this map if present.
1294 *
1295 * @param key key whose mapping is to be removed from the map
1296 * @return the previous value associated with <tt>key</tt>, or
1297 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1298 * (A <tt>null</tt> return can also indicate that the map
1299 * previously associated <tt>null</tt> with <tt>key</tt>.)
1300 */
1301 public V remove(Object key) {
1302 Entry<K,V> e = removeEntryForKey(key);
1303 return (e == null ? null : e.value);
1304 }
1305 // optimized implementations of default methods in Map
1306
1307 @Override
1308 public void forEach(BiConsumer<? super K, ? super V> action) {
1309 Objects.requireNonNull(action);
1310 final int expectedModCount = modCount;
1311 if (nullKeyEntry != null) {
1312 forEachNullKey(expectedModCount, action);
1313 }
1314 Object[] tab = this.table;
1315 for(int index = 0; index < tab.length; index++) {
1316 Object item = tab[index];
1317 if (item == null) {
1318 continue;
1319 }
1320 if (item instanceof HashMap.TreeBin) {
1321 eachTreeNode(expectedModCount, ((TreeBin)item).first, action);
1322 continue;
1323 }
1324 @SuppressWarnings("unchecked")
1325 Entry<K,V> entry = (Entry<K,V>)item;
1326 while (entry != null) {
1327 action.accept(entry.key, entry.value);
1328 entry = (Entry<K,V>)entry.next;
1329
1330 if (expectedModCount != modCount) {
1331 throw new ConcurrentModificationException();
1332 }
1333 }
1334 }
1335 }
1336
1337 private void eachTreeNode(int expectedModCount, TreeNode<K,V> node, BiConsumer<? super K, ? super V> action) {
1338 while (node != null) {
1339 @SuppressWarnings("unchecked")
1340 Entry<K,V> entry = (Entry<K,V>)node.entry;
1341 action.accept(entry.key, entry.value);
1342 node = (TreeNode<K,V>)entry.next;
1343
1344 if (expectedModCount != modCount) {
1345 throw new ConcurrentModificationException();
1346 }
1347 }
1348 }
1349
1350 private void forEachNullKey(int expectedModCount, BiConsumer<? super K, ? super V> action) {
1351 action.accept(null, nullKeyEntry.value);
1352
1353 if (expectedModCount != modCount) {
1354 throw new ConcurrentModificationException();
1355 }
1356 }
1357
1358 @Override
1359 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1360 Objects.requireNonNull(function);
1361 final int expectedModCount = modCount;
1362 if (nullKeyEntry != null) {
1363 replaceforNullKey(expectedModCount, function);
1364 }
1365 Object[] tab = this.table;
1366 for(int index = 0; index < tab.length; index++) {
1367 Object item = tab[index];
1368 if (item == null) {
1369 continue;
1370 }
1371 if (item instanceof HashMap.TreeBin) {
1372 replaceEachTreeNode(expectedModCount, ((TreeBin)item).first, function);
1373 continue;
1374 }
1375 @SuppressWarnings("unchecked")
1376 Entry<K,V> entry = (Entry<K,V>)item;
1377 while (entry != null) {
1378 function.apply(entry.key, entry.value);
1379 entry = (Entry<K,V>)entry.next;
1380
1381 if (expectedModCount != modCount) {
1382 throw new ConcurrentModificationException();
1383 }
1384 }
1385 }
1386 }
1387
1388 private void replaceEachTreeNode(int expectedModCount, TreeNode<K,V> node, BiFunction<? super K, ? super V, ? extends V> function) {
1389 while (node != null) {
1390 @SuppressWarnings("unchecked")
1391 Entry<K,V> entry = (Entry<K,V>)node.entry;
1392 entry.value = function.apply(entry.key, entry.value);
1393 node = (TreeNode<K,V>)entry.next;
1394
1395 if (expectedModCount != modCount) {
1396 throw new ConcurrentModificationException();
1397 }
1398 }
1399 }
1400
1401 private void replaceforNullKey(int expectedModCount, BiFunction<? super K, ? super V, ? extends V> function) {
1402 nullKeyEntry.value = function.apply(null, nullKeyEntry.value);
1403
1404 if (expectedModCount != modCount) {
1405 throw new ConcurrentModificationException();
1406 }
1407 }
1408
1409 @Override
1410 public V putIfAbsent(K key, V value) {
1411 if (table == EMPTY_TABLE) {
1412 inflateTable(threshold);
1413 }
1414 if (key == null) {
1415 if (nullKeyEntry == null || nullKeyEntry.value == null) {
1416 putForNullKey(value);
1417 return null;
1418 } else {
1419 return nullKeyEntry.value;
1420 }
1421 }
1422 int hash = hash(key);
1423 int i = indexFor(hash, table.length);
1424 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1425
1426 if (table[i] instanceof Entry) {
1427 int listSize = 0;
1428 Entry<K,V> e = (Entry<K,V>) table[i];
1429 for (; e != null; e = (Entry<K,V>)e.next) {
2382 findNextBin();
2383 }
2384 }
2385 }
2386
2387 public final boolean hasNext() {
2388 return next != null;
2389 }
2390
2391 @SuppressWarnings("unchecked")
2392 final Entry<K,V> nextEntry() {
2393 if (modCount != expectedModCount) {
2394 throw new ConcurrentModificationException();
2395 }
2396 Object e = next;
2397 Entry<K,V> retVal;
2398
2399 if (e == null)
2400 throw new NoSuchElementException();
2401
2402 if (e instanceof TreeNode) { // TreeBin
2403 retVal = (Entry<K,V>)((TreeNode)e).entry;
2404 next = retVal.next;
2405 } else {
2406 retVal = (Entry<K,V>)e;
2407 next = ((Entry<K,V>)e).next;
2408 }
2409
2410 if (next == null) { // Move to next bin
2411 findNextBin();
2412 }
2413 current = e;
2414 return retVal;
2415 }
2416
2417 public void remove() {
2418 if (current == null)
2419 throw new IllegalStateException();
2420 if (modCount != expectedModCount)
2421 throw new ConcurrentModificationException();
2422 K k;
2423
2424 if (current instanceof Entry) {
2425 k = ((Entry<K,V>)current).key;
2426 } else {
2427 k = ((Entry<K,V>)((TreeNode)current).entry).key;
|