1 /*
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
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
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
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 *
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 import java.io.*;
28
29 /**
30 * Hash table based implementation of the <tt>Map</tt> interface. This
31 * implementation provides all of the optional map operations, and permits
32 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
33 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
34 * unsynchronized and permits nulls.) This class makes no guarantees as to
35 * the order of the map; in particular, it does not guarantee that the order
36 * will remain constant over time.
37 *
38 * <p>This implementation provides constant-time performance for the basic
39 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
40 * disperses the elements properly among the buckets. Iteration over
41 * collection views requires time proportional to the "capacity" of the
42 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
43 * of key-value mappings). Thus, it's very important not to set the initial
44 * capacity too high (or the load factor too low) if iteration performance is
45 * important.
46 *
47 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
359 * <p>More formally, if this map contains a mapping from a key
360 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
361 * key.equals(k))}, then this method returns {@code v}; otherwise
362 * it returns {@code null}. (There can be at most one such mapping.)
363 *
364 * <p>A return value of {@code null} does not <i>necessarily</i>
365 * indicate that the map contains no mapping for the key; it's also
366 * possible that the map explicitly maps the key to {@code null}.
367 * The {@link #containsKey containsKey} operation may be used to
368 * distinguish these two cases.
369 *
370 * @see #put(Object, Object)
371 */
372 @SuppressWarnings("unchecked")
373 public V get(Object key) {
374 Entry<K,V> entry = getEntry(key);
375
376 return null == entry ? null : entry.getValue();
377 }
378
379 /**
380 * Returns <tt>true</tt> if this map contains a mapping for the
381 * specified key.
382 *
383 * @param key The key whose presence in this map is to be tested
384 * @return <tt>true</tt> if this map contains a mapping for the specified
385 * key.
386 */
387 public boolean containsKey(Object key) {
388 return getEntry(key) != null;
389 }
390
391 /**
392 * Returns the entry associated with the specified key in the
393 * HashMap. Returns null if the HashMap contains no mapping
394 * for the key.
395 */
396 @SuppressWarnings("unchecked")
397 final Entry<K,V> getEntry(Object key) {
398 if (isEmpty()) {
586 }
587
588 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
589 put(e.getKey(), e.getValue());
590 }
591
592 /**
593 * Removes the mapping for the specified key from this map if present.
594 *
595 * @param key key whose mapping is to be removed from the map
596 * @return the previous value associated with <tt>key</tt>, or
597 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
598 * (A <tt>null</tt> return can also indicate that the map
599 * previously associated <tt>null</tt> with <tt>key</tt>.)
600 */
601 public V remove(Object key) {
602 Entry<K,V> e = removeEntryForKey(key);
603 return (e == null ? null : e.value);
604 }
605
606 /**
607 * Removes and returns the entry associated with the specified key
608 * in the HashMap. Returns null if the HashMap contains no mapping
609 * for this key.
610 */
611 final Entry<K,V> removeEntryForKey(Object key) {
612 if (isEmpty()) {
613 return null;
614 }
615 int hash = (key == null) ? 0 : hash(key);
616 int i = indexFor(hash, table.length);
617 @SuppressWarnings("unchecked")
618 Entry<K,V> prev = (Entry<K,V>)table[i];
619 Entry<K,V> e = prev;
620
621 while (e != null) {
622 Entry<K,V> next = e.next;
623 Object k;
624 if (e.hash == hash &&
625 ((k = e.key) == key || (key != null && key.equals(k)))) {
680 */
681 public void clear() {
682 modCount++;
683 Arrays.fill(table, null);
684 size = 0;
685 }
686
687 /**
688 * Returns <tt>true</tt> if this map maps one or more keys to the
689 * specified value.
690 *
691 * @param value value whose presence in this map is to be tested
692 * @return <tt>true</tt> if this map maps one or more keys to the
693 * specified value
694 */
695 public boolean containsValue(Object value) {
696 if (value == null)
697 return containsNullValue();
698
699 Entry<?,?>[] tab = table;
700 for (int i = 0; i < tab.length ; i++)
701 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
702 if (value.equals(e.value))
703 return true;
704 return false;
705 }
706
707 /**
708 * Special-case code for containsValue with null argument
709 */
710 private boolean containsNullValue() {
711 Entry<?,?>[] tab = table;
712 for (int i = 0; i < tab.length ; i++)
713 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
714 if (e.value == null)
715 return true;
716 return false;
717 }
718
719 /**
720 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
721 * values themselves are not cloned.
722 *
723 * @return a shallow copy of this map
724 */
725 @SuppressWarnings("unchecked")
726 public Object clone() {
727 HashMap<K,V> result = null;
728 try {
729 result = (HashMap<K,V>)super.clone();
730 } catch (CloneNotSupportedException e) {
731 // assert false;
732 }
733 if (result.table != EMPTY_TABLE) {
|
1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
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
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
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 *
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.util.function.Consumer;
30 import java.util.function.BiFunction;
31 import java.util.function.Function;
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
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 */
376 @SuppressWarnings("unchecked")
377 public V get(Object key) {
378 Entry<K,V> entry = getEntry(key);
379
380 return null == entry ? null : entry.getValue();
381 }
382
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
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 */
407 @SuppressWarnings("unchecked")
408 final Entry<K,V> getEntry(Object key) {
409 if (isEmpty()) {
597 }
598
599 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
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
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
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) {
878 if (isEmpty()) {
879 return null;
880 }
881 int hash = (key == null) ? 0 : hash(key);
882 int i = indexFor(hash, table.length);
883 @SuppressWarnings("unchecked")
884 Entry<K,V> prev = (Entry<K,V>)table[i];
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)))) {
946 */
947 public void clear() {
948 modCount++;
949 Arrays.fill(table, null);
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
965 Entry<?,?>[] tab = table;
966 for (int i = 0; i < tab.length; i++)
967 for (Entry<?,?> e = tab[i]; e != null; e = e.next)
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() {
977 Entry<?,?>[] tab = table;
978 for (int i = 0; i < tab.length; i++)
979 for (Entry<?,?> e = tab[i]; e != null; e = e.next)
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 */
991 @SuppressWarnings("unchecked")
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 }
999 if (result.table != EMPTY_TABLE) {
|