HashMap源码分析：get(Object key)

超、凢脫俗 2023-10-05 11:48 12阅读 0赞

HashMap取值比赋值的逻辑要简单一些，赋值像是连环锁，而取值就是解连环锁。取值主要是链表的取值、红黑树的取值。首先先看一下get方法：

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

getNode(hash(key), key)方法包含了链表的取值以及红黑树的取值。

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值的第一个节点
                //若当前first的hash值和key值与当前的参数里面的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)//若当前first节点为红黑树的节点
                        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;//都不符合条件即返回null
        }

链表的取值：

if ((e = first.next) != null) {//若下个节点不为空
                    ···
                    do {//循环遍历链表
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }

这个就是循环链表取值，它的逻辑如图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70][]

红黑树取值逻辑： 和链表差不多，也是一级一级的去查找key所在位置，情况会比链表多一些。

代码：

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
                TreeNode<K,V> p = this;
                do {
                    int ph, dir; K pk;
                    TreeNode<K,V> pl = p.left, pr = p.right, q;
                    if ((ph = p.hash) > h)
                        p = pl;
                    else if (ph < h)
                        p = pr;
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                        return p;
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.find(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
                return null;
            }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201016163523704.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201016173239101.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70