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[] table = this.table;
1315 for(int index = 0; index < table.length; index++) {
1316 Object item = table[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 for (;entry != null; entry = (Entry<K,V>)entry.next) {
1327 if (expectedModCount != modCount) {
1328 throw new ConcurrentModificationException();
1329 }
1330 action.accept(entry.key, entry.value);
1331 }
1332 }
1333 }
1334
1335 private void eachTreeNode(int expectedModCount, TreeNode<K,V> node, BiConsumer<? super K, ? super V> action) {
1336 while (node != null) {
1337 if (expectedModCount != modCount) {
1338 throw new ConcurrentModificationException();
1339 }
1340 @SuppressWarnings("unchecked")
1341 Entry<K,V> entry = (Entry<K,V>)node.entry;
1342 action.accept(entry.key, entry.value);
1343 node = (TreeNode<K,V>)entry.next;
1344 }
1345 }
1346
1347 private void forEachNullKey(int expectedModCount, BiConsumer<? super K, ? super V> action) {
1348 if (expectedModCount != modCount) {
1349 throw new ConcurrentModificationException();
1350 }
1351 action.accept(null, nullKeyEntry.value);
1352 }
1353
1354 @Override
1355 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1356 Objects.requireNonNull(function);
1357 final int expectedModCount = modCount;
1358 if (nullKeyEntry != null) {
1359 replaceforNullKey(expectedModCount, function);
1360 }
1361 Object[] table = this.table;
1362 for(int index = 0; index < table.length; index++) {
1363 Object item = table[index];
1364 if (item == null) {
1365 continue;
1366 }
1367 if (item instanceof HashMap.TreeBin) {
1368 replaceEachTreeNode(expectedModCount, ((TreeBin)item).first, function);
1369 continue;
1370 }
1371 @SuppressWarnings("unchecked")
1372 Entry<K,V> entry = (Entry<K,V>)item;
1373 for (;entry != null; entry = (Entry<K,V>)entry.next) {
1374 if (expectedModCount != modCount) {
1375 throw new ConcurrentModificationException();
1376 }
1377 entry.value = function.apply(entry.key, entry.value);
1378 }
1379 }
1380 }
1381
1382 private void replaceEachTreeNode(int expectedModCount, TreeNode<K,V> node, BiFunction<? super K, ? super V, ? extends V> function) {
1383 while (node != null) {
1384 if (expectedModCount != modCount) {
1385 throw new ConcurrentModificationException();
1386 }
1387 @SuppressWarnings("unchecked")
1388 Entry<K,V> entry = (Entry<K,V>)node.entry;
1389 entry.value = function.apply(entry.key, entry.value);
1390 node = (TreeNode<K,V>)entry.next;
1391 }
1392 }
1393
1394 private void replaceforNullKey(int expectedModCount, BiFunction<? super K, ? super V, ? extends V> function) {
1395 if (expectedModCount != modCount) {
1396 throw new ConcurrentModificationException();
1397 }
1398 nullKeyEntry.value = function.apply(null, nullKeyEntry.value);
1399 }
1400
1401 @Override
1402 public V putIfAbsent(K key, V value) {
1403 if (table == EMPTY_TABLE) {
1404 inflateTable(threshold);
1405 }
1406 if (key == null) {
1407 if (nullKeyEntry == null || nullKeyEntry.value == null) {
1408 putForNullKey(value);
1409 return null;
1410 } else {
1411 return nullKeyEntry.value;
1412 }
1413 }
1414 int hash = hash(key);
1415 int i = indexFor(hash, table.length);
1416 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1417
1418 if (table[i] instanceof Entry) {
1419 int listSize = 0;
1420 Entry<K,V> e = (Entry<K,V>) table[i];
1421 for (; e != null; e = (Entry<K,V>)e.next) {
2374 findNextBin();
2375 }
2376 }
2377 }
2378
2379 public final boolean hasNext() {
2380 return next != null;
2381 }
2382
2383 @SuppressWarnings("unchecked")
2384 final Entry<K,V> nextEntry() {
2385 if (modCount != expectedModCount) {
2386 throw new ConcurrentModificationException();
2387 }
2388 Object e = next;
2389 Entry<K,V> retVal;
2390
2391 if (e == null)
2392 throw new NoSuchElementException();
2393
2394 if (e instanceof TreeNode) { // TreeBin
2395 retVal = (Entry<K,V>)((TreeNode)e).entry;
2396 next = retVal.next;
2397 } else {
2398 retVal = (Entry<K,V>)e;
2399 next = ((Entry<K,V>)e).next;
2400 }
2401
2402 if (next == null) { // Move to next bin
2403 findNextBin();
2404 }
2405 current = e;
2406 return retVal;
2407 }
2408
2409 public void remove() {
2410 if (current == null)
2411 throw new IllegalStateException();
2412 if (modCount != expectedModCount)
2413 throw new ConcurrentModificationException();
2414 K k;
2415
2416 if (current instanceof Entry) {
2417 k = ((Entry<K,V>)current).key;
2418 } else {
2419 k = ((Entry<K,V>)((TreeNode)current).entry).key;
|