HashMap源码分析(II)

shysh95

发布于 2020-04-14 16:41:51

2650

发布于 2020-04-14 16:41:51

文章被收录于专栏：shysh95

上一节主要讲述了HashMap的一些基础属性和构造方法，本节将会讲述HashMap的核心方法。

put方法

public V put(K key, V value) {
 
 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;
 
 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;
 
 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 (e != null) { // existing mapping for key
 
            V oldValue = e.value;
 
 if (!onlyIfAbsent || oldValue == null)
 
                e.value = value;
 
            afterNodeAccess(e);
 
 return oldValue;
 
 }
 
 }
 
 ++modCount;
 
 if (++size > threshold)
 
        resize();
 
    afterNodeInsertion(evict);
 
 return null;
 
}

首先查看当前的bucket集合是否为空，如果为空则进行扩容，具体的扩容逻辑后面详细说
计算key存储在bucket的位置，并判断当前bucket位置上有没有数据节点，如果没有则新建一个
如果bucket位置上存在数据节点，如果数据节点的hash值等于新数据的hash，并且数据节点的key和新数据的key相等，最终只是用新节点的Value替换原来节点Value（onlyIfAbsent为false的前提下）
如果不满足3的条件，并且Node是个TreeNode的话，那么将采用红黑树的插入方式增加节点
如果不满足条件3并且节点不是一个TreeNode，则需要循环遍历链表中的节点，如果链表中的节点有和新的数据相等的节点，则直接退出，并且用新节点的Value替换原来节点的Value（onlyIfAbsent为false的前提下）
当遍历到链表节点的最后一个节点时，将该节点的下一个节点赋值为新的数据节点，并且判断是否已经满足树状化的条件，如果是则需要bucket中的链表进行树状化，除了满足TREEIFY_THRESHOLD需要还有一个条件才能进行树状化，那就是整个bucket的数量需要满足64
当新增完节点以后，会判断数量是否已经超过threshold，如果超过了就需要进行扩容

get方法

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


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

根据key值计算出来的hash找到bucket的位置，先比较第一个节点，如果key相等直接返回该节点
如果key不相等，然后判断节点如果是TreeNode，则需要遍历树找到对应的节点
如果节点不是TreeNode，则遍历列表找到key相等的节点

remove方法

public V remove(Object key) {
 
 Node<K,V> e;
 
 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) {
 
 Node<K,V> node = null, e; K k; V v;
 
 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)
 
 ((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;
 
}

首先还是计算bucket中的位置，如果bucket中的第一个节点相等，那么就需要把bucket中的元素替换为原来的节点的下一个节点
如果bucket中的第一个节点不相等，那么就需要根据Node类型来遍历树或者链表查找相等的节点
找到相等的节点以后，如果是树状化的节点，就将树中的节点移除，如果是链表，就需要将删除的节点的next值更改为要删除的的节点的next的值
最后修改size，也就是整个hashmap中节点的数量

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

首先要做的事计算cap和threshold的值，新的容量计算需要根据老的threshold，如果扩容是第一次，那么第一次扩容的的容量就是在初始化map时指定的容量值(initalCapacity)，如果不是第一次扩容，扩容后的容量就是扩容前的threshold值
threshold的值的计算规则是，如果容量已经超过了16，那么新的threshold直接在原来的基础上double，否则就是用新的容量*负载因子
将计算好的threshold进行赋值
扩容时首先准备好一个新容量的Node集合。
然后遍历bucket，取出bucket的节点，如果取出的bucket中的节点只有一个节点那么直接重新hash放入新的bucket中
如果不是，并且节点是一个树状节点那么就利用树节点的扩容逻辑并且将节点移到合适的位置
如果是链表这边JDK8也是做了优化，减少了重新hash的性能消耗，而是采用了一个简单的逻辑，当节点的hash值和原来的容量做与运算时如果结果为0，表示该节点还是在原来的位置，如果不是，那么就是在原来的位置再加+原来的容量的位置。

下面讲一下为什么用(e.hash & oldCap)==0就可以判断元素的位置，首先按照原来的计算位置的方法都是按照hash值和length-1进行与运算取值的，而length又都是2的N次幂，那么length-1说明低位全是1，新容量只不过是将老的容量进行左移一位，如果(e.hash & oldCap) == 0说明与新老length-1的计算结果是一样的，所以就在原位置，否则就是老位置+原数组长度。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-04-06，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap