HashMap分析

HashMap分析     

HashMap内部有一个Entry数组，可以称之为hash table。HashMap的默认构造值为初始容量为16，负载因子为0.75，阀值(初始容量*负载因子)为12。其默认构造子如下：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{

    /** *//**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 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.
     * 
     * 如果一个较大的值被任意一个带有参数的构造器指定，最大容量被使用。
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;   //1073741824

    /** *//**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** *//**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] 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
     */
    int threshold;

    /** *//**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;  
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];  //默认情况下，以容量为16构建Entry数组
        init();
    }

put方法分析：
 <1>HashMap首先判断key是否为null，如果为null，
    <1.1>HashMap从hash table中第0个位置的Entry，如果该Entry不等于null且entry.key也不为null，当前value覆盖entry的value。
    <1.2>否则，在hash table[0]处创建新的key=null的Entry。
 <2>
    接下来，以key的hashcode做hash运算，获得hash值。该hash值与hash table的长度-1做与操作，获得key在当前hash table中的位置索引。
    然后检查在该索引位置是否存在Entry对象，如果存在，且该Entry对象的key的hash值与上面计算的hash值相等，且entry的key与传入的key相等或者key.equals(entry.key),那么以当前的value值覆盖旧值，并返回旧值。
    如果hash table中不存在key所指定的Entry，那么就要增加新的Entry。在增加Entry后，要检查容量是否已经达到阀值，如果达到阀值，就以当前hash table的长度的2倍扩展。同时要重新计算entry在新的hash table中的索引位置。注意，由于hash计算可能导致key的hash值可能是重复的，HashMap采用链表的方式解决hash值冲突的问题，另外一种解决方法是开放地址法。
    以下是put方法部分代码：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        
        /**//*这里对key的hasCode做hash*/
        int hash = hash(key.hashCode());
        /**//*通过hash值与hash表的长度减1做与操作获取hash表的索引值*/
        int i = indexFor(hash, table.length);
        /**//*由于hash可能重复，导致获取重复的索引值，这里通过判断传入的key的has值与当前节点的key的has值是否相等，且key相等或者equals相等，来用新的value替换旧值，并返回旧值*/
        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;
    }

处理key为空的情况：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />--> private V putForNullKey(V value) {
        /**//*从0桶查找key为null的Entry。如果桶中有null的Entry，那么把当前新的值设置到Entry中，并返回旧值*/
        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;
    }

计算key的hash值与计算key所应处在hash table中的位置：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->static int hash(int h) {
        // 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).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /** *//**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

增加entry节点以及扩容：

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />--> void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];//临时存储指定桶索引的Entry
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//在指定桶索引位置创建新的Entry，并自动把原桶索引的Entry作为当前Entry的next
        /**//*当size达到阀值(当前容量*负载因子=threshold)，需要扩容*/
        if (size++ >= threshold)
            resize(2 * table.length);
    }

------------------------------------------------

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />--> void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        /**//*如果就有容量达到默认的的容量最大值(2的30次方),threshold设为整形的最大值（2的31次方-1）*/
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        /**//*这里把源hash表中的数据拷贝到新的hash表中，注意的是，源hash表中链表到新hash表中由头变成了尾*/
        transfer(newTable);
        table = newTable;
        /**//*设置扩容后新的阀值*/
        threshold = (int)(newCapacity * loadFactor);
    }

get方法分析：
    当调用get方法时，HashMap首先判断key是否为null,如果为null，其hash值为0，否则通过hash算法计算。
    接下来，通过该hash值与hash table的长度-1做与操作，获得key在hash table中的索引。如果entry不等null，且该传入key的hash值与entry的hash值相等，且key==entry.key或者key.equals(entry.key)，则返回该entry.value.否则返回null.

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        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;
    }