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。