Java JDK7源码-java.util.HashMap<K,V>

源码

1
package java.util;
2
import java.io.*;
3
4
public class HashMap<K,V>
5
    extends AbstractMap<K,V>
6
    implements Map<K,V>, Cloneable, Serializable
7
{
8
9
    /**
10
     * 默认的初始容量 - 必须是2的幂次方
11
     */
12
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
13
14
    /**
15
     * 最大容量
16
     * 当任意构造函数中指定的容量大于该值时,都将被减少为该值
17
     * 换句话说,容量需要是2的幂次方,且<= 2^30
18
     */
19
    static final int MAXIMUM_CAPACITY = 1 << 30;
20
21
    /**
22
     * 默认的加载因子值
23
     */
24
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
25
26
    /**
27
     * 当hashMap没有存入键值对时,所使用的默认的空表
28
     */
29
    static final Entry<?,?>[] EMPTY_TABLE = {};
30
31
    /**
32
     * 实际使用的,可依需求调整大小的存储桶的表
33
     * 该表的长度必须为2的幂次方
34
     */
35
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
36
37
    /**
38
     * map中存储的键值对个数
39
     */
40
    transient int size;
41
42
    /**
43
     * 下一次扩展时需扩展到的容量大小
44
     * 即:capacity * load factor
45
     * 若当前存储桶的数组为EMPTY_TABLE,即尚未存入键值对
46
     * 那么threshold等于预设的初始容量
47
     * @serial
48
     */
49
    int threshold;
50
51
    /**
52
     * 哈希表的加载因子
53
     * @serial
54
     */
55
    final float loadFactor;
56
57
    /**
58
     * hashMap发生结构性变化的次数
59
     * 所谓结构性变化,指得是改变键值对数目的变化,或是其他修改hashMap内部结构的变化(例如,rehash)
60
     * 本字段被hashMap的集合视图的iterator用于判断是否需要fail-fast(抛出ConcurrentModificationException)
61
     */
62
    transient int modCount;
63
64
    /**
65
     * 当针对
66
     * The default threshold of map capacity above which alternative hashing is
67
     * used for String keys. Alternative hashing reduces the incidence of
68
     * collisions due to weak hash code calculation for String keys.
69
     * <p/>
70
     * This value may be overridden by defining the system property
71
     * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
72
     * forces alternative hashing to be used at all times whereas
73
     * {@code -1} value ensures that alternative hashing is never used.
74
     */
75
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
76
77
    /**
78
     * holds values which can't be initialized until after VM is booted.
79
     */
80
    private static class Holder {
81
82
        /**
83
         * Table capacity above which to switch to use alternative hashing.
84
         */
85
        static final int ALTERNATIVE_HASHING_THRESHOLD;
86
87
        static {
88
            String altThreshold = java.security.AccessController.doPrivileged(
89
                new sun.security.action.GetPropertyAction(
90
                    "jdk.map.althashing.threshold"));
91
92
            int threshold;
93
            try {
94
                threshold = (null != altThreshold)
95
                        ? Integer.parseInt(altThreshold)
96
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
97
98
                // disable alternative hashing if -1
99
                if (threshold == -1) {
100
                    threshold = Integer.MAX_VALUE;
101
                }
102
103
                if (threshold < 0) {
104
                    throw new IllegalArgumentException("value must be positive integer.");
105
                }
106
            } catch(IllegalArgumentException failed) {
107
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
108
            }
109
110
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
111
        }
112
    }
113
114
    /**
115
     * A randomizing value associated with this instance that is applied to
116
     * hash code of keys to make hash collisions harder to find. If 0 then
117
     * alternative hashing is disabled.
118
     */
119
    transient int hashSeed = 0;
120
121
    /**
122
     * Constructs an empty <tt>HashMap</tt> with the specified initial
123
     * capacity and load factor.
124
     *
125
     * @param  initialCapacity the initial capacity
126
     * @param  loadFactor      the load factor
127
     * @throws IllegalArgumentException if the initial capacity is negative
128
     *         or the load factor is nonpositive
129
     */
130
    public HashMap(int initialCapacity, float loadFactor) {
131
        if (initialCapacity < 0)
132
            throw new IllegalArgumentException("Illegal initial capacity: " +
133
                                               initialCapacity);
134
        if (initialCapacity > MAXIMUM_CAPACITY)
135
            initialCapacity = MAXIMUM_CAPACITY;
136
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
137
            throw new IllegalArgumentException("Illegal load factor: " +
138
                                               loadFactor);
139
140
        this.loadFactor = loadFactor;
141
        threshold = initialCapacity;
142
        init();
143
    }
144
145
    /**
146
     * Constructs an empty <tt>HashMap</tt> with the specified initial
147
     * capacity and the default load factor (0.75).
148
     *
149
     * @param  initialCapacity the initial capacity.
150
     * @throws IllegalArgumentException if the initial capacity is negative.
151
     */
152
    public HashMap(int initialCapacity) {
153
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
154
    }
155
156
    /**
157
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
158
     * (16) and the default load factor (0.75).
159
     */
160
    public HashMap() {
161
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
162
    }
163
164
    /**
165
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
166
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
167
     * default load factor (0.75) and an initial capacity sufficient to
168
     * hold the mappings in the specified <tt>Map</tt>.
169
     *
170
     * @param   m the map whose mappings are to be placed in this map
171
     * @throws  NullPointerException if the specified map is null
172
     */
173
    public HashMap(Map<? extends K, ? extends V> m) {
174
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
175
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
176
        inflateTable(threshold);
177
178
        putAllForCreate(m);
179
    }
180
181
    private static int roundUpToPowerOf2(int number) {
182
        // assert number >= 0 : "number must be non-negative";
183
        return number >= MAXIMUM_CAPACITY
184
                ? MAXIMUM_CAPACITY
185
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
186
    }
187
188
    /**
189
     * Inflates the table.
190
     */
191
    private void inflateTable(int toSize) {
192
        // Find a power of 2 >= toSize
193
        int capacity = roundUpToPowerOf2(toSize);
194
195
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
196
        table = new Entry[capacity];
197
        initHashSeedAsNeeded(capacity);
198
    }
199
200
    // internal utilities
201
202
    /**
203
     * Initialization hook for subclasses. This method is called
204
     * in all constructors and pseudo-constructors (clone, readObject)
205
     * after HashMap has been initialized but before any entries have
206
     * been inserted.  (In the absence of this method, readObject would
207
     * require explicit knowledge of subclasses.)
208
     */
209
    void init() {
210
    }
211
212
    /**
213
     * Initialize the hashing mask value. We defer initialization until we
214
     * really need it.
215
     */
216
    final boolean initHashSeedAsNeeded(int capacity) {
217
        boolean currentAltHashing = hashSeed != 0;
218
        boolean useAltHashing = sun.misc.VM.isBooted() &&
219
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
220
        boolean switching = currentAltHashing ^ useAltHashing;
221
        if (switching) {
222
            hashSeed = useAltHashing
223
                ? sun.misc.Hashing.randomHashSeed(this)
224
                : 0;
225
        }
226
        return switching;
227
    }
228
229
    /**
230
     * Retrieve object hash code and applies a supplemental hash function to the
231
     * result hash, which defends against poor quality hash functions.  This is
232
     * critical because HashMap uses power-of-two length hash tables, that
233
     * otherwise encounter collisions for hashCodes that do not differ
234
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
235
     */
236
    final int hash(Object k) {
237
        int h = hashSeed;
238
        if (0 != h && k instanceof String) {
239
            return sun.misc.Hashing.stringHash32((String) k);
240
        }
241
242
        h ^= k.hashCode();
243
244
        // This function ensures that hashCodes that differ only by
245
        // constant multiples at each bit position have a bounded
246
        // number of collisions (approximately 8 at default load factor).
247
        h ^= (h >>> 20) ^ (h >>> 12);
248
        return h ^ (h >>> 7) ^ (h >>> 4);
249
    }
250
251
    /**
252
     * Returns index for hash code h.
253
     */
254
    static int indexFor(int h, int length) {
255
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
256
        return h & (length-1);
257
    }
258
259
    /**
260
     * Returns the number of key-value mappings in this map.
261
     *
262
     * @return the number of key-value mappings in this map
263
     */
264
    public int size() {
265
        return size;
266
    }
267
268
    /**
269
     * Returns <tt>true</tt> if this map contains no key-value mappings.
270
     *
271
     * @return <tt>true</tt> if this map contains no key-value mappings
272
     */
273
    public boolean isEmpty() {
274
        return size == 0;
275
    }
276
277
    /**
278
     * Returns the value to which the specified key is mapped,
279
     * or {@code null} if this map contains no mapping for the key.
280
     *
281
     * <p>More formally, if this map contains a mapping from a key
282
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
283
     * key.equals(k))}, then this method returns {@code v}; otherwise
284
     * it returns {@code null}.  (There can be at most one such mapping.)
285
     *
286
     * <p>A return value of {@code null} does not <i>necessarily</i>
287
     * indicate that the map contains no mapping for the key; it's also
288
     * possible that the map explicitly maps the key to {@code null}.
289
     * The {@link #containsKey containsKey} operation may be used to
290
     * distinguish these two cases.
291
     *
292
     * @see #put(Object, Object)
293
     */
294
    public V get(Object key) {
295
        if (key == null)
296
            return getForNullKey();
297
        Entry<K,V> entry = getEntry(key);
298
299
        return null == entry ? null : entry.getValue();
300
    }
301
302
    /**
303
     * Offloaded version of get() to look up null keys.  Null keys map
304
     * to index 0.  This null case is split out into separate methods
305
     * for the sake of performance in the two most commonly used
306
     * operations (get and put), but incorporated with conditionals in
307
     * others.
308
     */
309
    private V getForNullKey() {
310
        if (size == 0) {
311
            return null;
312
        }
313
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
314
            if (e.key == null)
315
                return e.value;
316
        }
317
        return null;
318
    }
