HashMap存储数据过程

数据结构中由数组和链表来实现对数据的存储，他们各有特点。

数组：占用空间连续。寻址容易，查询速度快。但是，增加和删除效率非常低。

链表：占用空间不连续。寻址困难，查询速度慢。但是，增加和删除效率非常高。

那么，我们能不能结合数组和链表的优点(即查询快，增删效率也高)呢? 答案就是“哈希表”。哈希表的本质就是“数组+链表”。

首先给出结论：HashMap底层是数组加链表，JDK1.8后又进行了优化，链表长度达到8后会转成红黑树。

我们从HashMap的一个put(key,value)方法看看元素的存储数据过程。

几个重要的成员变量

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;
    
    /**
     * The default initial capacity - MUST be a power of two.
     * 默认数组初始大小：16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**
     * The load factor used when none specified in constructor.
     * 默认负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * The next size value at which to resize (capacity * load factor).
     * 集合存储元素数量达到该值触发扩容（负载因子*容量[默认16]）
     * @serial
     */
    int threshold;
    
    /**
     * The load factor for the hash table.
     * 实际负载因子
     * @serial
     */
    final float loadFactor;
    
    /**
     * 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.)
     * 核心数组，数组长度必须为2的整数幂
     */
    transient Node<K,V>[] table;
    
    /**
     * The number of key-value mappings contained in this map.
     * 集合存储元素数量
     */
    transient int size;
    
    ...

Node结构

一个Node就是代表链表的一个节点，一个Node对象存储了：

key：键对象
value：值对象
next:下一个节点
hash: 键对象的hash值

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node单链表结构图：

Node[]核心数组存储结构图：

再看put(K key, V value)方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hash()

为啥不用Object的hashcode方法？这段代码叫“扰动函数”，主要是增加随机性，避免哈希冲突。具体参考：JDK 源码中 HashMap 的 hash 方法原理是什么？

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putVal

参数三默认是false代表如果key存在则会替换存在value值。

/**
 * 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;
    // 如果核心数组为空代表需要初始化，resize()方法既能初始化也能扩容。后续讲。
    //注意此时核心数组table的引用已经传递给tab。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n-1)&hash 可以理解为 hash%n 找到数组中的索引位置i
    // 如果是空则直接放进去就行，放入的是个节点Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 以下是有值的情况，也就是出现了hash冲突。    
    else {
        Node<K,V> e; K k;
        //第一种情况：已存在的key值hash相同且key相同则替换即可。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //第二种情况：节点已经转换成TreeNode，也就是说已经转换成红黑树，存储则需要根据红黑树的规则自旋存储，具体不展开。  
        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);
                    //达到8条则转换成红黑树
                    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;
            }
        }
        // 以上二三情况找到已存在节点e 再根据条件选择是否替换value， 我们onlyIfAbsent是false 则会替换。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //当集合元素数量达到扩容数量触发resize扩容。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize()

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 情况一：通过旧表长度是否大于0判断是初始化还是扩容，如果大于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
    }
    // 情况二：当旧表长度不大于0时，通过oldThr是否大于0来判断是默认容量初始化还是给定容量初始化，当为给定容量初始化时
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 情况三：默认容量初始化
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 以下开始扩容，实际是重新创建新的table，大小为旧的两倍。然后元素重新计算hash值存入新的table。
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //单节点情况重新hash就行
                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;
}

这张图中index=2的桶中有四个节点，在未扩容之前，它们的 hash& cap 都等于2。在扩容之后，它们之中2、18还在一起，10、26却换了一个桶。这就是这句代码的含义：选择出扩容后在同一个桶中的节点。

所以lo和hi这两个链表的作用就是保存原链表拆分成的两个链表。

总结

总结一下大致的存储过程：

hash()方法获取key的哈希值
(n-1) & hash 计算出数组索引值i
生成Node(hash,key,value,next)对象
判断table[i]是否为null，为null则将新生成的Node存入
不为null则比较哈希值以及equals，相同则替换Node的value，不相同则遍历链表放入链表尾部，中间如果有相同的节点同样也替换value。
如果链表长度达到8则转换成红黑树。

源码总结：

HashMap默认容量为16，且容量必须为2的整数幂
默认负载因子为0.75
每次扩容大小为原来的2倍
jdk1.8后HashMap存储结构为数组加链表加红黑树，链表长度达到8则转换成红黑树
HashMap key可以为null
key相同会替换value
jdk1.8后链表改为尾插法
HashMap非线程安全