存储结构

说明：本次讲解的HashMap是jdk1.8中的实现，其他版本可能有差异

内部是由Node节点数组组成，Node节点之间又由链表或红黑树组成。

图是网上找的，实在不想画

属性介绍

    //存储数据的数组，初次使用时初始化，分配的长度总是2的冥次方
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    //容器中包含的所有元素数量
    transient int size;

	//代指HashMap结构被修改的次数，结构修改是指更改HashMap中映射的数量或以其他方式修改其内部结构的修改 
    transient int modCount;

    //下一次扩容的大小值 (capacity * load factor)
    int threshold;

    //扩容系数
    final float loadFactor;

构造方法

HashMap有4个构建方法，主要作用就是初始化存储数组容量、扩容系数、下一次触发扩容大小

public HashMap(int initialCapacity, float loadFactor) {
    	//初始容量，不能小于0，否则抛非法参数异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    	//容器超限了，则默认设置为最大值，2^30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    	//扩容系数设置不对，也会抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor; //设置扩容系数
        //根据设置的初始数组大小计算下次触发扩容时的大小，初始情况下threshold也表示数组的初始大小，这个可以通过resize()方法中看到
        this.threshold = tableSizeFor(initialCapacity);  
    }

    public HashMap(int initialCapacity) {
        //调用第一个构造方法，loadFactor默认0.75
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        //只设置loadFactor，默认0.75，其他字段都默认值
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false); //创建新的hashmap，并把原来的m内容填充进去
    }

散列算法

static final int hash(Object key) {
    int h;
    //h >>> 16 hash值右移16位，实际上就是将高16位通过右移到低16位，然后通过与原hash值异或处理，使高16位也参与到索引数组位置的计算当中，这样做的好处是为了同时保留高16位于低16位的特征，让哈希后的结果更均匀的分布，减少hash冲突，提升hashmap的运行效率。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap是根据hash值，通过以下方式计算存储的位置：(数组长度 - 1) & (h ^ (h >>> 16))

(n-1) & hash判断元素存放的位置，n等于数组的长度，与运算相当于取余运算(计算效率较取余运算更高)。假如不做 (h >>> 16) 右移运算，那么hash仅是最后四位和1111运算(假如数组长度为16)那么hash高位的信息就会全部丢失（比如，多个key的hashcode最后四位都是0000那么就会全部存储在索引为0的桶中产生冲突），如果右移16位就会将高位的信息与低位的16位异或运算，保留了高位与低位的特征更能体现key的hashcode的特征，降低冲突的概率。

put方法

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

/**
     * Implements Map.put and related methods.
     *
     * @param hash key的hash值
     * @param key the key
     * @param value 要存放的value
     * @param onlyIfAbsent如果为true，那么容器中如果存在就不改变已存在的值；否则替换
     * @param evict 意为逐出，在LinkedHashMap中有用，可以想像成LRU算法中对过期数据的删除
     * @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;
    //初次进来table为空
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; //通过resize()方法初始化table数组，并得到数组长度
    //(n - 1) & hash  根据hash取模求出在数组中的位置，并判断该位置是否已经有值，当前判断是无值状态
    if ((p = tab[i = (n - 1) & hash]) == null)
        //该索引位置没有值，那么创建新node，并赋值在该索引位置上
        tab[i] = newNode(hash, key, value, null);
    else {
        //走到这里，证明当前索引位置已经有冲突了
        Node<K,V> e; K k;
        //如果hash和key的值同时相等，那么就认为是同一个值，直接覆盖原来索引位置下的节点（value值的覆盖取决于onlyIfAbsent或者原node的value是Null）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            //走到这里，证明冲突的节点不是完全相同的，并且原节点已经是（红黑）树化的节点了，那新节点肯定也应该是TreeNode
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //不是树，那就是链表，接下来执行链表的操作
            for (int binCount = 0; ; ++binCount) {
                //从链表头部开始遍历，一直到尾部，将新的node直接插入到尾部
                if ((e = p.next) == null) {
                    //尾部插入
                    p.next = newNode(hash, key, value, null);
                    //判断链表节点数是否大于等于TREEIFY_THRESHOLD（默认8），这里-1的原因，就是没算进新创建的节点，超过了，那么要（红黑）树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表转红黑树，转换条件：1.链表节点数大于8；2.数组长度大于MIN_TREEIFY_CAPACITY（默认64）
                        treeifyBin(tab, hash); 
                    break;
                }
                //遍历链表的同时，判断有没有节点完全相同的，有的话，直接退出遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 存在相同的key
            V oldValue = e.value;
            //根据onlyIfAbsent的条件，判断是否覆盖原节点的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; //覆盖原值
            afterNodeAccess(e); //这也是个钩子方法，hashmap中没有实现
            return oldValue; //返回原值
        }
    }
    //修改次数加1
    ++modCount;
    //size加1，并判断是否超过扩容触发条件，超过后重新扩容
    if (++size > threshold)
        resize(); //扩容
    //这是一个钩子方法，留待子类实现，比如在LinkedHashMap中就有使用
    afterNodeInsertion(evict);
    return null;
}
//树化方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //数组长度不足MIN_TREEIFY_CAPACITY（64）则不树化，只做扩容，避免数组节点都挤压（冲突）
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
     * Implements Map.get and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //判断数组不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //hash计算得到数组索引位置对应的节点，判断当前节点是否与要获取的hash和key一致，是的话，直接返回，不是继续往下走
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //找到下一个节点，这里要说明一下，即使节点树化后，依然会维持原有的链表状态
            if (first instanceof TreeNode)
                //从红黑树中取出节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //遍历链表取出节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

remove方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

   	/**
     * Implements Map.remove and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //判断数组不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //hash计算得到数组索引位置对应的节点，判断当前节点是否与要获取的hash和key一致，是的话，不用找了，已经找到了，并把node设置为当前找到的p，不是的话则继续往下走
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            //找到下一个节点，这里要说明一下，即使节点树化后，依然会维持原有的链表状态
            if (p instanceof TreeNode)
                //从红黑树中取出节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                 //遍历链表取出节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                //红黑树节点，从树中删除，removeTreeNode方法针对节点数较少的情况，又会转会链表
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                //链表中第一个节点，直接移除，用next节点来填充
                tab[index] = node.next;
            else
                p.next = node.next; //找到的中间节点，则直接断链就行
            ++modCount; //增加修改次数
            --size; //大小减1
            afterNodeRemoval(node); //钩子方法
            return node;
        }
    }
    return null;
}