319
320
    /**
321
     * Returns <tt>true</tt> if this map contains a mapping for the
322
     * specified key.
323
     *
324
     * @param   key   The key whose presence in this map is to be tested
325
     * @return <tt>true</tt> if this map contains a mapping for the specified
326
     * key.
327
     */
328
    public boolean containsKey(Object key) {
329
        return getEntry(key) != null;
330
    }
331
332
    /**
333
     * Returns the entry associated with the specified key in the
334
     * HashMap.  Returns null if the HashMap contains no mapping
335
     * for the key.
336
     */
337
    final Entry<K,V> getEntry(Object key) {
338
        if (size == 0) {
339
            return null;
340
        }
341
342
        int hash = (key == null) ? 0 : hash(key);
343
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
344
             e != null;
345
             e = e.next) {
346
            Object k;
347
            if (e.hash == hash &&
348
                ((k = e.key) == key || (key != null && key.equals(k))))
349
                return e;
350
        }
351
        return null;
352
    }
353
354
    /**
355
     * Associates the specified value with the specified key in this map.
356
     * If the map previously contained a mapping for the key, the old
357
     * value is replaced.
358
     *
359
     * @param key key with which the specified value is to be associated
360
     * @param value value to be associated with the specified key
361
     * @return the previous value associated with <tt>key</tt>, or
362
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
363
     *         (A <tt>null</tt> return can also indicate that the map
364
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
365
     */
