深入理解HashMap

前言

基于jdk 1.8

1，HashMap的原理，内部数据结构是什么样的？

数组 + 单向链表的形式，这就是HashMap的存储方式，那么如何去验证呢？

数组验证

我们先从源头开始查找，一般情况下，我们使用HashMap都是从put方法开始，所以我们就来看看put方法：

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        ……
     …….
}

从上面的代码你发现了什么？是不是发现put方法操作的是内部类数组 Node<K,V>[] ，没错，它就是用数组来管理的。

单向链表验证

上面我们已经知道了HashMap是通过内部类Node<K,V>来进行数据维护的，
而我们通过源码可以发现，Node<K,V>类还维护了一个next节点，指向的就是下一个节点，
这里又充分表明了它是以链表的形式进行的管理，并且是单向。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    …..
}

2，HashMap中的Hash算法的作用是什么呢？为什么需要这个Hash算法的存在？

HashMap是用数组的形式进行的存储，所以它是有大小和下标的，HashMap定义的数组的默认大小为16

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

a，根据hash算法得到一个整型数
b，控制这个数字在0到15之间
c，用hash也使得下标尽可能的分散

怎么获取的一个整数呢？可以通过 ””.hashCode()

如何控制在0到15之间呢？我们可以通过%16来得到。但是HashMap并不是这样做的，它是通过.hashCode()获得一个int 32位的数值进行高16位和低16位的异或运算得到的

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3，put的具体流程是什么？

a，我们上面已经说到了，HashMap在put的时候，会计算一个下标位置，那么，它会先去判断这个下标下是否已经有值，如果有值，那么比较一下，key是否相同，如果相同，那么对值进行一个覆盖操作，如果key不同，那么继续去判断该节点的next节点是否为空，如果不为空，那么继续向下判断，为空，则直接放到这个空间，也就形成了所谓的链表式存储，可以进行一个图解：



4，红黑树的引入

hashmap使用单项链表的形式来存储信息，那么必然会造成链表过长而导致性能地下的问题，
所以在jdk1.8之后，hashmap引入了红黑树，专门用来解决这个问题，那么我们下面就来看看它是怎么处理的。

我们来分析下putval方法中的这块代码：

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;


Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

重点关注 “if (binCount >= TREEIFY_THRESHOLD - 1)”，如果链表的节点大于8的时候，将链表转换为红黑树

还有 “p instanceof TreeNode”，如果数据结构是树形，那么直接走红黑树的处理方式

5，扩容

无论是链表还是红黑树，我们的数组长度都只有16，所以总有用完的时候，那么我们就涉及到一
个扩容了，那么我们就要去了解下，什么时候扩容呢？如何扩容的呢？

a，扩容因子

什么时候开始扩容，这个问题，hashmap的开发者已经做了相应的设置，他定义了一个静态常量=0.75作为扩容因子，
当数组size()达到了总长度*0.75的时候，就进行扩容，比如：16*0.75=12，那么就表示当数组size()超过12的时候开始扩容

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

扩容的步骤：
a，先计算一个新的数组的大小
b，创建一个新的数组，new
c，进行一个数据移动，old -> new

内容主要有3种共存的节点形式，逐个进行判断，然后转移，具体代码体现如下：
a，数组有元素，next无元素
b，数组有元素，next为链表
c，数组有元素，next为红黑树

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // preserve order
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    if ((e.hash & oldCap) == 0) {
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}
return newTab;

简单的看，也就这么多东西。