HashMap源码解析(JDK1.7)

摘要：取模主要是为了能够平均的落在每个数组上面。在多线程的情况下，会造成死循环。把先暂存单线程情况，创建一个对象参见方法，然后把引入给数组的位置。队头插入的效率高，如果队尾插入，还要遍历链表。此时，线程执行以下代码。

table，Entry类型数组的数据

Entry，包括了key，value，Entry，以及hash

final K key;
V value;
Entry next;
int hash;

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);//见putForNullKey方法
    int hash = hash(key);
    int i = indexFor(hash, table.length);//见indexFor方法，取模
    for (Entry e = table[i]; e != null; e = e.next) {//遍历落在取模的数组上，遍历链表
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//判断hash值一样，并且key也要一样
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);//见addEntry方法
    return null;
}

key为空的情况，在数组的第一个位置的链表遍历查找，如果有key为空，返回相应的值，如果没有，添加到链表后面。

private V putForNullKey(V value) {
    for (Entry 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;
}

注释已经提醒了，length长度必须是2的非0幂数，h & (length-1)是对h%length的意思（length长度为2的非0幂数时有效）。比如123243423 % 16的值是15，123243423 & 15也是15，当然123243423是我随便打的。取模主要是为了能够平均的落在每个数组上面。

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

void addEntry(int hash, K key, V value, int bucketIndex) {
    //扩容为2倍长度，跟上面取模要求的一样，乘以2也是2的非0幂数
    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);//见createEntry方法
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex];//取到数组的位置的entry
    table[bucketIndex] = new Entry<>(hash, key, value, e);//新entry加到链表的头部，并把数组指向新entry
    size++;
}
/**
 * Creates new entry.
 */
Entry(int h, K k, V v, Entry n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry entry = getEntry(key);//见getEntry方法

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

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry e = table[0]; e != null; e = e.next) {//因为put的时候，直接放数组的第一个，所以查询的时候，也查询第一个
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);//先取hash
    for (Entry 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))))//判断hash和key都相等
            return e;
    }
    return null;
}

这个方法在调用put的时候，在resize扩容的时候调用。在多线程的情况下，会造成死循环。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        while(null != e) {
            Entry next = e.next;//把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;
        }
    }
}

1、put("a",1)，创建一个entry对象（参见createEntry方法），然后把引入给数组0的位置。

2、put("b",1)，再创建一个entry对象，然后新对象的next指向旧的entry对象，最后数组指向新entry。队头插入的效率高，如果队尾插入，还要遍历链表。


3、如果扩容到4，参加transfer方法，依然采用队头插入，也就是说，如果链表是1，2，3，4，那么插入后就变成4，3，2，1。
现创建一个表，取到链表数据，开始遍历。这里假设都到index为3的数组。

Entry next = e.next;//把next先暂存
e.next = newTable[i]时，这个e是key为b的entry
newTable[i] = e;执行完后，index为3的数组执行b。

现在执行暂存的a
继续执行上面几个步骤，完成扩容，结果如下：

我们设想一下，如果两个线程同时进行扩容，A线程获取key为b的entry的时候，时间分片到了，现在线程B线程执行，完成上面单线程的情况。
此时，A线程执行以下代码。

e.next = newTable[i];
newTable[i] = e;
e = next;

e.next = newTable[i];的时候，此时b的next指向a

newTable[i] = e;的时候

可以看到，index为3的指向b，b的next指向a，a的next指向b。当有get操作，并且hash也落在index为3的时候，就死循环了。