基于JDK1.8的HashMap源码解析三(get和remove以及迭代器)

本篇博客主要讲解了HashMap的get和remove和迭代器

相关系列

基于JDK1.8的HashMap源码解析一(变量和构造器)
基于JDK1.8的HashMap源码解析二(put和resize操作)

HashMap的get操作

// get方法判断传入key的节点是否存在，存在则返回value值
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;
    // 判断entry数组是否有元素，以及当前key的hash所在的bucket是否存在Node
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 检查第一个Node的key是否和当前key相等,相同则返回头结点
        // 注意，第二个判断明显是可以判断null的，所以1.8并没有对null做特殊处理
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果首节点不存在查找的key,遍历后续的尾节点
        if ((e = first.next) != null) {
            // 红黑书，跳过。。。
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 循环遍历查找Node节点的key是否与查询的key匹配，匹配则返回
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 没找到
    return null;
}

// 判断是否有包含key的Node
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

// 判断HashMap是否包含value
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        // 遍历entry数组
        for (int i = 0; i < tab.length; ++i) {
            // 遍历每个bucket的链表
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                // 判断节点value值是否有包含查找的value
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

其实HashMap的get方法还是挺简单的。先通过hash计算出key所在的bucket，在通过循环便利其中的Node判断是否包含查找的key，如果找到则返回节点的value值。

HashMap的remove操作

// 删除节点方法
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

// 移除包含key的节点
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;
    // 判断数组不为空且key所在bucket不为null
    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 {
                // 循环遍历后续所有尾节点判断是否包含删除的key，找到则记录跳出循环
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // 记录当前非删除的节点，因为到了删除的节点就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;
            // 给linkedHashMap留的后门
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

public void clear() {
    Node<K,V>[] tab;
    // 内部操作数加1
    modCount++;
    // 如果entry数组不为空，则将数组元素全部清空
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

HashMap的删除方法也很简单。先计算删除的key的hash在哪个bucket，遍历链表记录要删除的节点之后把上一个节点指向要删除节点的下一个节点。

HashMap的迭代器

abstract class HashIterator {
    // 下一返回节点
    Node<K,V> next;
    // 当前节点
    Node<K,V> current;
    // 快速失败检测
    int expectedModCount;
    // 当前下标
    int index;

    HashIterator() {
        // 记录HashMap的内部操作次数
        expectedModCount = modCount;
        // 记录当前的entry数组
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        // 拿到第一个有Node的entry下标
        if (t != null && size > 0) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }
    
    // 判断是否有下一个节点
    public final boolean hasNext() {
        return next != null;
    }
    
    // 
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        // 迭代过程中原entry数组被操作过则快速失败
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 没有下一个元素还迭代则抛出异常
        if (e == null)
            throw new NoSuchElementException();
        // 移动到当前节点的下一节点，如果没有节点再继续寻找entry数组中下一个有节点的下标
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        // 当前节点等于null抛出状态异常
        if (p == null)
            throw new IllegalStateException();
        // 迭代过程中原entry数组被操作过则快速失败
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        // 正常情况调用删除节点
        removeNode(hash(key), key, null, false, false);
        // 因为调用删除之后内部操作次数会+1，所以重新赋值内部操作数
        expectedModCount = modCount;
    }
}

HashMap的内部迭代器采用fail-fast模式，即快速失败模式。我们可以发现迭代器的方法中，首先判断了”modCount”是否等于内部记录的”expectedModCount”，如果不是，那么直接抛出ConcurrentModificationException。这就说明了，在使用迭代器过程中，我们是无法对HashMap进行remove和put操作的，因为这都会让我们内部的modCount改变导致和记录的expectedModCount不一致。但是我们可以使用迭代器自己的remove方法，因为调用迭代器自己的remove方法会执行删除操作并更新expectedModCount。所以我们一定要注意，不要在迭代过程中直接对HashMap进行remove操作，而应该使用迭代器的remove操作。如果你想在HashMap迭代过程中实现新增，你可以自己继承一个HashMap创建一个自己的迭代器(我并不建议这么做，因为你要解决是否还需要遍历这个节点以及如何实现)