HashMap源码分析

Java版本：

java version "1.7.0_79"
Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)

HashMap由散列表结构实现。

HashMap 主要成员变量：
因子越小，冲突越少。因子越小，越容易触发扩容，从而使每个数组节点上的元素数减少，查找的效率也会提高，但是同时将会消耗不少的空间。
因子小，以空间换时间
因子大，以时间换空间

/**
 * 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;

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

/**
 * The next size value at which to resize (capacity * load factor).
 * 阀值
 * @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).
 */
transient int modCount ;

Entry定义如下：

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 ;
        }

        /**
         * 只有当key与value同时相等时，才返回true
         * 
         */
        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.
         */
        void recordAccess(HashMap<K,V> m ) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m ) {
        }
    }

put()
在执行put方法时，会判断key是否已经存入，如果存入，则覆盖之前的值，否则将通过addEntry()方法添加一个Entry对象。
addEntry()方法，如果size大于等于阀值(容量*加载因子)并且table[bucketIndex]元素不为空，将会触发扩容，bucketIndex计算结果类似于取余运算。
扩容时，将会把table容量扩大一倍，并将之前table中的值，通过transfer方法放入newtable中（重新hash），最后将newtable赋给table。

/**
 * 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.
 *
 * @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) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value );
    int hash = hash(key);
    // indexFor函数在下面有详细介绍
    int i = indexFor(hash, table.length);
    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.
 * 容量扩大一倍，因为hashmap的容量总是为2的次方
 */
void addEntry( int hash , K key , V value , int bucketIndex) {
    if ((size >= threshold ) && (null != table[bucketIndex])) {
        resize(2 * table. length);
        hash = ( null != key ) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table. length);
    }

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

/**
 * 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.
 *
 * @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.
 * 如果newTable[i]不为空，那么将newTable[i]作为新插入元素的下一个元素，
 * 即插入元素插入到链表的最前端。
 */
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);
            }
            int i = indexFor( e. hash, newCapacity);
            e. next = newTable[i];  // 链式
            newTable[i] = e;
            e = next;
        }
    }
}


/**
 * Returns index for hash code h.
 * length为2的次方，那么length-1二进制则为111111...形式；
 * &运算：1&1=1,1&0=0,0&1=0，0&0=0
 * 当h小于length时，结果即为h，当h大于length时，最后结果也将小于length，
 * 个人理解结果为h%length，效率却高于h%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);
}