366
    public V put(K key, V value) {
367
        if (table == EMPTY_TABLE) {
368
            inflateTable(threshold);
369
        }
370
        if (key == null)
371
            return putForNullKey(value);
372
        int hash = hash(key);
373
        int i = indexFor(hash, table.length);
374
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
375
            Object k;
376
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
377
                V oldValue = e.value;
378
                e.value = value;
379
                e.recordAccess(this);
380
                return oldValue;
381
            }
382
        }
383
384
        modCount++;
385
        addEntry(hash, key, value, i);
386
        return null;
387
    }
388
389
    /**
390
     * Offloaded version of put for null keys
391
     */
392
    private V putForNullKey(V value) {
393
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
394
            if (e.key == null) {
395
                V oldValue = e.value;
396
                e.value = value;
397
                e.recordAccess(this);
398
                return oldValue;
399
            }
400
        }
401
        modCount++;
402
        addEntry(0, null, value, 0);
403
        return null;
404
    }
405
406
    /**
407
     * This method is used instead of put by constructors and
408
     * pseudoconstructors (clone, readObject).  It does not resize the table,
409
     * check for comodification, etc.  It calls createEntry rather than
410
     * addEntry.
411
     */
412
    private void putForCreate(K key, V value) {
413
        int hash = null == key ? 0 : hash(key);
414
        int i = indexFor(hash, table.length);
415
416
        /**
417
         * Look for preexisting entry for key.  This will never happen for
418
         * clone or deserialize.  It will only happen for construction if the
419
         * input Map is a sorted map whose ordering is inconsistent w/ equals.
420
         */
421
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
422
            Object k;
423
            if (e.hash == hash &&
424
                ((k = e.key) == key || (key != null && key.equals(k)))) {
425
                e.value = value;
426
                return;
427
            }
428
        }
429
430
        createEntry(hash, key, value, i);
431
    }
432
433
    private void putAllForCreate(Map<? extends K, ? extends V> m) {
434
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
435
            putForCreate(e.getKey(), e.getValue());
436
    }
