HashMap源码解读

本文简单分析下HashMap的源码，重点解读了HashMap的resize、put和remove方法。

HashMap类概览

先看一下HashMap中的一些重要字段和常用方法，这里先总结一下比较重要的属性：

• capacity：桶数组大小，默认16

• load_factor：加载因子，用来计算扩容的阈值

• threshold：扩容阈值，等于capacity*load_factor

• treeify_threshold：将链表转为红黑树的阈值，默认8

• untreeify_threshold：将红黑树转为链表阈值，默认6

• min_treeify_capacity：将链表转为红黑树，桶数组最小长度，默认64；也就是说数组长度小于64时，即使链表长度大于8也不会将其转为红黑树。

//继承自AbstractMap，实现了Map、Cloneable和Serializable接口
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    //默认大小为2^4，也就是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	//最大容量为一个int大小，2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
	//加载因子，默认为0.75，也就是size > 0.75 * capacity时，进行扩容
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	//链表长度超过8，转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
	//树中节点数量小于6，转成链表
    //这里留个小疑问，为什么是6而不是8
    static final int UNTREEIFY_THRESHOLD = 6;
    //capacity大于64，才会将链表转成红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
    //hash方法，允许key为null，key的hash值的低16位和高16位异或，应该是减少hash冲突
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
	//node数组
    transient Node<K,V>[] table;
    //entrySet的缓存
    transient Set<Map.Entry<K,V>> entrySet;
    //map中记录了多少个键值对
    transient int size;
	//阈值，前面提到过的，默认8
    int threshold;
	//加载因子，前面也提到过，默认0.75
    final float loadFactor;
    //get方法，通过key找对应value
    public V get(Object key) {
    }
    //判断是否包含key
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    //Map中元素添加到当前map
    public void putAll(Map<? extends K, ? extends V> m) {
    }
    //删除某个键值对
    public V remove(Object key) {
    }
    //删除Map中所有元素
    public void clear() {
    }
    //是否包含value
    public boolean containsValue(Object value) {
    }
    //通过key获取对应value
    public V getOrDefault(Object key, V defaultValue) {
    }
    public V putIfAbsent(K key, V value) {
    }
    public boolean remove(Object key, Object value) {
    }
    //forEach方法，内部其实就是个for循环
    public void forEach(BiConsumer<? super K, ? super V> action) {
    }
	//下面3个是迭代器方法
    final class KeyIterator extends HashIterator
    }
    final class ValueIterator extends HashIterator
    }
    final class EntryIterator extends HashIterator
    }
}

put()方法

在读源码前，这里先总结下put()方法中值得关注的一些细节：

• 桶下标：确定key的桶下标用的是(n - 1) & hash，而不是hash % n
  • 用位运算效率更高
  • 因为n始终是2的幂，可以保证(n - 1) & hash =hash % n
• 扩容：如果size > capacity * loadfactor，调用resize()对桶数组进行扩容
• 链表转红黑树：如果链表长度达到8
  • 如果capacity<64，扩容数组
  • 如果capacity>=64，将链表转为转红黑树

public V put(K key, V value) {
    //调用putVal方法
    return putVal(hash(key), key, value, false, true);
}
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是null，或者长度为0，需要调用resize函数初始化一下
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //(n-1) & hash = hash % n，因为n是2的次幂
    //这里也是HashMap扩容每次乘以2的原因之一，可以通过位运算快速确定元素下标
    if ((p = tab[i = (n - 1) & hash]) == null)
        //这个位置没有，直接放在链表头部
        tab[i] = newNode(hash, key, value, null);
    else {
        //这个位置已经有元素了，发生哈希冲突？或者两者key相同
        Node<K,V> e; K k;
        //p表示的是原来位置i处的节点
        //如果原来该位置的节点的hash等于参数hash，并且两者key相同，说明当前的put操作等价于更新
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //两个key不同，发生hash冲突，创建一个新的节点放到链表或红黑树中
        //节点是红黑树节点，走这条分支
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //是链表节点，走这条分支
        else {
            //遍历链表一直到链表尾部
            //如果中间发现相同的key，说明Map中存在该key，更新下key值对应的value即可
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //已经到了链表尾部，没有发现具有相同key值的键值对
                    //那就要创建一个新的节点，添加到链表尾部
                    p.next = newNode(hash, key, value, null);
                    //如果链表长度超过阈值（默认8），链表转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //找到具有相同key值的键值对，直接break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //e不为空，说明Map中存在相同key的键值对，直接更新
        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()方法

现在来看看resize()函数里面的扩容细节，这里面有三个细节需要注意：

• 桶数组大小是有限制的，默认为2^30，如果$oldCap*2 >2^{30}$不进行扩容，并将阈值设置成Integer.MAX_VALUE；
• e=oldTab[j]之后，立即将oldTab[j]=null，帮助gc？？；
• 迁移元素时，对于链表，将其分成两部分，其中一部分如果在j位置，迁移后依旧在j位置，剩下那部分迁移后在j+oldCap位置:
  • 链表中哪些节点index不变？hash & oldCap == 0的节点index不变，其余的变为j+oldCap；
  • 这一特性再次体现了数组容量是2的n次幂的好处。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //oldCap表示原始长度，oldThr表示原始的扩容阈值
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    //新的容量和扩容阈值
    int newCap, newThr = 0;
    //原始容量大于0，说明不是第一次
    if (oldCap > 0) {
        //如果旧的容量已经大于最大限制，也就是2^30，无法再扩容了，直接返回
        //并将扩容阈值设置成int型的最大值，即后续不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //数组大小乘2，也就是左移1位，同样地，新的扩容阈值也要乘2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //oldCap == 0，并且oldThr > 0 的情况下进入该分支
    //带初始容量构造器时，将容量设置成threshold
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //oldCap == 0，并且oldThr == 0 的情况下进入该分支
    else {               // zero initial threshold signifies using defaults
        //这种情况说明桶数组还是null，没有初始化，直接新建一个默认大小，也就是8的数组
        newCap = DEFAULT_INITIAL_CAPACITY;
        //扩容阈值 = 加载因子 * 容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新的阈值还是0，用加载因子乘以新的容量，得到新的阈值
    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"})
    //创建一个newCap大小的数组
    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) {
                //唉？很细节，先把旧数组j位置设成null，防止内存泄漏？快速gc？
                oldTab[j] = null;
                //这个位置就链表头一个元素，直接放到新数组对应位置即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //如果是个树节点，调用split方法把树中所有节点迁移到新数组中
                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-while循环遍历链表
                    do {
                        next = e.next;
                        //如果hash & oldCap == 0，这些元素不需要移动
                        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;
                        //loHead不需要移动，直接放到新数组j位置
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //hiHead需要移动，放到新数组j+oldCap位置
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

remove()方法

这里面需要注意的细节不多，比较有趣的一点是：删除节点后，如果红黑树节点数量小于等于6，将树转为链表，而不是8，防止在链表和红黑树之间来回转换。

public V remove(Object key) {
    Node<K,V> e;
    //直接调用removeNode方法
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
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) {
        //上面条件中，定位到hash(key)在桶数组中的index，并用p表示链表头节点
        Node<K,V> node = null, e; K k; V v;
        //如果表头就是我们要找的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);
            }
        }
        //找到了key对应的value，进入下面代码，否则直接返回
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

打赏