数据结构

• table，Entry 类型数组的数据
• Entry，包括了 key，value，Entry，以及 hash

final K key;
V value;
Entry<K,V> next;
int hash;

put 方法

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<K,V> 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;
}

putForNullKey 方法

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

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

indexFor 方法

注释已经提醒了，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);
}

addEntry 方法

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 方法
}

createEntry 方法

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

get 方法

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

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

getForNullKey 方法

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

getEntry 方法

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

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

transfer 方法

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

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

单线程情况：

多线程死循环情况：