HashMap_1.7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

 
     /**
      * An empty table instance to share when the table is not inflated.
      */
     static final Entry<?,?>[] EMPTY_TABLE = {};
 
     /**
      * The table, resized as necessary. Length MUST Always be a power of two.
      */
     transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

     static class Entry<K,V> implements Map.Entry<K,V> {
      final K key;
      V value;
      Entry<K,V> next;
      int hash;
      /**
       * Creates new entry.
       */
      Entry(int h, K k, V v, Entry<K,V> n) {
          value = v;
          next = n;
          key = k;
          hash = h;
      }

      public final K getKey() {
          return key;
      }

      public final V getValue() {
          return value;
      }

      public final V setValue(V newValue) {
          V oldValue = value;
          value = newValue;
          return oldValue;
      }

      public final boolean equals(Object o) {
          if (!(o instanceof Map.Entry))
              return false;
          Map.Entry e = (Map.Entry)o;
          Object k1 = getKey();
          Object k2 = e.getKey();
          if (k1 == k2 || (k1 != null && k1.equals(k2))) {
              Object v1 = getValue();
              Object v2 = e.getValue();
              if (v1 == v2 || (v1 != null && v1.equals(v2)))
                  return true;
          }
          return false;
      }

      public final int hashCode() {
          return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
      }

      public final String toString() {
          return getKey() + "=" + getValue();
      }

      /**
       * This method is invoked whenever the value in an entry is
       * overwritten by an invocation of put(k,v) for a key k that's already
       * in the HashMap.
       * 只要通过调用put（k，v）为已经在哈希映射中的键k覆盖条目中的值，就会调用此方法。
       */
      void recordAccess(HashMap<K,V> m) {
      }

      /**
       * This method is invoked whenever the entry is
       * removed from the table.
       * 每当从表中删除条目时，就会调用此方法
       */
      void recordRemoval(HashMap<K,V> m) {
      }
     } 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

 /**
  * The default initial capacity - MUST be a power of two.
  * 默认的初始容量 - 必须是2的幂。 1 << 4 等于2的4次方=16.
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 /**
  * The maximum capacity, used if a higher value is implicitly specified
  * by either of the constructors with arguments.
  * MUST be a power of two <= 1<<30.
  * 最大容量。 默认是2的30次方=1073741824
  */
 static final int MAXIMUM_CAPACITY = 1 << 30;

 /**
  * The load factor used when none specified in constructor.
  * 当构造函数中没有指定负载因子。就是使用默认负载因子
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  * An empty table instance to share when the table is not inflated.
  * 一个空表实例
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};

 /**
  * The table, resized as necessary. Length MUST Always be a power of two.
  * 表必要时调整大小。 长度必须始终是2的幂。
  */
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 /**
  * The number of key-value mappings contained in this map.
  */
 transient int size;

 /**
  * The next size value at which to resize (capacity * load factor).
  * 调整大小的下一个大小值（capacity * load factor）。
  * 如果table == EMPTY_TABLE，那么这时创建表的初始容量。
  * @serial
  */
 // If table == EMPTY_TABLE then this is the initial capacity at which the
 // table will be created when inflated.
 //门槛
 int threshold;

 /**
  * The load factor for the hash table.
  * 负载因子。
  * @serial
  */
 final float loadFactor;

 /**
  * The number of times this HashMap has been structurally modified
  * Structural modifications are those that change the number of mappings in
  * the HashMap or otherwise modify its internal structure (e.g.,
  * rehash).  This field is used to make iterators on Collection-views of
  * the HashMap fail-fast.  (See ConcurrentModificationException).
  * 修改次数 实现fail-fast机制
  */
 transient int modCount;

 /**
  * The default threshold of map capacity above which alternative hashing is
  * used for String keys. Alternative hashing reduces the incidence of
  * collisions due to weak hash code calculation for String keys.
  * Map容量的默认阈值高于该字符串键的替代哈希值。 由于String键的弱散列码计算，替代散列减少了冲突的发生率。
  * <p/>
  * This value may be overridden by defining the system property
  * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
  * forces alternative hashing to be used at all times whereas
  * {@code -1} value ensures that alternative hashing is never used.
  * 可以通过定义系统属性{@code jdk.map.althashing.threshold}来覆盖此值。 {@code 1}的属性值强制使用替代散列，而{@code -1}值确保不会使用替代散列。
  */
 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
 
 /**
  * holds values which can't be initialized until after VM is booted.
  */
 private static class Holder {

     /**
      * Table capacity above which to switch to use alternative hashing.
      * 保存在VM引导之后无法初始化的值。
      */
     static final int ALTERNATIVE_HASHING_THRESHOLD;

     static {
         String altThreshold = java.security.AccessController.doPrivileged(
             new sun.security.action.GetPropertyAction(
                 "jdk.map.althashing.threshold"));

         int threshold;
         try {
             threshold = (null != altThreshold)
                     ? Integer.parseInt(altThreshold)
                     : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

             // disable alternative hashing if -1
             if (threshold == -1) {
                 threshold = Integer.MAX_VALUE;
             }

             if (threshold < 0) {
                 throw new IllegalArgumentException("value must be positive integer.");
             }
         } catch(IllegalArgumentException failed) {
             throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
         }

         ALTERNATIVE_HASHING_THRESHOLD = threshold;
     }
 }

 /**
  * A randomizing value associated with this instance that is applied to
  * hash code of keys to make hash collisions harder to find. If 0 then
  * alternative hashing is disabled.
  * 与该实例相关联的随机化值应用于密钥的哈希码，以使哈希冲突更难找到。 如果0，则替代散列被禁用。
  */
 transient int hashSeed = 0;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and load factor.
   * 指定的初始容量和负载因子
   * @param  initialCapacity the initial capacity
   * @param  loadFactor      the load factor
   * @throws IllegalArgumentException if the initial capacity is negative
   *         or the load factor is nonpositive
   */
  public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);

      this.loadFactor = loadFactor;
      threshold = initialCapacity;
      init();
  }

  /**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and the default load factor (0.75).
   * 指定其容量大小，负载因子使用默认的0.75
   * @param  initialCapacity the initial capacity.
   * @throws IllegalArgumentException if the initial capacity is negative.
   */
  public HashMap(int initialCapacity) {
      this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

  /**
   * Constructs an empty <tt>HashMap</tt> with the default initial capacity
   * (16) and the default load factor (0.75).
   * 容量大小使用默认值16，负载因子使用默认值0.75
   */
  public HashMap() {
      this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }

  /**
   * Constructs a new <tt>HashMap</tt> with the same mappings as the
   * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
   * default load factor (0.75) and an initial capacity sufficient to
   * hold the mappings in the specified <tt>Map</tt>.
   * 使用与指定的 Map 相同的映射构造新的HashMap。HashMap使用默认负载因子（0.75）创建，初始容量足以将映射保存在指定的Map 中。
   * @param   m the map whose mappings are to be placed in this map
   * @throws  NullPointerException if the specified map is null
   */
  public HashMap(Map<? extends K, ? extends V> m) {
      this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                    DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
      inflateTable(threshold);

      putAllForCreate(m);
  }

  // internal utilities

  /**
   * Initialization hook for subclasses. This method is called
   * in all constructors and pseudo-constructors (clone, readObject)
   * after HashMap has been initialized but before any entries have
   * been inserted.  (In the absence of this method, readObject would
   * require explicit knowledge of subclasses.)
   * 子类的初始化钩子。
   */
  void init() {
  }

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

   /**
    * Retrieve object hash code and applies a supplemental hash function to the
    * result hash, which defends against poor quality hash functions.  This is
    * critical because HashMap uses power-of-two length hash tables, that
    * otherwise encounter collisions for hashCodes that do not differ
    * in lower bits. Note: Null keys always map to hash 0, thus index 0.
    * 检索对象哈希码，并将补充哈希函数应用于结果哈希，从而抵御不良品质的哈希函数。 这是至关重要的，
    * 因为HashMap使用二分之二长度的哈希表，否则会遇到低位不相同的hashCodes的冲突。 注意：空键总是映射到哈希值0，因此索引为0。
    */
   final int hash(Object k) {
       int h = hashSeed;
       /**如果key是字符串，调用un.misc.Hashing.stringHash32生成hash值*/
       if (0 != h && k instanceof String) {
           return sun.misc.Hashing.stringHash32((String) k);
       }

       h ^= k.hashCode();

       // This function ensures that hashCodes that differ only by
       // constant multiples at each bit position have a bounded
       // number of collisions (approximately 8 at default load factor).
       /**此函数确保每个位位置上仅有常数倍数不同的hashCode具有有界数量的冲突（默认负载系数约为8）。*/
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }

   /**
    * Returns index for hash code h.
    * 返回hash值的索引，采用除模取余法，h & (length-1)操作 等价于 hash % length操作， 但&操作性能更优
    */
   static int indexFor(int h, int length) {
       // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
       return h & (length-1);
   } 
  /**
    * Associates the specified value with the specified key in this map.
    * If the map previously contained a mapping for the key, the old
    * value is replaced.
    *Map存入一个简直对。如果Key存在，则替换
    * @param key key with which the specified value is to be associated
    * @param value value to be associated with the specified key
    * @return the previous value associated with <tt>key</tt>, or
    *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
    *         (A <tt>null</tt> return can also indicate that the map
    *         previously associated <tt>null</tt> with <tt>key</tt>.)
    */
   public V put(K key, V value) {
       /**如果table == EMPTY_TABLE，那么这时创建表的初始容量。*/
       if (table == EMPTY_TABLE) {
           inflateTable(threshold);
       }
       /**对key为null的键值对调用putForNullKey处理*/
       if (key == null)
           return putForNullKey(value);
       /**生成key hash值*/
       int hash = hash(key);
       /**获取数组hash值的索引*/
       int i = indexFor(hash, table.length);
       /**查找Key是否相等，则替换*/
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }

       modCount++;
       addEntry(hash, key, value, i);
       return null;
   }
   /**
    * Adds a new entry with the specified key, value and hash code to
    * the specified bucket.  It is the responsibility of this
    * method to resize the table if appropriate.
    * 将指定的键，值和哈希码的新条目添加到指定的存储桶。 如果适当，扩容。
    * Subclass overrides this to alter the behavior of put method.
    */
   void addEntry(int hash, K key, V value, int bucketIndex) {
       if ((size >= threshold) && (null != table[bucketIndex])) {
           //扩容 按2倍扩展
           resize(2 * table.length);
           hash = (null != key) ? hash(key) : 0;
           bucketIndex = indexFor(hash, table.length);
       }

       createEntry(hash, key, value, bucketIndex);
   }

   /**
    * Like addEntry except that this version is used when creating entries
    * as part of Map construction or "pseudo-construction" (cloning,
    * deserialization).  This version needn't worry about resizing the table.
    * 插入单链表表头
    * Subclass overrides this to alter the behavior of HashMap(Map),
    * clone, and readObject.
    */
   void createEntry(int hash, K key, V value, int bucketIndex) {
       Entry<K,V> e = table[bucketIndex];
       table[bucketIndex] = new Entry<>(hash, key, value, e);
       size++;
   }    

   /**
    * Offloaded version of put for null keys
    * 操作key为null键
    */
   private V putForNullKey(V value) {
       //查找key为null键，则替换
       for (Entry<K,V> e = table[0]; e != null; e = e.next) {
           if (e.key == null) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }
       modCount++;
       addEntry(0, null, value, 0);
       return null;
   }

   /**
    * This method is used instead of put by constructors and
    * pseudoconstructors (clone, readObject).  It does not resize the table,
    * check for comodification, etc.  It calls createEntry rather than
    * addEntry.
    * 使用这种方法代替构造函数和伪构造函数（clone，readObject）。 它不调整表的大小，检查comodification等。它调用createEntry而不是addEntry。
    */
   private void putForCreate(K key, V value) {
       int hash = null == key ? 0 : hash(key);
       int i = indexFor(hash, table.length);

       /**
        * Look for preexisting entry for key.  This will never happen for
        * clone or deserialize.  It will only happen for construction if the
        * input Map is a sorted map whose ordering is inconsistent w/ equals.
        * 查找Key是否相等，则替换
        */
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           if (e.hash == hash &&
               ((k = e.key) == key || (key != null && key.equals(k)))) {
               e.value = value;
               return;
           }
       }

       createEntry(hash, key, value, i);
   }
   
   /**
    * 指定Map集合添加到HashMap中
    */
   private void putAllForCreate(Map<? extends K, ? extends V> m) {
       for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
           putForCreate(e.getKey(), e.getValue());
   }
   