437
438
    /**
439
     * Rehashes the contents of this map into a new array with a
440
     * larger capacity.  This method is called automatically when the
441
     * number of keys in this map reaches its threshold.
442
     *
443
     * If current capacity is MAXIMUM_CAPACITY, this method does not
444
     * resize the map, but sets threshold to Integer.MAX_VALUE.
445
     * This has the effect of preventing future calls.
446
     *
447
     * @param newCapacity the new capacity, MUST be a power of two;
448
     *        must be greater than current capacity unless current
449
     *        capacity is MAXIMUM_CAPACITY (in which case value
450
     *        is irrelevant).
451
     */
452
    void resize(int newCapacity) {
453
        Entry[] oldTable = table;
454
        int oldCapacity = oldTable.length;
455
        if (oldCapacity == MAXIMUM_CAPACITY) {
456
            threshold = Integer.MAX_VALUE;
457
            return;
458
        }
459
460
        Entry[] newTable = new Entry[newCapacity];
461
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
462
        table = newTable;
463
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
464
    }
465
466
    /**
467
     * Transfers all entries from current table to newTable.
468
     */
469
    void transfer(Entry[] newTable, boolean rehash) {
470
        int newCapacity = newTable.length;
471
        for (Entry<K,V> e : table) {
472
            while(null != e) {
473
                Entry<K,V> next = e.next;
474
                if (rehash) {
475
                    e.hash = null == e.key ? 0 : hash(e.key);
476
                }
477
                int i = indexFor(e.hash, newCapacity);
478
                e.next = newTable[i];
479
                newTable[i] = e;
480
                e = next;
481
            }
482
        }
483
    }
484
485
    /**
486
     * Copies all of the mappings from the specified map to this map.
487
     * These mappings will replace any mappings that this map had for
488
     * any of the keys currently in the specified map.
489
     *
490
     * @param m mappings to be stored in this map
491
     * @throws NullPointerException if the specified map is null
492
     */
493
    public void putAll(Map<? extends K, ? extends V> m) {
494
        int numKeysToBeAdded = m.size();
495
        if (numKeysToBeAdded == 0)
496
            return;
497
498
        if (table == EMPTY_TABLE) {
499
            inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
500
        }
501
502
        /*
503
         * Expand the map if the map if the number of mappings to be added
504
         * is greater than or equal to threshold.  This is conservative; the
505
         * obvious condition is (m.size() + size) >= threshold, but this
506
         * condition could result in a map with twice the appropriate capacity,
507
         * if the keys to be added overlap with the keys already in this map.
508
         * By using the conservative calculation, we subject ourself
509
         * to at most one extra resize.
510
         */
511
        if (numKeysToBeAdded > threshold) {
512
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
513
            if (targetCapacity > MAXIMUM_CAPACITY)
514
                targetCapacity = MAXIMUM_CAPACITY;
515
            int newCapacity = table.length;
516
            while (newCapacity < targetCapacity)
517
                newCapacity <<= 1;
518
            if (newCapacity > table.length)
519
                resize(newCapacity);
520
        }
521
522
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
523
            put(e.getKey(), e.getValue());
524
    }
525
526
    /**
527
     * Removes the mapping for the specified key from this map if present.
528
     *
529
     * @param  key key whose mapping is to be removed from the map
530
     * @return the previous value associated with <tt>key</tt>, or
531
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
532
     *         (A <tt>null</tt> return can also indicate that the map
533
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
534
     */
535
    public V remove(Object key) {
536
        Entry<K,V> e = removeEntryForKey(key);
537
        return (e == null ? null : e.value);
538
    }
539
540
    /**
541
     * Removes and returns the entry associated with the specified key
542
     * in the HashMap.  Returns null if the HashMap contains no mapping
543
     * for this key.
544
     */
545
    final Entry<K,V> removeEntryForKey(Object key) {
546
        if (size == 0) {
547
            return null;
548
        }
549
        int hash = (key == null) ? 0 : hash(key);
550
        int i = indexFor(hash, table.length);
551
        Entry<K,V> prev = table[i];
552
        Entry<K,V> e = prev;
553
554
        while (e != null) {
555
            Entry<K,V> next = e.next;
556
            Object k;
557
            if (e.hash == hash &&
558
                ((k = e.key) == key || (key != null && key.equals(k)))) {
559
                modCount++;
560
                size--;
561
                if (prev == e)
562
                    table[i] = next;
563
                else
564
                    prev.next = next;
565
                e.recordRemoval(this);
566
                return e;
567
            }
568
            prev = e;
569
            e = next;
570
        }
571
572
        return e;
573
    }
574
575
    /**
576
     * Special version of remove for EntrySet using {@code Map.Entry.equals()}
577
     * for matching.
578
     */
