HashMap的put和get原理，结合源码分析详细分析

 1 /**
 2  * Hash table based implementation of the <tt>Map</tt> interface.  This
 3  * implementation provides all of the optional map operations, and permits
 4  * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
 5  * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 6  * unsynchronized and permits nulls.)  This class makes no guarantees as to
 7  * the order of the map; in particular, it does not guarantee that the order
 8  * will remain constant over time.
 9  *
10  * <p>This implementation provides constant-time performance for the basic
11  * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
12  * disperses the elements properly among the buckets.  Iteration over
13  * collection views requires time proportional to the "capacity" of the
14  * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
15  * of key-value mappings).  Thus, it's very important not to set the initial
16  * capacity too high (or the load factor too low) if iteration performance is
17  * important.
18  *
19  * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
20  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
21  * <i>capacity</i> is the number of buckets in the hash table, and the initial
22  * capacity is simply the capacity at the time the hash table is created.  The
23  * <i>load factor</i> is a measure of how full the hash table is allowed to
24  * get before its capacity is automatically increased.  When the number of
25  * entries in the hash table exceeds the product of the load factor and the
26  * current capacity, the hash table is <i>rehashed</i> (that is, internal data
27  * structures are rebuilt) so that the hash table has approximately twice the
28  * number of buckets.
29  *
30  * <p>As a general rule, the default load factor (.75) offers a good tradeoff
31  * between time and space costs.  Higher values decrease the space overhead
32  * but increase the lookup cost (reflected in most of the operations of the
33  * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The
34  * expected number of entries in the map and its load factor should be taken
35  * into account when setting its initial capacity, so as to minimize the
36  * number of rehash operations.  If the initial capacity is greater
37  * than the maximum number of entries divided by the load factor, no
38  * rehash operations will ever occur.
39  *
40  * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
41  * creating it with a sufficiently large capacity will allow the mappings to
42  * be stored more efficiently than letting it perform automatic rehashing as
43  * needed to grow the table.
44  *
45  * <p><strong>Note that this implementation is not synchronized.</strong>
46  * If multiple threads access a hash map concurrently, and at least one of
47  * the threads modifies the map structurally, it <i>must</i> be
48  * synchronized externally.  (A structural modification is any operation
49  * that adds or deletes one or more mappings; merely changing the value
50  * associated with a key that an instance already contains is not a
51  * structural modification.)  This is typically accomplished by
52  * synchronizing on some object that naturally encapsulates the map.
53  */

1  /**
2      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
3      * (16) and the default load factor (0.75).
4      */
5     public HashMap() {
6         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
7     }

 1    /**
 2      * Constructs an empty <tt>HashMap</tt> with the specified initial
 3      * capacity and the default load factor (0.75).
 4      *
 5      * @param  initialCapacity the initial capacity.
 6      * @throws IllegalArgumentException if the initial capacity is negative.
 7      */
 8     public HashMap(int initialCapacity) {
 9         this(initialCapacity, DEFAULT_LOAD_FACTOR);
10     }

/**
     * 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();
    }

 1 /**
 2      * Associates the specified value with the specified key in this map.
 3      * If the map previously contained a mapping for the key, the old
 4      * value is replaced.
 5      *
 6      * @param key key with which the specified value is to be associated
 7      * @param value value to be associated with the specified key
 8      * @return the previous value associated with <tt>key</tt>, or
 9      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
10      *         (A <tt>null</tt> return can also indicate that the map
11      *         previously associated <tt>null</tt> with <tt>key</tt>.)
12      */
13     public V put(K key, V value) {
14         if (table == EMPTY_TABLE) {
15             inflateTable(threshold);
16         }
17         if (key == null)
18             return putForNullKey(value);
19         int hash = hash(key);
20         int i = indexFor(hash, table.length);
21         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
22             Object k;
23             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
24                 V oldValue = e.value;
25                 e.value = value;
26                 e.recordAccess(this);
27                 return oldValue;
28             }
29         }
30 
31         modCount++;//
32         addEntry(hash, key, value, i);
33         return null;
34     }
　　

 1  /**
 2      * Offloaded version of get() to look up null keys.  Null keys map
 3      * to index 0.  This null case is split out into separate methods
 4      * for the sake of performance in the two most commonly used
 5      * operations (get and put), but incorporated with conditionals in
 6      * others.
 7      */
 8     private V getForNullKey() {
 9         if (size == 0) {
10             return null;
11         }
12         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
13             if (e.key == null)
14                 return e.value;
15         }
16         return null;
17     }