/**
    * Copies all of the mappings from the specified map to this map.
    * These mappings will replace any mappings that this map had for
    * any of the keys currently in the specified map.
    * 将指定Map集合复制目前Map。如果有存在相同key值，则替换。
    * @param m mappings to be stored in this map
    * @throws NullPointerException if the specified map is null
    */
   public void putAll(Map<? extends K, ? extends V> m) {
       int numKeysToBeAdded = m.size();
       if (numKeysToBeAdded == 0)
           return;
      /**如果table == EMPTY_TABLE，那么这时创建表的初始容量。*/
       if (table == EMPTY_TABLE) {
           inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
       }

       /*
        * Expand the map if the map if the number of mappings to be added
        * is greater than or equal to threshold.  This is conservative; the
        * obvious condition is (m.size() + size) >= threshold, but this
        * condition could result in a map with twice the appropriate capacity,
        * if the keys to be added overlap with the keys already in this map.
        * By using the conservative calculation, we subject ourself
        * to at most one extra resize.
        * 如果要添加的映射数大于或等于阈值，则展开映射。 这是保守的 明显的条件是（m.size（）+ size）> = threshold，
        * 但是如果要添加的键与已经在该映射中的键重叠，则此条件可能导致具有两倍相应容量的映射。 通过使用保守的计算，我们最多只能调整一次调整大小。
        */
       if (numKeysToBeAdded > threshold) {
           int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
           if (targetCapacity > MAXIMUM_CAPACITY)
               targetCapacity = MAXIMUM_CAPACITY;
           int newCapacity = table.length;
           while (newCapacity < targetCapacity)
               newCapacity <<= 1;
           if (newCapacity > table.length)
               resize(newCapacity);
       }

       for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
           put(e.getKey(), e.getValue());
   }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

  /**计算出number 2的n次方结果 number=6 计算出8*/
  private static int roundUpToPowerOf2(int number) {
      // assert number >= 0 : "number must be non-negative";
      return number >= MAXIMUM_CAPACITY
              ? MAXIMUM_CAPACITY
              : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
  }

  /**
   * Inflates the table.
   * put和putAll方法中 table == EMPTY_TABLE 创建初始化容量数组
   */
  private void inflateTable(int toSize) {
      // Find a power of 2 >= toSize
      int capacity = roundUpToPowerOf2(toSize);

      threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
      table = new Entry[capacity];
      initHashSeedAsNeeded(capacity);
  }
  /**
   * Initialize the hashing mask value. We defer initialization until we
   * really need it.
   * 初始化散列掩码值。 我们推迟初始化，直到我们真的需要它。
   */
  final boolean initHashSeedAsNeeded(int capacity) {
      boolean currentAltHashing = hashSeed != 0;
      boolean useAltHashing = sun.misc.VM.isBooted() &&
              (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
      boolean switching = currentAltHashing ^ useAltHashing;
      if (switching) {
          hashSeed = useAltHashing
              ? sun.misc.Hashing.randomHashSeed(this)
              : 0;
      }
      return switching;
  }    
  /**
   * Rehashes the contents of this map into a new array with a
   * larger capacity.  This method is called automatically when the
   * number of keys in this map reaches its threshold.
   *
   * If current capacity is MAXIMUM_CAPACITY, this method does not
   * resize the map, but sets threshold to Integer.MAX_VALUE.
   * This has the effect of preventing future calls.
   * 扩容
   * 将该Map的内容重新组合成具有较大容量的新阵列。 当该Map的键数达到其阈值时，将自动调用此方法。 
   * 如果当前容量为MAXIMUM_CAPACITY，则此方法不会调整映射大小，而是将阈值设置为Integer.MAX_VALUE。           
   * @param newCapacity the new capacity, MUST be a power of two;
   *        must be greater than current capacity unless current
   *        capacity is MAXIMUM_CAPACITY (in which case value
   *        is irrelevant).
   */
  void resize(int newCapacity) {
      Entry[] oldTable = table;
      int oldCapacity = oldTable.length;
      if (oldCapacity == MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return;
      }

      Entry[] newTable = new Entry[newCapacity];
      transfer(newTable, initHashSeedAsNeeded(newCapacity));
      table = newTable;
      /**重新计算阈值*/
      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  }

  /**
   * Transfers all entries from current table to newTable.
   * 将当前数组的数据传输到新数组中。
   */
  void transfer(Entry[] newTable, boolean rehash) {
      int newCapacity = newTable.length;
      for (Entry<K,V> e : table) {
          while(null != e) {
              Entry<K,V> next = e.next;
              if (rehash) {
                  e.hash = null == e.key ? 0 : hash(e.key);
              }
              /**重新获取数组hash值的索引*/
              int i = indexFor(e.hash, newCapacity);
              /**赋值新数组*/
              e.next = newTable[i];
              newTable[i] = e;
              e = next;
          }
      }
  }

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

  /**
   * Returns the value to which the specified key is mapped,
   * or {@code null} if this map contains no mapping for the key.
   *
   * <p>More formally, if this map contains a mapping from a key
   * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
   * key.equals(k))}, then this method returns {@code v}; otherwise
   * it returns {@code null}.  (There can be at most one such mapping.)
   *
   * <p>A return value of {@code null} does not <i>necessarily</i>
   * indicate that the map contains no mapping for the key; it's also
   * possible that the map explicitly maps the key to {@code null}.
   * The {@link #containsKey containsKey} operation may be used to
   * distinguish these two cases.
   *  返回指定key对应的value
   * @see #put(Object, Object)
   */
  public V get(Object key) {
      if (key == null)
          return getForNullKey();
      Entry<K,V> entry = getEntry(key);

      return null == entry ? null : entry.getValue();
  }

  /**
   * Offloaded version of get() to look up null keys.  Null keys map
   * to index 0.  This null case is split out into separate methods
   * for the sake of performance in the two most commonly used
   * operations (get and put), but incorporated with conditionals in
   * others.
   * 查找key为null的value，注意如果key为null，则其hash值为0，默认是放在table[0]里的
   */
  private V getForNullKey() {
      if (size == 0) {
          return null;
      }
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
          if (e.key == null)
              return e.value;
      }
      return null;
  }

  /**
   * Returns <tt>true</tt> if this map contains a mapping for the
   * specified key.
   * 判断是否包含指定的key
   * @param   key   The key whose presence in this map is to be tested
   * @return <tt>true</tt> if this map contains a mapping for the specified
   * key.
   */
  public boolean containsKey(Object key) {
      return getEntry(key) != null;
  }

  /**
   * Returns the entry associated with the specified key in the
   * HashMap.  Returns null if the HashMap contains no mapping
   * for the key.
   * 根据key查找键值对，找不到返回null
   */
  final Entry<K,V> getEntry(Object key) {
      if (size == 0) {
          return null;
      }
      /**如果key为null，hash值为0，否则调用hash方法，对key生成hash值*/
      int hash = (key == null) ? 0 : hash(key);
      /**调用indexFor方法生成hash值的索引，遍历该索引下的链表，查找key“相等”的键值对*/
      for (Entry<K,V> e = table[indexFor(hash, table.length)];
           e != null;
           e = e.next) {
          Object k;
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      }
      return null;
  }
  /**
   * Returns <tt>true</tt> if this map maps one or more keys to the
   * specified value.
   * 是否含有指定value的值
   * @param value value whose presence in this map is to be tested
   * @return <tt>true</tt> if this map maps one or more keys to the
   *         specified value
   */
  public boolean containsValue(Object value) {
      if (value == null)
          return containsNullValue();

      Entry[] tab = table;
      for (int i = 0; i < tab.length ; i++)
          for (Entry e = tab[i] ; e != null ; e = e.next)
              if (value.equals(e.value))
                  return true;
      return false;
  }

  /**
   * Special-case code for containsValue with null argument
   * 是否包含value为null值
   */
  private boolean containsNullValue() {
      Entry[] tab = table;
      for (int i = 0; i < tab.length ; i++)
          for (Entry e = tab[i] ; e != null ; e = e.next)
              if (e.value == null)
                  return true;
      return false;
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

  /**
   * Removes the mapping for the specified key from this map if present.
   * 如果存在从该Map中删除指定键的映射。
   * @param  key key whose mapping is to be removed from the map
   * @return the previous value associated with <tt>key</tt>, or
   *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
   *         (A <tt>null</tt> return can also indicate that the map
   *         previously associated <tt>null</tt> with <tt>key</tt>.)
   */
  public V remove(Object key) {
      Entry<K,V> e = removeEntryForKey(key);
      return (e == null ? null : e.value);
  }
  
  /**
   * Removes and returns the entry associated with the specified key
   * in the HashMap.  Returns null if the HashMap contains no mapping
   * for this key.
   * 删除并返回与HashMap中指定的键相关联的条目。 如果HashMap不包含此键的映射，则返回null。
   */
  final Entry<K,V> removeEntryForKey(Object key) {
      if (size == 0) {
          return null;
      }
      /**计算hash值及索引*/
      int hash = (key == null) ? 0 : hash(key);
      int i = indexFor(hash, table.length);
      Entry<K,V> prev = table[i];
      Entry<K,V> e = prev;

      while (e != null) {
          Entry<K,V> next = e.next;
          Object k;
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k)))) {
              modCount++;
              size--;
              if (prev == e)
                  table[i] = next;
              else
                  prev.next = next;
              e.recordRemoval(this);
              return e;
          }
          prev = e;
          e = next;
      }

      return e;
  }

  /**
   * Special version of remove for EntrySet using {@code Map.Entry.equals()}
   * for matching.
   * 使用{@code Map.Entry.equals（）}进行匹配的EntrySet的特殊版本的EntrySet。
   */
  final Entry<K,V> removeMapping(Object o) {
      if (size == 0 || !(o instanceof Map.Entry))
          return null;

      Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
      Object key = entry.getKey();
       /**计算hash值及索引*/
      int hash = (key == null) ? 0 : hash(key);
      int i = indexFor(hash, table.length);
      Entry<K,V> prev = table[i];
      Entry<K,V> e = prev;

      while (e != null) {
          Entry<K,V> next = e.next;
          if (e.hash == hash && e.equals(entry)) {
              modCount++;
              size--;
              if (prev == e)
                  table[i] = next;
              else
                  prev.next = next;
              e.recordRemoval(this);
              return e;
          }
          prev = e;
          e = next;
      }

      return e;
  }

  /**
   * Removes all of the mappings from this map.
   * The map will be empty after this call returns.
   * 清空map，将table数组所有元素设为null
   */
  public void clear() {
      modCount++;
      Arrays.fill(table, null);
      size = 0;
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

  private abstract class HashIterator<E> implements Iterator<E> {
      Entry<K,V> next;        // next entry to return
      int expectedModCount;   // For fast-fail
      /**当前Entry<K,V>[] table下标*/
      int index;              // current slot
      Entry<K,V> current;     // current entry

      HashIterator() {
          expectedModCount = modCount;
          if (size > 0) { // advance to first entry
              Entry[] t = table;
              /**查询Entry<K,V>[] table不为空Entry<K,V>。因为hash值定位数组下标，所有下标值不是连续，用查找方式查询值是否为null。*/
              while (index < t.length && (next = t[index++]) == null)
                  ;
          }
      }

      public final boolean hasNext() {
          return next != null;
      }

      final Entry<K,V> nextEntry() {
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
          Entry<K,V> e = next;
          if (e == null)
              throw new NoSuchElementException();
          /**链表next值是否为null,为空查询Entry<K,V>[] table数组*/
          if ((next = e.next) == null) {
              Entry[] t = table;
              while (index < t.length && (next = t[index++]) == null)
                  ;
          }
          current = e;
          return e;
      }

      public void remove() {
          if (current == null)
              throw new IllegalStateException();
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
          Object k = current.key;
          current = null;
          HashMap.this.removeEntryForKey(k);
          expectedModCount = modCount;
      }
  }
  /**value迭代器*/
  private final class ValueIterator extends HashIterator<V> {
      public V next() {
          return nextEntry().value;
      }
  }
   /**key迭代器*/
  private final class KeyIterator extends HashIterator<K> {
      public K next() {
          return nextEntry().getKey();
      }
  }
  /**Entry<K,V>对象迭代器*/
  private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
      public Map.Entry<K,V> next() {
          return nextEntry();
      }
  }

  // Subclass overrides these to alter behavior of views' iterator() method
  Iterator<K> newKeyIterator()   {
      return new KeyIterator();
  }
  Iterator<V> newValueIterator()   {
      return new ValueIterator();
  }
  Iterator<Map.Entry<K,V>> newEntryIterator()   {
      return new EntryIterator();
  }