579
    final Entry<K,V> removeMapping(Object o) {
580
        if (size == 0 || !(o instanceof Map.Entry))
581
            return null;
582
583
        Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
584
        Object key = entry.getKey();
585
        int hash = (key == null) ? 0 : hash(key);
586
        int i = indexFor(hash, table.length);
587
        Entry<K,V> prev = table[i];
588
        Entry<K,V> e = prev;
589
590
        while (e != null) {
591
            Entry<K,V> next = e.next;
592
            if (e.hash == hash && e.equals(entry)) {
593
                modCount++;
594
                size--;
595
                if (prev == e)
596
                    table[i] = next;
597
                else
598
                    prev.next = next;
599
                e.recordRemoval(this);
600
                return e;
601
            }
602
            prev = e;
603
            e = next;
604
        }
605
606
        return e;
607
    }
608
609
    /**
610
     * Removes all of the mappings from this map.
611
     * The map will be empty after this call returns.
612
     */
613
    public void clear() {
614
        modCount++;
615
        Arrays.fill(table, null);
616
        size = 0;
617
    }
618
619
    /**
620
     * Returns <tt>true</tt> if this map maps one or more keys to the
621
     * specified value.
622
     *
623
     * @param value value whose presence in this map is to be tested
624
     * @return <tt>true</tt> if this map maps one or more keys to the
625
     *         specified value
626
     */
627
    public boolean containsValue(Object value) {
628
        if (value == null)
629
            return containsNullValue();
630
631
        Entry[] tab = table;
632
        for (int i = 0; i < tab.length ; i++)
633
            for (Entry e = tab[i] ; e != null ; e = e.next)
634
                if (value.equals(e.value))
635
                    return true;
636
        return false;
637
    }
638
639
    /**
640
     * Special-case code for containsValue with null argument
641
     */
642
    private boolean containsNullValue() {
643
        Entry[] tab = table;
644
        for (int i = 0; i < tab.length ; i++)
645
            for (Entry e = tab[i] ; e != null ; e = e.next)
646
                if (e.value == null)
647
                    return true;
648
        return false;
649
    }
650
651
    /**
652
     * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
653
     * values themselves are not cloned.
654
     *
655
     * @return a shallow copy of this map
656
     */
657
    public Object clone() {
658
        HashMap<K,V> result = null;
659
        try {
660
            result = (HashMap<K,V>)super.clone();
661
        } catch (CloneNotSupportedException e) {
662
            // assert false;
663
        }
664
        if (result.table != EMPTY_TABLE) {
665
            result.inflateTable(Math.min(
666
                (int) Math.min(
667
                    size * Math.min(1 / loadFactor, 4.0f),
668
                    // we have limits...
669
                    HashMap.MAXIMUM_CAPACITY),
670
               table.length));
671
        }
672
        result.entrySet = null;
673
        result.modCount = 0;
674
        result.size = 0;
675
        result.init();
676
        result.putAllForCreate(this);
677
678
        return result;
679
    }
680
681
    static class Entry<K,V> implements Map.Entry<K,V> {
682
        final K key;
683
        V value;
684
        Entry<K,V> next;
685
        int hash;
686
687
        /**
688
         * Creates new entry.
689
         */
690
        Entry(int h, K k, V v, Entry<K,V> n) {
691
            value = v;
692
            next = n;
693
            key = k;
694
            hash = h;
695
        }
696
697
        public final K getKey() {
698
            return key;
699
        }
700
701
        public final V getValue() {
702
            return value;
703
        }
704
705
        public final V setValue(V newValue) {
706
            V oldValue = value;
707
            value = newValue;
708
            return oldValue;
709
        }
710
711
        public final boolean equals(Object o) {
712
            if (!(o instanceof Map.Entry))
713
                return false;
714
            Map.Entry e = (Map.Entry)o;
715
            Object k1 = getKey();
716
            Object k2 = e.getKey();
717
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
718
                Object v1 = getValue();
719
                Object v2 = e.getValue();
720
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
721
                    return true;
722
            }
723
            return false;
724
        }
725
726
        public final int hashCode() {
727
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
728
        }
729
730
        public final String toString() {
731
            return getKey() + "=" + getValue();
732
        }
733
734
        /**
735
         * This method is invoked whenever the value in an entry is
736
         * overwritten by an invocation of put(k,v) for a key k that's already
737
         * in the HashMap.
738
         */
739
        void recordAccess(HashMap<K,V> m) {
740
        }
741
742
        /**
743
         * This method is invoked whenever the entry is
744
         * removed from the table.
745
         */
746
        void recordRemoval(HashMap<K,V> m) {
747
        }
748
    }
749
750
    /**
751
     * Adds a new entry with the specified key, value and hash code to
752
     * the specified bucket.  It is the responsibility of this
753
     * method to resize the table if appropriate.
754
     *
755
     * Subclass overrides this to alter the behavior of put method.
756
     */
