HashMap源码分析(JDK1.7)

HashMap JDK1.7 概述

HashMap是一个以Key-Value键值对方式存储的集合，每一个键值对也叫做Entry。

HashMap里面的数组

几个重要参数

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

• DEFAULT_INITIAL_CAPACITY：默认HashMap初始大小。初始在初始默认状态下，HashMap中的数组长度Capacity为16，长度是2的幂。
• DEFAULT_LOAD_FACTOR：负载因子。默认LoadFactor为0.75。
• MAXIMUM_CAPACITY：HashMap最大容量。HashMap的容量是有限的。

当HashMap.Size >= Capacity * LoadFactor时，HashMap将进行Resize操作，为什么HashMap初始默认长度为16，目的是为了降低hash碰撞的几率。我们先看平时常用的Put和Get的方法。

---

Put方法

以下为JDK1.7中HashMap中的put方法，我们来举个例子说明一下整体过程。

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        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;
    }

当我们调用put方法：put("apple", 0)，往Hashmap中插入一个key为apple，value为0的元素，从源码中来看，经过两个判空的操作后，来到了int hash = hash(key);这一步，这一步是对插入元素的key进行做一次hash函数取到hash值，再来到int i = indexFor(hash, table.length);计算到这个元素在Hashmap中的index，
假设计算出的index为2，那么当前Hashmap：

index2插入一个元素
经过了多次put操作，Hashmap中的元素越来越多，用hash函数难免会遇到index冲突，比如
index2冲突了
出现这种情况的时候Hashmap使用链表来解决这种情况，HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点，当新的Entry映射到了冲突的位置，会使用头插法插入到链表的头部（使用头插法是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大）：
头插法插入到冲突位置

---

Get方法

以下为JDK1.7中HashMap中的get方法及getEntry方法，同样举例说明整体过程：

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

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

    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : 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;
    }

当我们调用get方法，将key传入传入到getEntry，首先是hash函数操作：int hash = (key == null) ? 0 : hash(key);，取到hash值，然后来到for循环
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next)，
调用indexFor取到对应的index，如果存在上面提到Hashmap中index冲突，一个位置存在多个Entry的情况，这时候先取到index位置中链表的头结点，判断key的值是否为所要查找的key的值是否相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))，
如果不相等则继续e = e.next取得链表下一个节点，继续判断key，最终找到key相等的结果返回出去。

index冲突，查找链表中并判断key

---

高并发下的HashMap存在的问题

当调用put方法的时候，会调用到put方法中的addEntry方法，addEntry方法具体如下：

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

HashMap的容量是有限的，当HashMap.Size >= Capacity * LoadFactor时，在addEntry时就会触发resize方法
HashMap在高并发下会出现问题，问题出在其resize方法中的transfer方法。
我们来看一下resize方法：

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

resize时会创建出一个2倍原来HashMap的长度的Entry数组，接着调用transfer方法，transfer方法的作用是遍历原Entry数组，把所有的Entry重新Hash到新数组，一下是addEntry
方法：

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

长度扩大以后，Hash的规则也随之改变
而这一段代码：

                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;

就是重新计算hash，然后放到新的数组的代码，在执行最后三行代码时，即使index冲突，也会使用头插的方式插入Entry。
当有两个线程同时对一个已经到临界扩容状态的HashMap进行操作时，两个线程都对该HashMap进行resize操作，假设线程B进入到transfer里面Entry<K,V> next = e.next;后挂起，然后线程A完成了所有resize操作，线程B继续操作，线程A操作后的由于存在Entry重新分配后顺序改变，线程Btransfer方法将引发Entry链表成环的状况，此后如果调用get查找一个不存在key的而且hash恰好位于链表的位置，则会引发死循环，这就是HashMap在1.7及1.7版本一下时高并发存在的问题。