JDK7 中的 HashMap

HashMap 能够看成是一个数组，每个数组元素是一个单向链表。

其中，每个链表的节点能够看成一个 Entry 实例，Entry 由两局部 (或者 4 个属性) 组成：key, value, hash 值和用于单向链表的 next。

一、初始化

在第一个元素插入 HashMap 的时候做一次数组的初始化，就是先确定初始的数组大小，并计算数组扩容的阈值。

private void inflateTable(int toSize) {
    // 保障数组大小肯定是 2 的 n 次方。// 比方这样初始化：new HashMap(20)，那么解决成初始数组大小是 32
    int capacity = roundUpToPowerOf2(toSize);
    // 计算扩容阈值：capacity * loadFactor
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 算是初始化数组吧
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

小结：

1. 数组的初始化大小肯定为 2^n，这是因为更快的定位元素，一个乏味的算法一个数x 对2^n取模，等价于x&(2^n-1)，例如：11%4 = 11&(4-1)，与运算相比取模运算在计算机看来快得多。
2. 不管咱们指定容器的容量为多少，初始化的时候大小主动设置为最相近的 2^n 那么大，例如，手动指定初始化容量为 11，其实初始化的时候，大小为 16，手动指定为 17，初始化大小则为 32。
3. 在 new HashMap 的时候不会初始化数组的大小，只有当 put 第一个元素到容器中的时候才会初始化。

二、get 过程剖析

分三步：

1. 依据 key 计算 hash 值。
2. 找到相应的数组下标(key 的 hash 值对数组的长度取模)：hash & (length – 1)。
3. 遍历该数组地位处的链表，直到找到相等 (== 或 equals) 的 key。

public V get(Object key) {// key 为 null 的话，会被放到 table[0]，所以只有遍历下 table[0] 处的链表就能够了
    if (key == null) return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();}

getEntry(key):

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

小结：

1. HashMap 的 key 和 value 都能够为 null，并将它放在数组的 0 号地位上。
2. 当 key 为 null 的时候，这个 key 对应的 hash 值为 0。

三、put 过程剖析

public V put(K key, V value) {
    // 当插入第一个元素的时候，须要先初始化数组大小
    if (table == EMPTY_TABLE) {inflateTable(threshold);// 见【一】}
    // 如果 key 为 null，最终会将这个 entry 放到 table[0] 中
    if (key == null) return putForNullKey(value);
    // 1. 求 key 的 hash 值
    int hash = hash(key);
    // 2. 找到对应的数组下标，见【四】int i = indexFor(hash, table.length);
    // 3. 遍历一下对应下标处的链表，看是否有反复的 key 曾经存在，//    如果有，间接笼罩，put 办法返回旧值就完结了
    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++;
    // 4. 不存在反复的 key，将此 entry 增加到链表中，见【五】addEntry(hash, key, value, i);
    return null;
}

小结：

1. 当插入第一个元素的时候，才会初始化数组大小。
2. 当 put 一个不存在的 key 时，返回 null，put 一个存在的 key 则返回原来的旧值。
3. 1.7 中没有红黑树概念，如果数据量很大，产生 Hash 抵触的概率很大，会以致链表过长，查问效率重大降落。

四、计算数组地位

应用 key 的 hash 值对数组长度进行取模

static int indexFor(int hash, int length) {return hash & (length-1);
}

五、增加节点到链表中

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果以后 HashMap 大小曾经达到了阈值，并且新值要插入的数组地位曾经有元素了，那么要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 须要扩容，先扩容，见【六】，再插入
        resize(2 * table.length);
        // 扩容当前，从新计算 hash 值
        hash = (null != key) ? hash(key) : 0;
        // 从新计算扩容后的新的下标
        bucketIndex = indexFor(hash, table.length);
    }
    // 在上面
    createEntry(hash, key, value, bucketIndex);
}
// 其实就是将新值放到链表的表头，而后 size++
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++;
}

这个办法的次要逻辑就是先判断是否须要扩容，需要的话先扩容，而后再将这个新的数据插入到扩容后的数组的相应地位处的链表的表头。

小结：

1. 呈现 Hash 抵触的时候，采纳链地址法，将新元素插入到旧链表的头部。
2. 须要扩容的话，先扩容再插入，区别于 1.8。

六、数组的扩容

在插入新值的时候，如果以后的 size 曾经达到了阈值，并且要插入的数组地位上曾经有元素，那么就会触发扩容，扩容后，数组大小为原来的 2 倍。

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

// transfer 办法

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，迁徙到新数组的 i 号地位，即 newCapacityp[i]
            e.next = newCapacityp[i];
            newCapacity[i] = e;
            e = next;
        }
    }
}

扩容就是用一个新的大数组替换原来的小数组，将所有的元素从新计算 Hash 值，并将原来数组中的值迁徙到新的数组中。原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 地位上。比方原来数组长度是 16，那么扩容后，原来 table[0] 处的链表中的所有元素会被调配到新数组中 newTable[0] 和 newTable[16] 这两个地位。

小结：

1. 多线程并发中，transfer办法可能会以致新数组生成环状链表，这样再查问这个链表上没有的元素的时候，会造成死循环，CPU 飙升。
2. 迁徙数据的时候须要将所有旧数组上的元素从新计算一次 Hash，区别于 1.8。