HashMap的底层存储方式

HashMap的底层存储方式分为数组+链表和数组加红黑树两种方式。

在HashMap的成员变量中，有两个参数来决定node的挂载方式是链表还是红黑树。

HashMap成员变量解释：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;    默认的数组长度

static final int MAXIMUM_CAPACITY = 1 << 30;           最大数组长度

static final float DEFAULT_LOAD_FACTOR = 0.75f;        默认的加载因子  

static final int TREEIFY_THRESHOLD = 8;                当元素个数超过8时链表结构变为红黑树结构

static final int UNTREEIFY_THRESHOLD = 6;              原来红黑树结构元素个数小于6时变为链表结构

static final int MIN_TREEIFY_CAPACITY = 64;            最小树形化阈值

HashMap构造函数分析：

1、最常用的无参构造函数，所有的参数使用默认配置

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

2、提供数组长度的构造函数。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

3、提供数组长度和加载因子的构造方法

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

4、带容器的构造方式，将原有容器的对象，全部put到新创建的HashMap对象中

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

重要方法解析

resize()  //动态扩容方法

以下是摘录的resize方法中动态扩容的部分。

在putVal()方法最后，会有个对threshold的判断，threshold是用来决定是否对map就行扩容的关键。当size++的值大于threshold时，调用动态扩容方法。

扩容部分

1、当第一次进行put操作时，oldCap和oldThr都为0

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

新的数组大小就是默认值16，扩容阈值就是16*0.75=12

2、当oldCap大于0时，如果原来空间大于等于最大空间时，直接返回原来空间，无法扩容

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}

3、当oldCap大于0时，oldCap大于16且oldCap*2小于最大空间时，newThr=oldThr*2；

4、oldCap不大于0，oldThr 大于0，一般是map存储数据过后进行清空。新的数组大小就是原来阈值大小。

else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;

当数组需要扩容时，新的数组大小和扩容阈值都计算出来后，剩下的就是数据迁移。

首先创建一个大小为newCap的node数组。

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

如果原来数组中有数据，那就需要进行迁移。

迁移部分

1、如果数组j下标只有一个元素。next==null,直接计算出他在新数组的位置，赋值过去。

if (e.next == null)
    newTab[e.hash & (newCap - 1)] = e;

2、如果数据j下标是红黑树存储结构，按照红黑树方式进行迁移

else if (e instanceof TreeNode)
    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

3、如果数组下标j是链表存储，且有个多个的时候。用do，while循环方式，对每个node元素进行定位

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

实际put方法

putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

1、如果是第一次put数据，先对容器进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

2、根据数组长度-1的结果跟key的hash值与运算得到node在数组中的位置

[i = (n - 1) & hash]

3、如果当前位置为null，创建新node存入数组

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

4、如果当前下标有数据且是红黑树存储，插入新的树节点

if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

 5、如果当前节点有数据，链表存储，使用循环的方式往下添加

当链表个数达到树形化阈值的，当前下标下链表树形化

如果下标下key相同，修改node为新的value。

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

根据key移出数据

remove(Object key)

return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;

根据key的hash值确定下标，如果下标相同，key相同，删除节点。

根据key获取数据

getNode(int hash, Object key) 

根据key的hash值确定数组下标。

如果是链表结构，通过循环的方式进行key匹配。找到key相同的node

如果是红黑树，通过循环的方式，遍历节点，找到key相同的node。

返回value。