< prev index next >

src/java.base/share/classes/java/util/HashMap.java

Print this page




 484         this.loadFactor = DEFAULT_LOAD_FACTOR;
 485         putMapEntries(m, false);
 486     }
 487 
 488     /**
 489      * Implements Map.putAll and Map constructor.
 490      *
 491      * @param m the map
 492      * @param evict false when initially constructing this map, else
 493      * true (relayed to method afterNodeInsertion).
 494      */
 495     final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 496         int s = m.size();
 497         if (s > 0) {
 498             if (table == null) { // pre-size
 499                 float ft = ((float)s / loadFactor) + 1.0F;
 500                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
 501                          (int)ft : MAXIMUM_CAPACITY);
 502                 if (t > threshold)
 503                     threshold = tableSizeFor(t);


 504             }
 505             else if (s > threshold)
 506                 resize();
 507             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
 508                 K key = e.getKey();
 509                 V value = e.getValue();
 510                 putVal(hash(key), key, value, false, evict);
 511             }
 512         }
 513     }
 514 
 515     /**
 516      * Returns the number of key-value mappings in this map.
 517      *
 518      * @return the number of key-value mappings in this map
 519      */
 520     public int size() {
 521         return size;
 522     }
 523 
 524     /**
 525      * Returns {@code true} if this map contains no key-value mappings.
 526      *


 644                         break;
 645                     p = e;
 646                 }
 647             }
 648             if (e != null) { // existing mapping for key
 649                 V oldValue = e.value;
 650                 if (!onlyIfAbsent || oldValue == null)
 651                     e.value = value;
 652                 afterNodeAccess(e);
 653                 return oldValue;
 654             }
 655         }
 656         ++modCount;
 657         if (++size > threshold)
 658             resize();
 659         afterNodeInsertion(evict);
 660         return null;
 661     }
 662 
 663     /**























 664      * Initializes or doubles table size.  If null, allocates in
 665      * accord with initial capacity target held in field threshold.
 666      * Otherwise, because we are using power-of-two expansion, the
 667      * elements from each bin must either stay at same index, or move
 668      * with a power of two offset in the new table.
 669      *
 670      * @return the table
 671      */
 672     final Node<K,V>[] resize() {
 673         Node<K,V>[] oldTab = table;
 674         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 675         int oldThr = threshold;
 676         int newCap, newThr = 0;
 677         if (oldCap > 0) {
 678             if (oldCap >= MAXIMUM_CAPACITY) {
 679                 threshold = Integer.MAX_VALUE;
 680                 return oldTab;
 681             }
 682             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 683                      oldCap >= DEFAULT_INITIAL_CAPACITY)
 684                 newThr = oldThr << 1; // double threshold
 685         }
 686         else if (oldThr > 0) // initial capacity was placed in threshold
 687             newCap = oldThr;
 688         else {               // zero initial threshold signifies using defaults
 689             newCap = DEFAULT_INITIAL_CAPACITY;
 690             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 691         }
 692         if (newThr == 0) {
 693             float ft = (float)newCap * loadFactor;
 694             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
 695                       (int)ft : Integer.MAX_VALUE);
 696         }
 697         threshold = newThr;
 698         @SuppressWarnings({"rawtypes","unchecked"})
 699         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];





 700         table = newTab;
 701         if (oldTab != null) {
 702             for (int j = 0; j < oldCap; ++j) {
 703                 Node<K,V> e;
 704                 if ((e = oldTab[j]) != null) {
 705                     oldTab[j] = null;
 706                     if (e.next == null)
 707                         newTab[e.hash & (newCap - 1)] = e;
 708                     else if (e instanceof TreeNode)
 709                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
 710                     else { // preserve order
 711                         Node<K,V> loHead = null, loTail = null;
 712                         Node<K,V> hiHead = null, hiTail = null;
 713                         Node<K,V> next;
 714                         do {
 715                             next = e.next;
 716                             if ((e.hash & oldCap) == 0) {
 717                                 if (loTail == null)
 718                                     loHead = e;
 719                                 else
 720                                     loTail.next = e;
 721                                 loTail = e;
 722                             }
 723                             else {
 724                                 if (hiTail == null)

 725                                     hiHead = e;
 726                                 else
 727                                     hiTail.next = e;

 728                                 hiTail = e;
 729                             }
 730                         } while ((e = next) != null);
 731                         if (loTail != null) {
 732                             loTail.next = null;
 733                             newTab[j] = loHead;
 734                         }
 735                         if (hiTail != null) {
 736                             hiTail.next = null;
 737                             newTab[j + oldCap] = hiHead;
 738                         }
 739                     }
 740                 }
 741             }
 742         }
 743         return newTab;
 744     }
 745 
 746     /**
 747      * Replaces all linked nodes in bin at index for given hash unless




 484         this.loadFactor = DEFAULT_LOAD_FACTOR;
 485         putMapEntries(m, false);
 486     }
 487 
 488     /**
 489      * Implements Map.putAll and Map constructor.
 490      *
 491      * @param m the map
 492      * @param evict false when initially constructing this map, else
 493      * true (relayed to method afterNodeInsertion).
 494      */
 495     final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 496         int s = m.size();
 497         if (s > 0) {
 498             if (table == null) { // pre-size
 499                 float ft = ((float)s / loadFactor) + 1.0F;
 500                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
 501                          (int)ft : MAXIMUM_CAPACITY);
 502                 if (t > threshold)
 503                     threshold = tableSizeFor(t);
 504             } else if (s > threshold) {
 505                 resize(s);
 506             }


 507             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
 508                 K key = e.getKey();
 509                 V value = e.getValue();
 510                 putVal(hash(key), key, value, false, evict);
 511             }
 512         }
 513     }
 514 
 515     /**
 516      * Returns the number of key-value mappings in this map.
 517      *
 518      * @return the number of key-value mappings in this map
 519      */
 520     public int size() {
 521         return size;
 522     }
 523 
 524     /**
 525      * Returns {@code true} if this map contains no key-value mappings.
 526      *


 644                         break;
 645                     p = e;
 646                 }
 647             }
 648             if (e != null) { // existing mapping for key
 649                 V oldValue = e.value;
 650                 if (!onlyIfAbsent || oldValue == null)
 651                     e.value = value;
 652                 afterNodeAccess(e);
 653                 return oldValue;
 654             }
 655         }
 656         ++modCount;
 657         if (++size > threshold)
 658             resize();
 659         afterNodeInsertion(evict);
 660         return null;
 661     }
 662 
 663     /**
 664      * Resize the table to the nearest power of two to {@code size}. Moves all items to the new table.
 665      *
 666      * @param size expected number of elements in the new table
 667      * @return the table
 668      */
 669     final Node<K, V>[] resize(int size) {
 670         if (size < 0) {
 671             throw new IllegalArgumentException("Negative number of elements does not make sense.");
 672         }
 673         Node<K, V>[] oldTable = table;
 674         int oldCapacity = (oldTable == null) ? 0 : oldTable.length;
 675         int newCapacity = tableSizeFor(size);
 676 
 677         // need to resize?
 678         if (newCapacity > oldCapacity) {
 679             threshold = (int) ((float) newCapacity * loadFactor);
 680             return createTableAndMoveElements(newCapacity, oldCapacity, oldTable);
 681         } else {
 682             return oldTable;
 683         }
 684     }
 685 
 686     /**
 687      * Initializes or doubles table size.  If null, allocates in
 688      * accord with initial capacity target held in field threshold.
 689      * Otherwise, because we are using power-of-two expansion, the
 690      * elements from each bin must either stay at same index, or move
 691      * with a power of two offset in the new table.
 692      *
 693      * @return the table
 694      */
 695     final Node<K,V>[] resize() {
 696         Node<K,V>[] oldTab = table;
 697         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 698         int oldThr = threshold;
 699         int newCap, newThr = 0;
 700         if (oldCap > 0) {
 701             if (oldCap >= MAXIMUM_CAPACITY) {
 702                 threshold = Integer.MAX_VALUE;
 703                 return oldTab;
 704             }
 705             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 706                      oldCap >= DEFAULT_INITIAL_CAPACITY)
 707                 newThr = oldThr << 1; // double threshold
 708         }
 709         else if (oldThr > 0) // initial capacity was placed in threshold
 710             newCap = oldThr;
 711         else {               // zero initial threshold signifies using defaults
 712             newCap = DEFAULT_INITIAL_CAPACITY;
 713             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 714         }
 715         if (newThr == 0) {
 716             float ft = (float)newCap * loadFactor;
 717             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
 718                       (int)ft : Integer.MAX_VALUE);
 719         }
 720         threshold = newThr;
 721 
 722         return createTableAndMoveElements(newCap, oldCap, oldTab);
 723     }
 724 
 725     private Node<K, V>[] createTableAndMoveElements(int newCap, int oldCap, Node<K, V>[] oldTab) {
 726         @SuppressWarnings({"rawtypes", "unchecked"})
 727         Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
 728         table = newTab;
 729         if (oldTab != null) {
 730             for (int j = 0; j < oldCap; ++j) {
 731                 Node<K, V> e;
 732                 if ((e = oldTab[j]) != null) {
 733                     oldTab[j] = null;
 734                     if (e.next == null) {
 735                         newTab[e.hash & (newCap - 1)] = e;
 736                     } else if (e instanceof TreeNode) {
 737                         ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
 738                     } else { // preserve order
 739                         Node<K, V> loHead = null, loTail = null;
 740                         Node<K, V> hiHead = null, hiTail = null;
 741                         Node<K, V> next;
 742                         do {
 743                             next = e.next;
 744                             if ((e.hash & oldCap) == 0) {
 745                                 if (loTail == null) {
 746                                     loHead = e;
 747                                 } else {
 748                                     loTail.next = e;

 749                                 }
 750                                 loTail = e;
 751                             } else {
 752                                 if (hiTail == null) {
 753                                     hiHead = e;
 754                                 } else {
 755                                     hiTail.next = e;
 756                                 }
 757                                 hiTail = e;
 758                             }
 759                         } while ((e = next) != null);
 760                         if (loTail != null) {
 761                             loTail.next = null;
 762                             newTab[j] = loHead;
 763                         }
 764                         if (hiTail != null) {
 765                             hiTail.next = null;
 766                             newTab[j + oldCap] = hiHead;
 767                         }
 768                     }
 769                 }
 770             }
 771         }
 772         return newTab;
 773     }
 774 
 775     /**
 776      * Replaces all linked nodes in bin at index for given hash unless


< prev index next >