757
    void addEntry(int hash, K key, V value, int bucketIndex) {
758
        if ((size >= threshold) && (null != table[bucketIndex])) {
759
            resize(2 * table.length);
760
            hash = (null != key) ? hash(key) : 0;
761
            bucketIndex = indexFor(hash, table.length);
762
        }
763
764
        createEntry(hash, key, value, bucketIndex);
765
    }
766
767
    /**
768
     * Like addEntry except that this version is used when creating entries
769
     * as part of Map construction or "pseudo-construction" (cloning,
770
     * deserialization).  This version needn't worry about resizing the table.
771
     *
772
     * Subclass overrides this to alter the behavior of HashMap(Map),
773
     * clone, and readObject.
774
     */
775
    void createEntry(int hash, K key, V value, int bucketIndex) {
776
        Entry<K,V> e = table[bucketIndex];
777
        table[bucketIndex] = new Entry<>(hash, key, value, e);
778
        size++;
779
    }
780
781
    private abstract class HashIterator<E> implements Iterator<E> {
782
        Entry<K,V> next;        // next entry to return
783
        int expectedModCount;   // For fast-fail
784
        int index;              // current slot
785
        Entry<K,V> current;     // current entry
786
787
        HashIterator() {
788
            expectedModCount = modCount;
789
            if (size > 0) { // advance to first entry
790
                Entry[] t = table;
791
                while (index < t.length && (next = t[index++]) == null)
792
                    ;
793
            }
794
        }
795
796
        public final boolean hasNext() {
797
            return next != null;
798
        }
799
800
        final Entry<K,V> nextEntry() {
801
            if (modCount != expectedModCount)
802
                throw new ConcurrentModificationException();
803
            Entry<K,V> e = next;
804
            if (e == null)
805
                throw new NoSuchElementException();
806
807
            if ((next = e.next) == null) {
808
                Entry[] t = table;
809
                while (index < t.length && (next = t[index++]) == null)
810
                    ;
811
            }
812
            current = e;
813
            return e;
814
        }
815
816
        public void remove() {
817
            if (current == null)
818
                throw new IllegalStateException();
819
            if (modCount != expectedModCount)
820
                throw new ConcurrentModificationException();
821
            Object k = current.key;
822
            current = null;
823
            HashMap.this.removeEntryForKey(k);
824
            expectedModCount = modCount;
825
        }
826
    }
827
828
    private final class ValueIterator extends HashIterator<V> {
829
        public V next() {
830
            return nextEntry().value;
831
        }
832
    }
833
834
    private final class KeyIterator extends HashIterator<K> {
835
        public K next() {
836
            return nextEntry().getKey();
837
        }
838
    }
839
840
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
841
        public Map.Entry<K,V> next() {
842
            return nextEntry();
843
        }
844
    }
845
846
    // Subclass overrides these to alter behavior of views' iterator() method
847
    Iterator<K> newKeyIterator()   {
848
        return new KeyIterator();
849
    }
850
    Iterator<V> newValueIterator()   {
851
        return new ValueIterator();
852
    }
853
    Iterator<Map.Entry<K,V>> newEntryIterator()   {
854
        return new EntryIterator();
855
    }
856
857
858
    // Views
859
860
    private transient Set<Map.Entry<K,V>> entrySet = null;
861
862
    /**
863
     * Returns a {@link Set} view of the keys contained in this map.
864
     * The set is backed by the map, so changes to the map are
865
     * reflected in the set, and vice-versa.  If the map is modified
866
     * while an iteration over the set is in progress (except through
867
     * the iterator's own <tt>remove</tt> operation), the results of
868
     * the iteration are undefined.  The set supports element removal,
869
     * which removes the corresponding mapping from the map, via the
870
     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
871
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
872
     * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
873
     * operations.
874
     */
875
    public Set<K> keySet() {
876
        Set<K> ks = keySet;
877
        return (ks != null ? ks : (keySet = new KeySet()));
878
    }
879
880
    private final class KeySet extends AbstractSet<K> {
881
        public Iterator<K> iterator() {
882
            return newKeyIterator();
883
        }
884
        public int size() {
885
            return size;
886
        }
887
        public boolean contains(Object o) {
888
            return containsKey(o);
889
        }
890
        public boolean remove(Object o) {
891
            return HashMap.this.removeEntryForKey(o) != null;
892
        }
893
        public void clear() {
894
            HashMap.this.clear();
895
        }
896
    }