1     /**
2      * Returns index for hash code h.返回hashCode值
3      */
4     static int indexFor(int h, int length) {
5         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
6         return h & (length-1);
7     } 

 1     /**
 2      * Adds a new entry with the specified key, value and hash code to
 3      * the specified bucket.  It is the responsibility of this
 4      * method to resize the table if appropriate.
 5      *
 6      * Subclass overrides this to alter the behavior of put method.
 7      */
 8     void addEntry(int hash, K key, V value, int bucketIndex) {
 9         if ((size >= threshold) && (null != table[bucketIndex])) {
10             resize(2 * table.length);
11             hash = (null != key) ? hash(key) : 0;
12             bucketIndex = indexFor(hash, table.length);
13         }
14 
15         createEntry(hash, key, value, bucketIndex);
16     }
17 
18     /**
19      * Like addEntry except that this version is used when creating entries
20      * as part of Map construction or "pseudo-construction" (cloning,
21      * deserialization).  This version needn't worry about resizing the table.
22      *
23      * Subclass overrides this to alter the behavior of HashMap(Map),
24      * clone, and readObject.
25      */
26     void createEntry(int hash, K key, V value, int bucketIndex) {
27         Entry<K,V> e = table[bucketIndex];
28         table[bucketIndex] = new Entry<>(hash, key, value, e);
29         size++;
30     }

 1  /**
 2      * Returns the value to which the specified key is mapped,
 3      * or {@code null} if this map contains no mapping for the key.
 4      *
 5      * <p>More formally, if this map contains a mapping from a key
 6      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 7      * key.equals(k))}, then this method returns {@code v}; otherwise
 8      * it returns {@code null}.  (There can be at most one such mapping.)
 9      *
10      * <p>A return value of {@code null} does not <i>necessarily</i>
11      * indicate that the map contains no mapping for the key; it's also
12      * possible that the map explicitly maps the key to {@code null}.
13      * The {@link #containsKey containsKey} operation may be used to
14      * distinguish these two cases.
15      *
16      * @see #put(Object, Object)
17      */
18     public V get(Object key) {
19         if (key == null)
20             return getForNullKey();
21         Entry<K,V> entry = getEntry(key);
22 
23         return null == entry ? null : entry.getValue();
24     }
25 
26     /**
27      * Offloaded version of get() to look up null keys.  Null keys map
28      * to index 0.  This null case is split out into separate methods
29      * for the sake of performance in the two most commonly used
30      * operations (get and put), but incorporated with conditionals in
31      * others.
32      */
33     private V getForNullKey() {
34         if (size == 0) {
35             return null;
36         }
37         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
38             if (e.key == null)
39                 return e.value;
40         }
41         return null;
42     }

 1    /**
 2      * Returns the entry associated with the specified key in the
 3      * HashMap.  Returns null if the HashMap contains no mapping
 4      * for the key.
 5      */
 6     final Entry<K,V> getEntry(Object key) {
 7         if (size == 0) {
 8             return null;
 9         }
10 
11         int hash = (key == null) ? 0 : hash(key);
12         for (Entry<K,V> e = table[indexFor(hash, table.length)];
13              e != null;
14              e = e.next) {
15             Object k;
16             if (e.hash == hash &&
17                 ((k = e.key) == key || (key != null && key.equals(k))))
18                 return e;
19         }
20         return null;
21     }

1  Map map = new HashMap();
2         map.put("123","456");
3         map.put("abc","456");
4         map.put("dd","456");
5         map.put("ss","789");
6         Object s = map.put("123","777");
7         System.out.println(map);//key不可重复，重复的话会将原来的value值覆盖,但是value的值不是唯一的，每个key都有唯一的一个value与之对应
8         System.out.println(s);//返回旧的value值456