897
898
    /**
899
     * Returns a {@link Collection} view of the values contained in this map.
900
     * The collection is backed by the map, so changes to the map are
901
     * reflected in the collection, and vice-versa.  If the map is
902
     * modified while an iteration over the collection is in progress
903
     * (except through the iterator's own <tt>remove</tt> operation),
904
     * the results of the iteration are undefined.  The collection
905
     * supports element removal, which removes the corresponding
906
     * mapping from the map, via the <tt>Iterator.remove</tt>,
907
     * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
908
     * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
909
     * support the <tt>add</tt> or <tt>addAll</tt> operations.
910
     */
911
    public Collection<V> values() {
912
        Collection<V> vs = values;
913
        return (vs != null ? vs : (values = new Values()));
914
    }
915
916
    private final class Values extends AbstractCollection<V> {
917
        public Iterator<V> iterator() {
918
            return newValueIterator();
919
        }
920
        public int size() {
921
            return size;
922
        }
923
        public boolean contains(Object o) {
924
            return containsValue(o);
925
        }
926
        public void clear() {
927
            HashMap.this.clear();
928
        }
929
    }
930
931
    /**
932
     * Returns a {@link Set} view of the mappings contained in this map.
933
     * The set is backed by the map, so changes to the map are
934
     * reflected in the set, and vice-versa.  If the map is modified
935
     * while an iteration over the set is in progress (except through
936
     * the iterator's own <tt>remove</tt> operation, or through the
937
     * <tt>setValue</tt> operation on a map entry returned by the
938
     * iterator) the results of the iteration are undefined.  The set
939
     * supports element removal, which removes the corresponding
940
     * mapping from the map, via the <tt>Iterator.remove</tt>,
941
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
942
     * <tt>clear</tt> operations.  It does not support the
943
     * <tt>add</tt> or <tt>addAll</tt> operations.
944
     *
945
     * @return a set view of the mappings contained in this map
946
     */
947
    public Set<Map.Entry<K,V>> entrySet() {
948
        return entrySet0();
949
    }
950
951
    private Set<Map.Entry<K,V>> entrySet0() {
952
        Set<Map.Entry<K,V>> es = entrySet;
953
        return es != null ? es : (entrySet = new EntrySet());
954
    }
955
956
    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
957
        public Iterator<Map.Entry<K,V>> iterator() {
958
            return newEntryIterator();
959
        }
960
        public boolean contains(Object o) {
961
            if (!(o instanceof Map.Entry))
962
                return false;
963
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;
964
            Entry<K,V> candidate = getEntry(e.getKey());
965
            return candidate != null && candidate.equals(e);
966
        }
967
        public boolean remove(Object o) {
968
            return removeMapping(o) != null;
969
        }
970
        public int size() {
971
            return size;
972
        }
973
        public void clear() {
974
            HashMap.this.clear();
975
        }
976
    }
977
978
    /**
979
     * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
980
     * serialize it).
981
     *
982
     * @serialData The <i>capacity</i> of the HashMap (the length of the
983
     *             bucket array) is emitted (int), followed by the
984
     *             <i>size</i> (an int, the number of key-value
985
     *             mappings), followed by the key (Object) and value (Object)
986
     *             for each key-value mapping.  The key-value mappings are
987
     *             emitted in no particular order.
988
     */
989
    private void writeObject(java.io.ObjectOutputStream s)
990
        throws IOException
991
    {
992
        // Write out the threshold, loadfactor, and any hidden stuff
993
        s.defaultWriteObject();
994
995
        // Write out number of buckets
996
        if (table==EMPTY_TABLE) {
997
            s.writeInt(roundUpToPowerOf2(threshold));
998
        } else {
999
           s.writeInt(table.length);
1000
        }
1001
1002
        // Write out size (number of Mappings)
1003
        s.writeInt(size);
1004
1005
        // Write out keys and values (alternating)
1006
        if (size > 0) {
1007
            for(Map.Entry<K,V> e : entrySet0()) {
1008
                s.writeObject(e.getKey());
1009
                s.writeObject(e.getValue());
1010
            }
1011
        }
1012
    }
1013
1014
    private static final long serialVersionUID = 362498820763181265L;
1015
1016
    /**
1017
     * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1018
     * deserialize it).
1019
     */
1020
    private void readObject(java.io.ObjectInputStream s)
1021
         throws IOException, ClassNotFoundException
1022
    {
1023
        // Read in the threshold (ignored), loadfactor, and any hidden stuff
1024
        s.defaultReadObject();
1025
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
1026
            throw new InvalidObjectException("Illegal load factor: " +
1027
                                               loadFactor);
1028
        }
1029
1030
        // set other fields that need values
1031
        table = (Entry<K,V>[]) EMPTY_TABLE;
1032
1033
        // Read in number of buckets
1034
        s.readInt(); // ignored.
1035
1036
        // Read number of mappings
1037
        int mappings = s.readInt();
1038
        if (mappings < 0)
1039
            throw new InvalidObjectException("Illegal mappings count: " +
1040
                                               mappings);
1041
1042
        // capacity chosen by number of mappings and desired load (if >= 0.25)
1043
        int capacity = (int) Math.min(
1044
                    mappings * Math.min(1 / loadFactor, 4.0f),
1045
                    // we have limits...
1046
                    HashMap.MAXIMUM_CAPACITY);
1047
1048
        // allocate the bucket array;
1049
        if (mappings > 0) {
1050
            inflateTable(capacity);
1051
        } else {
1052
            threshold = capacity;
1053
        }
1054
1055
        init();  // Give subclass a chance to do its thing.
1056
1057
        // Read the keys and values, and put the mappings in the HashMap
1058
        for (int i = 0; i < mappings; i++) {
1059
            K key = (K) s.readObject();
1060
            V value = (V) s.readObject();
1061
            putForCreate(key, value);
1062
        }
1063
    }
1064
1065
    // These methods are used when serializing HashSets
1066
    int   capacity()     { return table.length; }
1067
    float loadFactor()   { return loadFactor;   }
1068
}

已整理层级关系

本类直接继承的类

本类直接实现的接口

综述

本类是Java集合框架中的一员。其中K,V分别是map中key与value的类型。

哈希表是Map接口的实现类,本实现提供了所有可选的map操作,并允许key或value为null(除了线程不安全及允许key或value为null外,HashMap可以被粗略的看作哈希表[Hash table])。

本类不保证map中的元素的有序性。特别的,本类不会保证map中的元素的顺序随着时间的推移是不变的。

如果所用的哈希函数将元素分散到了适当的桶中,对于基本操作而言(也就是get和put),本实现的时间复杂度为常数阶。

迭代本实现集合视图所需的时间与以下内容正相关:

hashMap的”容量”(桶的个数) 及 hashMap的size(键值对的个数)。

因此如果对迭代的性能比较看重,就不能将初始容量设置得过高(或将加载因子设置得过低)。

影响hashMap性能的参数有两个:

  1. 初始容量(initial capacity): 所谓容量,就是指哈希表中的桶的数量,而初始容量,顾名思义,自然就是哈希表在创建时的容量。
  2. 加载因子(load factor): 哈希表装得多满时需要自动扩展的阀值。例如若加载因子为l,当前容量为c,则当entry(即键值对)数超过l*c时,哈希表就需要进行一次重构(rehashed),以扩展自身的容量。重构完成后,哈希表中的容量,或者说是桶数,会大致扩展为原值的两倍。

本实现中,加载因子的默认值为0.75,该值是时间消耗及空间消耗平衡后的结果。加大加载因子降低了空间消耗,但却增大了查找耗时(包括get及put在内,hashMap绝大多数的操作均遵循这个规律)。为了最小化重构操作的次数,在设定hashMap的初始容量时需考虑预期的键值对个数及加载因子的值。如果初始容量与加载因子的乘积大于存入键值对个数的最大值,那么永远也不会发生扩展。

如果已确定会有大量的键值对会被存入hashMap,那么比起设定一个较小的初始容量,导致hashMap反复的扩展,一开始便设定一个足够大的初始容量的性能要更高。

注意,本实现是线程不安全的。如果复数个线程同时访问hashMap,并且至少有一个线程导致hashMap发生了结构性变化(任何导致hashMap增加或删除至少一个键值对的操作,仅仅只是改变某个key的值并不算是结构性变化),那么就必须在外部对hashMap进行并发控制。通常,我们可以以Collections.synchronizedMap方法包装hashMap,从而实现线程安全化。如果我们需要保证hashMap的线程安全性,那么最好在创建之初就完成包装,以避免意外的线程安全性问题。例如,我们可以这样写:

1
Map m = Collections.synchronizedMap(new HashMap(...));

本实现所有的集合视图返回的iterator都是fail-fast的:在iterator创建后,若hashMap因该iterator之外的原因(也就是说不是iterator.remove方法导致的)发生了结构性变化,iterator将抛出ConcurrentModificationException。因此,面对并发修改时,iterator会简单干脆的承认失败,而不会进行复杂的风险评估,判断该并发修改是否会对自身产生影响。

我们并不能指望通过fail-fast来保证线程安全性,iterator抛出ConcurrentModificationException只是尽力而为。